社区讨论
蒟蒻真的调不出来了,求大佬帮助
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 条回复,欢迎继续交流。
正在加载回复...