【Codeforces】 CF587F Duff is Mad

#include 
using namespace std;
typedef long long LL;
const int N=100100,MAXB=295;
struct Node{ int k,neg,id;};
int n,q,lenth[N];
string str[N];
int tr[N][26],idx,ne[N],ed[N];
int bigidx,rv[N];
int L[N],R[N],dfnidx=-1;
int e[N],NE[N],h[N],IDX;
vector<Node> query[N];
int que[N],sum[N];
LL ans[N],pref[MAXB][N];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
void add(int x,int y){ e[IDX]=y,NE[IDX]=h[x],h[x]=IDX++;}
int insert(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		if(!tr[p][c]) tr[p][c]=++idx;
		p=tr[p][c];
	}
	return p;
}
void build_ACAM(){
	int hh=0,tt=-1;
	for(int i=0;i<26;i++) if(tr[0][i]) que[++tt]=tr[0][i];
	while(hh<=tt){
		int u=que[hh++];
		for(int i=0;i<26;i++){
			int v=tr[u][i];
			if(!v) tr[u][i]=tr[ne[u]][i];
			else ne[v]=tr[ne[u]][i],que[++tt]=v;
		}
	}
}
void dfs(int u){
	for(int i=h[u];~i;i=NE[i]) dfs(e[i]),sum[u]+=sum[e[i]];
}
void dfs_dfn(int u){
	L[u]=++dfnidx;
	for(int i=h[u];~i;i=NE[i]) dfs_dfn(e[i]);
	R[u]=dfnidx;
}
struct BLOCK{
	int LIM,pos[N],tag1[N],tag2[N];
	void build(){
		LIM=sqrt(idx);
		for(int i=1;i<=idx;i++) pos[i]=(i-1)/LIM+1;
	}
	void add(int l,int r){
		if(pos[l]==pos[r]) for(int i=l;i<=r;i++) tag1[i]++;
		else{
			int i=l,j=r;
			while(pos[i]==pos[l]) tag1[i]++,i++;
			while(pos[j]==pos[r]) tag1[j]++,j--;
			for(int k=pos[i];k<=pos[j];k++) tag2[k]++;
		}
	}
	int ask(int x){ return tag1[x]+tag2[pos[x]];}
}block;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>str[i],lenth[i]=str[i].size();
	int m=0;
	for(int i=1;i<=n;i++) m+=lenth[i];
	for(int i=1;i<=n;i++) ed[i]=insert(str[i]);
	build_ACAM();
	memset(h,-1,sizeof(h));
	for(int i=1;i<=idx;i++) add(ne[i],i);
	int B=290;
	for(int i=1;i<=n;i++)
		if(lenth[i]>B){
			rv[i]=++bigidx;
			for(int j=0;j<=idx;j++) sum[j]=0;
            int p=0;
            for(int j=0;j<str[i].size();j++){
                p=tr[p][str[i][j]-'a'];
                sum[p]++;
            }
			dfs(0);
			LL res=0;
			for(int j=1;j<=n;j++) res+=sum[ed[j]],pref[bigidx][j]=res;
		}
	for(int i=1;i<=q;i++){
		int l=read(),r=read(),k=read();
		if(lenth[k]>B) k=rv[k],ans[i]=pref[k][r]-pref[k][l-1];
		else query[r].push_back({k,1,i}),query[l-1].push_back({k,-1,i});
	}
	dfs_dfn(0);
	block.build();
	for(int i=1;i<=n;i++){
        block.add(L[ed[i]],R[ed[i]]);
		for(auto j:query[i]){
            int x=j.k,p=0;
            for(int k=0;k<str[x].size();k++){
                p=tr[p][str[x][k]-'a'];
                ans[j.id]+=j.neg*block.ask(L[p]);
            }
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112