547E - Mike and Friends - CodeForces Solution

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <tuple>
 
#define all(a) a.begin(), a.end()
#define cnt0(x) __builtin_ctz(x)
#define endl '\n'
#define itn int
#define ll long long
#define ull unsigned long long
#define rep(i, a, b) for(int i = a;i <= b; i ++)
#define per(i, a, b) for(int i = a;i >= b; i --)
#define cntone(x) __builtin_popcount(x)
#define db double
#define x first
#define y second
#define AC main(void)
#define HYS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
using ld = double long;

const long double eps = 1e-9;
int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, k;
int _ = 1;
const int MOD = 10007;

struct node{
	int l, r, cnt;
}tr[N * 21];

struct Historical_Segment_Tree{
	int idx;
	int root[N];
	
	inline int build(int l, int r){
		int q = ++ idx;
		if(l == r)	return q;
		int mid = l + r >> 1;
		tr[q].l = build(l, mid);//存的是左儿子的编号并非边界
		tr[q].r = build(mid + 1, r);
		return q;
	}

	inline int insert(int p, int l, int r, int x, int sum){//需要用到的上一个版本root[i - 1](返回的值是当前版本的root)
		int q = ++ idx;
		tr[q] = tr[p];//复制上一个节点的信息
		if(l == r){
			tr[q].cnt += sum;//新版本的信息加1
			return q;
		}
		int mid = l + r >> 1;
		if(x <= mid)	tr[q].l = insert(tr[p].l, l, mid, x, sum);//在左子树则需要更新信息，否则保留原本信息就可以
		else tr[q].r = insert(tr[p].r, mid + 1, r, x, sum);
		tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
		return q;
	}

	inline int query(int p, int q, int L, int R, int l, int r){
		if(L >= l && R <= r)	return tr[q].cnt - tr[p].cnt;
		int mid = L + R >> 1;
		int cnt = 0;
		if(l <= mid)	cnt += query(tr[p].l, tr[q].l, L, mid, l, r);
		if(r > mid)		cnt += query(tr[p].r, tr[q].r, mid + 1, R, l, r);
		return cnt;
	}

	inline int query(int p, int q, int l, int r, int k){//区间k小
		if(l == r)	return l;
		int mid = l + r >> 1;
		int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
		if(cnt >= k)	return query(tr[p].l, tr[q].l, l, mid, k);
		else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
	}
}HST;

struct Aho_Corasick_Automaton{
	int cnt[N], tr[N][26], idx, q[N], nxt[N], mx[N];
	int pre[N];//跳到上一个有终止节点的位置
	int son[N];//
	int id[N], reid[N];//每个字符串原串位置的标记
	int sz[N], h[N], e[N], ne[N], dfn[N], tdl, idx1;//ac自动机fail树上建dfs序数组
	int vis[N * 2], used[N * 2];//找环

	inline void add(int a, int b){
		ne[idx1] = h[a], e[idx1] = b, h[a] = idx1 ++;
	}

	//多组测试清空操作
	inline void init(){
        for(int i = 0; i <= idx; i ++ ){
        	memset(tr[i], 0, sizeof tr[i]);
        	nxt[i] = cnt[i] = ne[i] = 0, h[i] = -1;
			vis[i] = used[i] = 0;
        } 
        idx = tdl = idx1 = 0;
    }

	inline bool findcycle(int u){//AC自动机找从0号是否可以有环(不能经过字符串被标记的地方)
		if(used[u] == 1)	return true;
		if(used[u] == -1)	return false;
		vis[u] = used[u] = true;
		for(int i = 0; i < 2; i ++)
			if(!son[tr[u][i]])	if(findcycle(tr[u][i]))	return true;
		used[u] = -1;
		return false;
	}

	inline void dfs(int u){//dfs序
		sz[u] = 1, dfn[u] = ++ tdl;
		for(int i = h[u]; ~i; i = ne[i]){
			int j = e[i];
			dfs(j);
			sz[u] += sz[j];
		}
	}

	inline int insert(std::string &s, int x){//插入字符 和插入的是第几个字符
		int p = 0;
		for(char &ch : s){
			int u = ch - 'a';
			if(!tr[p][u]){
				tr[p][u] = ++ idx;
			}
			p = tr[p][u];
		}
		id[p] = x;//标记第x个字符的结尾
		reid[x] = p;
		cnt[p] ++;
		son[p] = 1;
		mx[p] = std::max(mx[p], (int)s.length());
		return p;
	}
	
	inline void build(){//建立ac自动机
		int p = 0;
		int hh = 0,tt = -1;
		for(int i = 0; i < 26; i ++)
			if(tr[p][i])	q[++ tt] = tr[p][i];
		while(hh <= tt){
			int tq = q[hh ++];
			for(int i = 0; i < 26; i ++){
				int j = tr[tq][i];
				if(!tr[tq][i]){
					tr[tq][i] = tr[nxt[tq]][i];
				}
				else{
					q[++ tt] = tr[tq][i];
					nxt[j] = tr[nxt[tq]][i];
					if(cnt[nxt[j]])  pre[j] = nxt[j];
                   	else pre[j] = pre[nxt[j]];
					son[j] |= son[nxt[j]];//标记能到达终止节点路径上的所有点
				}
			}
		}
	}

	//ac自动机fail树上建dfs序的建边(记得inith)
	inline void failtree(){
		memset(h, -1, sizeof h);
		for(int i = 1; i <= idx; i ++)	add(nxt[i], i);
		dfs(0);
	}

	inline int query(std::string &s){
		int res = 0, j = 0;
		for(char &ch : s){
			int u = ch - '0';
			j = tr[j][u];
			int p = u;
			while(p){
				res += cnt[p];
				p = nxt[p];
			}
		}
		return res;
	}	

}acam;

std::string str[N];

void solve(){
	std::cin >> n >> m;
	auto &root = HST.root;
	const auto &tdl = acam.tdl;
	const auto &sz = acam.sz, &dfn = acam.dfn, &id = acam.reid;
	for(int i = 1; i <= n; i ++){
		std::cin >> str[i];
		acam.insert(str[i], i);
	}
	acam.build();
	acam.failtree();
	HST.build(1, tdl);
	for(int i = 1; i <= n; i ++){
		int p = 0;
		for(int j = 0; str[i][j]; j ++){
			p = acam.tr[p][str[i][j] - 'a'];
			if(!j)	root[i] = HST.insert(root[i - 1], 1, tdl, dfn[p], 1);
			else root[i] = HST.insert(root[i], 1, tdl, dfn[p], 1);
		}
	}
	
	while(m --){
		int L, R, K;
		std::cin >> L >> R >> K;
		L --;
		K = id[K];
		std::cout << HST.query(root[L], root[R], 1, tdl, dfn[K], dfn[K] + sz[K] - 1) << '\n';
	}
}

int AC{
   	HYS
    
//	std::cin >> _;
	while(_ --)
        solve();

    return 0;
}