QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#79558 | #5014. 复读程度 | NATURAL6 | 0 | 1514ms | 604232kb | C++14 | 9.2kb | 2023-02-20 13:36:30 | 2023-02-20 13:36:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 200010
inline unsigned long long qread()
{
unsigned long long a=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){(a*=10)+=(ch^48);ch=getchar();}
return a*f;
}
int n,m,cx,xk,L,R,tot,occ[N],rt[2][N];
int cl=400,l,r,c[N];
unsigned long long wl[N],wr[N],ans[N],vr[N],vl[N];
char ch[N];
struct node
{
int x,y,id;
unsigned long long val;
};
bool operator<(const node x,const node y){return x.x==y.x?x.y<y.y:x.x<y.x;}
bool operator>(const node x,const node y){return x.x==y.x?x.y>y.y:x.x>y.x;}
inline bool cmp(node x,node y){return c[x.x]==c[y.x]?((c[x.x]&1)?x.y<y.y:x.y>y.y):x.x<y.x;}
vector<node>q,Q[2][N];
struct E
{
int tot,head[N],nex[N],t[N];
inline void adde(int x,int y)
{
t[++tot]=y;
nex[tot]=head[x];
head[x]=tot;
return ;
}
};
struct BIT
{
int tim,tag[N];
unsigned long long val[N];
inline int lowbit(int x){return x&-x;}
inline void adds(int x,unsigned long long y)
{
for(;x<=n*2;x+=lowbit(x))
{
(tag[x]!=tim)&&(tag[x]=tim,val[x]=0);
val[x]+=y;
}
}
unsigned long long ask(int x)
{
unsigned long long an=0;
for(;x;x-=lowbit(x))an+=tag[x]==tim?val[x]:0;
return an;
}
}bit;
struct sam
{
int ps,p,link[N],len[N],tot,cnt,T,siz[N];
int rg[N],ed[N],c[N],sz[N],pos[N],clen[N];
int s[N],top[N],dfn[N],rk[N],tag[N];
vector<int>vec[N];
map<char,int>ch[N];
E e;
inline void addc(char c)
{
len[ps=++cnt]=len[p=T]+1,siz[T=ps]=1;
while(p&&!ch[p][c])ch[p][c]=ps,p=link[p];
if(!p)return link[ps]=1,void();
cx=ch[p][c];
if(len[p]+1==len[cx])return link[ps]=cx,void();
xk=++cnt;
len[xk]=len[p]+1;
ch[xk]=ch[cx];
rg[xk]=rg[cx];
link[xk]=link[cx];
while(p&&ch[p][c]==cx)ch[p][c]=xk,p=link[p];
link[cx]=link[ps]=xk;
return ;
}
inline void dfs(int rt)
{
dfn[rt]=++tot;
rk[tot]=rt;
if(s[rt])top[s[rt]]=top[rt],dfs(s[rt]);
for(int i=e.head[rt];i;i=e.nex[i])
{
if(e.t[i]==s[rt])continue;
top[e.t[i]]=e.t[i];
dfs(e.t[i]);
}
return ;
}
inline void init()
{
for(int i=1;i<=cnt;++i)++c[len[i]],sz[i]=1;
for(int i=1;i<=n;++i)c[i]+=c[i-1];
for(int i=cnt;i>=1;--i)pos[c[len[i]]--]=i;
for(int i=cnt;i>=2;--i)
{
cx=pos[i];
e.adde(link[cx],cx);
siz[link[cx]]+=siz[cx];
sz[link[cx]]+=sz[cx];
clen[cx]=len[cx]-len[link[cx]];
if(sz[cx]>sz[s[link[cx]]])s[link[cx]]=cx;
}
top[1]=1;dfs(1);
return ;
}
inline int f(int id,int le)
{
while(len[link[top[id]]]>=le)id=link[top[id]];
int l=dfn[top[id]],r=dfn[id],w=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(len[rk[mid]]>=le)w=mid,r=mid-1;
else l=mid+1;
}
return rk[w];
}
}sa[2];
struct C
{
int cs,st[N],ed[N],c[N];
unsigned long long s[N],val[N],tag[N];
inline void init()
{
for(int i=1;i<=n*2;++i)c[i]=(i-1)/cl+1,ed[c[i]]=i;
for(int i=n*2;i;--i)st[c[i]]=i;
return ;
}
inline void clear()
{
for(int i=1;i<=n*2;++i)val[i]=s[i]=0;
for(int i=1;i<=m;++i)tag[i]=0;
return ;
}
inline void adds(int l,int r,unsigned long long v)
{
if(c[l]==c[r])
{
for(int i=l;i<=r;i++) val[i]+=v*s[i];
return ;
}
for(int i=l;i<=ed[c[l]];++i) val[i]+=v*s[i];
for(int i=c[l]+1;i<=c[r]-1;++i) tag[i]+=v;
for(int i=st[c[r]];i<=r;++i) val[i]+=v*s[i];
return ;
}
inline unsigned long long q(int x){return val[x]+tag[c[x]]*s[x];}
}fk;
struct NODE
{
int cnt,s[N<<1],sum[N],L,R,zz;
unsigned long long val[N<<2];
vector<node>qq[2][N];
inline void solve()
{
for(int k=0;k<=1;++k)
{
cx=1;
fk.clear();
for(int i=1;i<=tot;i++)
{
sum[i]=cx;
cx+=sa[k].vec[i].size();
for(int j=0;j<sa[k].vec[i].size();j++)fk.s[sum[i]+j]=(!k)?vr[sa[k].vec[i][j]]:vl[sa[k].vec[i][j]];
}
for(int i=1;i<=sa[k^1].cnt;++i)
{
xk=sa[k^1].rk[i],zz=sa[k^1].tag[xk];
L=sa[k].vec[zz].size()-sa[k^1].clen[xk]+sum[zz],R=sa[k].vec[zz].size()-1+sum[zz];
fk.adds(L,R,occ[zz]*(!k?vl[xk]:vr[xk]));
for(node r:qq[k][i])
{
for(int j=r.x;j<=r.y;++j)
{
int v=sa[k].rk[j],dis=0;
int bo=sa[k].tag[v];
dis=sa[k].len[rt[k][bo]]-sa[k].len[v];
val[r.id]+=r.val*fk.q(sum[bo]+sa[k].vec[bo].size()-dis-1);
}
}
}
}
return ;
}
inline void work()
{
sort(q.begin(),q.end(),cmp);
for(int i=0;i<(int)q.size();++i)
{
if(l<q[i].x)qq[0][r].push_back((node){l+1,q[i].x,++cnt,1}),l=q[i].x;
if(r<q[i].y)qq[1][l].push_back((node){r+1,q[i].y,++cnt,1}),r=q[i].y;
if(l>q[i].x)qq[0][r].push_back((node){q[i].x+1,l,++cnt,(unsigned long long)-1}),l=q[i].x;
if(r>q[i].y)qq[1][l].push_back((node){q[i].y+1,r,++cnt,(unsigned long long)-1}),r=q[i].y;
s[i]=cnt;
}
fk.init();
solve();
for(int i=1;i<=cnt;++i)val[i]+=val[i-1];
for(int i=0;i<q.size();++i)ans[q[i].id]+=q[i].val*val[s[i]];
}
}fxk;
int main()
{
//freopen("b.in","r",stdin);
//freopen("b.out","w",stdout);
n=qread();
m=qread();
cin>>(ch+1);
for(int i=1;i<=n;++i)wl[i]=qread();
for(int i=1;i<=n;++i)wr[i]=qread();
sa[0].T=sa[1].T=sa[0].cnt=sa[1].cnt=1;
for(int i=1;i<=n;i++)sa[0].addc(ch[i]),sa[0].rg[sa[0].ed[i]=sa[0].T]=i;
for(int i=n;i>=1;i--)sa[1].addc(ch[i]),sa[1].rg[sa[1].ed[i]=sa[1].T]=i;
sa[0].init(),sa[1].init();
for(int i=2;i<=sa[0].cnt;++i)
{
cx=sa[0].pos[i];
L=sa[0].rg[cx]-sa[0].len[cx]+1,R=sa[0].rg[cx];
xk=sa[1].f(sa[1].ed[L],R-L+1);
if(sa[1].len[xk]==R-L+1)
{
sa[0].tag[cx]=sa[1].tag[xk]=++tot;
rt[0][tot]=cx,rt[1][tot]=xk;
occ[tot]=sa[0].siz[cx];
}
}
for(int i=sa[0].cnt;i>=2;--i)
{
cx=sa[0].pos[i];
if(!sa[0].tag[cx])for(char chr='a';chr<='z';++chr)sa[0].ch[cx][chr]&&(sa[0].tag[cx]=sa[0].tag[sa[0].ch[cx][chr]]);
}
for(int i=sa[1].cnt;i>=2;--i)
{
cx=sa[1].pos[i];
if(!sa[1].tag[cx])for(char chr='a';chr<='z';++chr)sa[1].ch[cx][chr]&&(sa[1].tag[cx]=sa[1].tag[sa[1].ch[cx][chr]]);
}
for(int i=sa[0].cnt;i>=2;--i)
{
cx=sa[0].pos[i];
sa[0].vec[sa[0].tag[cx]].push_back(cx);
}
for(int i=sa[1].cnt;i>=2;--i)
{
cx=sa[1].pos[i];
sa[1].vec[sa[1].tag[cx]].push_back(cx);
}
for(int i=tot;i;--i)
{
for(int j:sa[0].vec[i])
{
for(int k=sa[0].e.head[j];k;k=sa[0].e.nex[k])vr[j]+=vr[sa[0].e.t[k]];
if(sa[0].len[j]==sa[0].rg[j])vr[j]+=wr[sa[0].rg[j]];
}
for(int j:sa[1].vec[i])
{
for(int k=sa[1].e.head[j];k;k=sa[1].e.nex[k])vl[j]+=vl[sa[1].e.t[k]];
if(sa[1].len[j]==n-sa[1].rg[j]+1)vl[j]+=wl[sa[1].rg[j]];
}
}
for(int i=1,x,X,y,Y;i<=m;++i)
{
x=qread();
y=qread();
X=qread();
Y=qread();
cx=sa[0].f(sa[0].ed[Y],Y-X+1);
xk=sa[1].f(sa[1].ed[x],y-x+1);
int l1=sa[0].dfn[cx],r1=sa[0].dfn[cx]+sa[0].sz[cx]-1,l2=sa[1].dfn[xk],r2=sa[1].dfn[xk]+sa[1].sz[xk]-1;
if(sa[0].tag[cx]==sa[1].tag[xk])
{
int zz=sa[0].len[rt[0][sa[1].tag[xk]]]-(sa[1].rg[xk]-sa[1].rg[rt[1][sa[1].tag[xk]]]+sa[0].rg[rt[0][sa[1].tag[xk]]]-sa[0].rg[cx]);
if(sa[0].clen[cx]-1>=sa[1].rg[xk]-sa[1].rg[rt[1][sa[1].tag[xk]]]&&(y-x+1>zz||Y-X+1>zz))ans[i]-=occ[sa[1].tag[xk]]*vl[xk]*vr[cx];
}
else
{
Q[0][sa[0].tag[cx]].push_back((node){sa[0].len[cx]-(Y-X),r2,i,-vr[cx]});
Q[0][sa[0].tag[cx]].push_back((node){sa[0].clen[cx],r2,i,vr[cx]});
Q[0][sa[0].tag[cx]].push_back((node){sa[0].len[cx]-(Y-X),l2-1,i,vr[cx]});
Q[0][sa[0].tag[cx]].push_back((node){sa[0].clen[cx],l2-1,i,-vr[cx]});
Q[1][sa[1].tag[xk]].push_back((node){sa[1].len[xk]-(y-x),r1,i,-vl[xk]});
Q[1][sa[1].tag[xk]].push_back((node){sa[1].clen[xk],r1,i,vl[xk]});
Q[1][sa[1].tag[xk]].push_back((node){sa[1].len[xk]-(y-x),l1-1,i,vl[xk]});
Q[1][sa[1].tag[xk]].push_back((node){sa[1].clen[xk],l1-1,i,-vl[xk]});
}
q.push_back((node){r1,r2,i,1});
q.push_back((node){r1,l2-1,i,(unsigned long long)-1});
q.push_back((node){l1-1,r2,i,(unsigned long long)-1});
q.push_back((node){l1-1,l2-1,i,1});
}
for(int i=1;i<=tot;++i)
{
for(int k=0;k<=1;++k)
{
++bit.tim;
sort(Q[k][i].begin(),Q[k][i].end());
cx=Q[k][i].size()-1;
while(cx>=0&&Q[k][i][cx].x==sa[k^1].vec[i].size())--cx;
for(int j=0;j<sa[k^1].vec[i].size();++j)
{
xk=sa[k^1].vec[i][j];
bit.adds(sa[k^1].dfn[xk],k==0?vl[xk]:vr[xk]);
while(cx>=0&&sa[k^1].vec[i].size()-j-1==Q[k][i][cx].x)
{
node S=Q[k][i][cx];
ans[S.id]+=occ[i]*S.val*bit.ask(S.y);
--cx;
}
}
}
}
for(int i=1;i<=n*2;++i)c[i]=(i-1)/cl+1;
fxk.work();
for(int i=1;i<=m;++i)printf("%llu\n",ans[i]);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 12ms
memory: 51840kb
input:
500 500 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
13577243068842929935 12476711121268294326 16743946924230018276 15363331807929279863 16931884767229885935 12888898522090720985 4004249951341603293 8171891678984586116 16620200389275031673 10378469268004772228 2864035159824145807 561254583489766117 12029631008578292736 883762801052165866 6926760179853...
result:
wrong answer 1st lines differ - expected: '15720454042420499810', found: '13577243068842929935'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 1514ms
memory: 604232kb
input:
100000 100000 zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
4758451521627630019 6317977285640306202 5625540601279087957 10258390208398592090 5601856252243435601 2241842638676820870 16653145506369526413 14073055445940096863 16691573597446886581 3784526005034855261 11538155476722747377 16632077405559968177 15553088833262702794 5632801252358379773 1460992355794...
result:
wrong answer 1st lines differ - expected: '16102224067619618967', found: '4758451521627630019'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%