CF587F Duff is Mad 题解

大佬教程收集整理的这篇文章主要介绍了CF587F Duff is Mad 题解，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

难搞的题啊……做了一下午

使用到了主席树，AC自动机，根号分治，树状数组等算法及技巧。

可以想到一个比较明显的做法，就是建立出AC自动机，然后将fail树的dfs序处理出来，建立线段树。对于选取的 (s[l,r]) 这些字符串，将结束点的子树加一，然后枚举 s[k] 在线段树里面查询答案。

发现这样的话复杂度可以达到优秀的 (n^2logn) 。考虑使用主席树，可以降到 (n^2logn) （啥也没变啊喂！）

考虑根号分治，对于 (len_k <= T) 的部分，使用上面的算法可以做到 (Tlogn) 的单次查询。

对于 (len_k > T) 的部分，我们首先处理一个数组 (dp[i][j]) 表示在 (s_i) 中有多少个 (s_j) 。预处理出所有 (s_i > T) 的 (dp[i]) 。

我们枚举每一个长串，标记串上每一个点，然后对于每一个终止点，在其fail树中的子树里进行查询。

#include <cstdio>
#include <cString>
#include <algorithm>
#include <vector>
#include <queue>

#define mid (l+r>>1)
using namespace std;

int read()
{
	int a = 0,x = 1;char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') x = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9') {a = a*10 + ch-'0';ch = getchar();}
	return a*x;
}
const int n=1e5+7,T=228;
int n,q,m[n];unsigned s[N/T+7][n];
char S[n];
vector<int>arr[n],g;
int ch[n][26],tot=1,cnt,pos[n],nxt[n];
int add(char *s,vector<int>&a)
{
	int t = 1,len = strlen(s+1);
	for(int i = 1;i <= len;i ++) {
		if(!ch[t][s[i]-'a']) ch[t][s[i]-'a'] = ++tot;
		t = ch[t][s[i]-'a'];a.push_BACk(t);
	}
	return t;
}
void get_fail()
{
	for(int i = 0;i < 26;i ++) ch[0][i] = 1;
	queue<int>q;q.push(1);
	while(!q.empty()) {
		int u = q.front();q.pop();
		for(int i = 0;i < 26;i ++) {
			if(!ch[u][i]) ch[u][i] = ch[nxt[u]][i];
			else {
				nxt[ch[u][i]] = ch[nxt[u]][i];
				q.push(ch[u][i]);
			}
		}
	}
}

int head[n],go[n],nt[n];
void add(int u,int v)
{
	go[++cnt] = v;
	nt[cnt] = head[u];
	head[u] = cnt;
}

int dfn[n],siz[n];
void dfs(int u)
{
	dfn[u] = ++cnt,siz[u] = 1;
	for(int e = head[u];e;e = nt[e]){
		dfs(go[e]);siz[u] += siz[go[e]];
	}
}

int tre[N<<5],tag[N<<5],rt[n],ls[N<<5],rs[N<<5];
void push_down(int root,int l,int r)
{
	tag[root<<1|1] += tag[root],tag[root<<1] += tag[root];
	tre[root<<1] += (mid-l+1)*tag[root],tre[root<<1|1] += (r-mid)*tag[root];
	tag[root] = 0;
}

void modify(int root,int l,int r,int ql,int qr,int X)
{
	if(l >= ql && r <= qr) {tag[root] += x,tre[root] += (r-l+1)*x;return ;}
	if(l > qr || r < ql) return ;
	push_down(root,l,r);
	modify(root<<1,l,mid,ql,qr,X);modify(root<<1|1,mid+1,r,ql,qr,X);
	tre[root] = tre[root<<1|1] + tre[root<<1];
}
int query(int root,int l,int r,int ql,int qr)
{
	if(l >= ql && r <= qr) return tre[root];
	if(l > qr || r < ql) return 0;
	push_down(root,l,r);
	return query(root<<1,l,mid,ql,qr) + query(root<<1|1,mid+1,r,ql,qr);
}



void modify(int r1,int &r2,int l,int r,int ql,int qr,int X)
{
	if(l > qr || r < ql) return ;
	r2 = ++cnt;ls[r2] = ls[r1],rs[r2] = rs[r1];tre[r2] = tre[r1];tag[r2] = tag[r1];
	if(l >= ql && r <= qr) {tre[r2] += (r-l+1)*x,tag[r2] += x;return ;}
	modify(ls[r1],ls[r2],l,mid,ql,qr,X);modify(rs[r1],rs[r2],mid+1,r,ql,qr,X);
	tre[r2] += x*(min(r,qr)-max(l,ql)+1);
}

int query(int r1,int r2,int l,int r,int ql,int qr)
{
	if(l >= ql && r <= qr) return tre[r2]-tre[r1];
	if(l > qr || r < ql) return 0;
	return (min(qr,r)-max(ql,l)+1)*(tag[r2]-tag[r1]) + query(ls[r1],ls[r2],l,mid,ql,qr) + query(rs[r1],rs[r2],mid+1,r,ql,qr);
}
int id[n],B[n];
void add1(int p,int a,int *B)
{
	for(int i = p;i <= tot;i += i&-i) B[i] += a;
}
int query(int p,int *B)
{
	int ret = 0;
	for(int i = p;i >=1;i -= i&-i) ret += B[i];
	return ret;
}

int main()
{
	// freopen("random.in","r"/,stdin);
	// freopen("sol.out","w",stdout);
	n = read(),q = read();
	for(int i = 1;i <= n;i ++) {
		scanf("%s",S+1);
		pos[i] = add(S,arr[i]);m[i] = strlen(S+1);
		if(m[i] >= T) g.push_BACk(i),id[i] = g.size();
	}
	get_fail();
	for(int i = 2;i <= tot;i ++) add(nxt[i],i);
	cnt = 0;dfs(1);cnt=0;
	for(int o:g) {
		++cnt;
		for(auto u:arr[o]) {
			add1(dfn[u],1,B);
		}
		for(int i = 1;i <= n;i ++) {
			s[cnt][i] = s[cnt][i-1] + query(dfn[pos[i]]+siz[pos[i]]-1,B) - query(dfn[pos[i]]-1,B);
		}
		for(auto u:arr[o]) {
			add1(dfn[u],-1,B);
		}
	}
	cnt = 0;for(int i = 1;i <= n;i ++) {
		modify(rt[i-1],rt[i],1,tot,dfn[pos[i]],dfn[pos[i]]+siz[pos[i]]-1,1);
	}
	for(int i = 1;i <= q;i ++) {
		int l = read(),r = read(),k = read();
		if(m[k] >= T) {
			printf("%un",s[id[k]][r]-s[id[k]][l-1]);
		} else {
			int ret = 0;
			for(int x:arr[k]) {
				int qwq = query(rt[l-1],rt[r],1,tot,dfn[x],dfn[x]);
				ret += qwq;
			}
			printf("%dn",ret);
		}
	}

	return 0;
}

大佬总结

以上是大佬教程为你收集整理的CF587F Duff is Mad 题解全部内容，希望文章能够帮你解决CF587F Duff is Mad 题解所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。