社区讨论

蒟蒻真的调不出来了,求大佬帮助

CF666EForensic Examination参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7w2v10
此快照首次捕获于
2025/11/21 04:33
4 个月前
此快照最后确认于
2025/11/21 04:33
4 个月前
查看原帖
代码如下:
CPP
#include<bits/stdc++.h>
#define lson tr[now].l
#define rson tr[now].r
#define hi puts("hi");
using namespace std;

int qq,m;
char s1[500050],s2[50050];

struct que
{
	int l,r,len,rr,ans1,ans2,kd;
}qu[500050];

int cmp(que a,que b)
{
	if(a.rr==b.rr)
	{
		return a.len>b.len;
	}
	return a.rr<b.rr;
}

int cmp2(que a,que b)
{
	return a.kd<b.kd;
}

struct SAM 
{
	struct point
	{
		int son[26],fa,len;
	}t[100010];

	struct tree
	{
		int l,r,sum,pos,val;
	}tr[10000000];

	int last=1,cnt=1,rt[200020];
	int tot=0,pre=1;
	int fa[200020][19];

	vector<int> g[200010],qv[200010];

	int push_up(int now)
	{
		if(tr[lson].sum<tr[rson].sum)
		{
			tr[now].sum=tr[rson].sum;
			tr[now].pos=tr[rson].pos;
			tr[now].val=tr[rson].val;
		}
		else
		{
			tr[now].sum=tr[lson].sum;
			tr[now].pos=tr[lson].pos;
			tr[now].val=tr[lson].val;
		}
	}

	int insert(int &now,int l,int r,int pos,int val)
	{
		if(!now)
		{
			now=++tot;
		}
		if(l==r)
		{
			tr[now].sum+=val;
			tr[now].pos=now;
			tr[now].val=l;
			return 0;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
		{
			insert(lson,l,mid,pos,val);
		}
		else
		{
			insert(rson,mid+1,r,pos,val);
		}
		push_up(now);
	}

	int query(int now,int l,int r,int ll,int rr)
	{
		if(ll<=l&&r<=rr) 
		{
			return tr[now].pos;
		}
		int mid=(l+r)>>1;
		if(rr<=mid)
		{
			return query(lson,l,mid,ll,rr);
		}
		else
		{
			if(mid<ll)
			{
				return query(rson,mid+1,r,ll,rr);
			}
			else
			{
				register int lpos=query(lson,l,mid,ll,mid);
				register int rpos=query(rson,mid+1,r,mid+1,rr);
				if(tr[lpos].sum<tr[rpos].sum) return rpos;
				else return lpos;
			}
		}
	}

	int merge(int a,int b,int l,int r)
	{
		if(!a) return b;
		if(!b) return a;
		if(l==r)
		{
			tr[a].sum+=tr[b].sum;
			tr[a].pos=a;
			tr[a].val=l;
			return a;
		}
		int mid=(l+r)>>1;
		tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
		tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
		push_up(a);
		return a;
	}

	void add(int c,int num)
	{
		int p=last;
		if(t[p].son[c]&&t[p].len+1==t[t[p].son[c]].len)
		{
			last=t[p].son[c];
			insert(rt[last],1,m,num,1);
			return ;
		}
		int np=++cnt;
		t[np].len=t[p].len+1;
		insert(rt[np],1,m,num,1);
		while(p&&!t[p].son[c])
		{
			t[p].son[c]=np;
			p=t[p].fa;
		}
		if(!p)
		{
			t[np].fa=1;
		}
		else
		{
			int q=t[p].son[c],nq;
			if(t[q].len==t[p].len+1)
			{
				t[np].fa=q;
			}
			else
			{
				nq=++cnt;
				t[nq]=t[q];
				t[nq].len=t[p].len+1;
				t[np].fa=t[q].fa=nq;
				while(p&&t[p].son[c]==q)
				{
					t[p].son[c]=nq;
					p=t[p].fa;
				}
			}
		}
		last=np;
	}

	void dfs(int now)
	{
		fa[now][0]=t[now].fa;
		for(int i=1;i<=18;i++)
		{
			fa[now][i]=fa[fa[now][i-1]][i-1];
		}
		for(int i=0;i<g[now].size();i++)
		{
			dfs(g[now][i]);
		}
	}

	void sam_build(int kd)
	{
		scanf("%s",s2);
		int len=strlen(s2);
		last=1;
		for(int i=0;i<len;i++)
		{
			add(s2[i]-'a',kd);
		}
	}

	void dfs2(int now)
	{
		for(int i=0;i<g[now].size();i++)
		{
			dfs2(g[now][i]);
			merge(rt[now],rt[g[now][i]],1,m);
		}
		for(int i=0;i<qv[now].size();i++)
		{
			int pos=query(rt[now],1,m,qu[qv[now][i]].l,qu[qv[now][i]].r);
			qu[qv[now][i]].ans1=tr[pos].val;
			qu[qv[now][i]].ans2=tr[pos].sum;
		}
	}

	void solve()
	{
		scanf("%s",s1);
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			sam_build(i);
		}
		scanf("%d",&qq);
		int tmp;
		for(int i=1;i<=qq;i++)
		{
			scanf("%d%d%d%d",&qu[i].l,&qu[i].r,&tmp,&qu[i].rr);
			qu[i].len=qu[i].rr-tmp+1;
			qu[i].kd=i;
		}
		sort(qu+1,qu+qq+1,cmp);
		for(int i=1;i<=cnt;i++) g[t[i].fa].push_back(i);
		for(int i=1;i<=cnt;i++) if(!rt[i]) rt[i]=++tot;
		dfs(1);
		int len=strlen(s1);
		int now=0;
		for(int i=1;i<=qq;i++)
		{
			if(qu[i].rr!=qu[i-1].rr)
			{
				for(int j=qu[i-1].rr;j<=qu[i].rr-1;j++)
				{
					int c=s1[j]-'a';
					while(pre)
					{
						if(t[pre].son[c]) break;
						else pre=t[pre].fa;
					}
					pre=t[pre].son[c];
				}
				now=pre;
			}
			if(!now||t[now].len<qu[i].len)
			{
				continue;
			}
			else
			{
				for(int j=18;j>=0;j--)
				{
					if(t[fa[now][j]].len>=qu[i].len)
					{
						now=fa[now][j];
					}
				}
				qv[now].push_back(i);
			}
		}
		dfs2(1);
		sort(qu+1,qu+qq+1,cmp2);
		for(int i=1;i<=qq;i++)
		{
			if(!qu[i].ans2)
			{
				printf("%d 0\n",qu[i].l);
			}
			else
			{
				printf("%d %d\n",qu[i].ans1,qu[i].ans2);
			}
		}
	}
}sam;

int main()
{
	sam.solve();
}

回复

2 条回复,欢迎继续交流。

正在加载回复...