QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#79951 | #5014. 复读程度 | NATURAL6 | 0 | 11ms | 51828kb | C++14 | 9.0kb | 2023-02-21 13:39:49 | 2023-02-21 13:39:51 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename sa> bool chkmax(sa &x,sa y){return x<y?x=y,1:0;}
template<typename sa> bool chkmin(sa &x,sa y){return x>y?x=y,1:0;}
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;
}
struct node{
int x,y,id; ull w;
node(int x=0,int y=0,int id=0,ull w=0):x(x),y(y),id(id),w(w){}
bool operator<(const node c)const{return x==c.x?y<c.y:x<c.x;}
};
const int B=400;
int n,m,q,tot;
int occ[200005],rt[2][200005];
ull ans[100005],wl[100005],wr[100005],vl[200005],vr[200005];
char s[100005];
vector<node> qry;
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 ;
}
};
namespace bit{
int tim,tag[N];
unsigned long long val[N];
inline int lowbit(int x){return x&-x;}
inline void add(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;
}
}
struct sam
{
int cx,xk,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];
vector<node> subqry[2][200005];
namespace blo{
int m;
int lf[1005],rg[1005],bl[200005];
ull a[200005],val[200005],tag[1005];
void init(){
for(int i=1;i<=n*2;++i)bl[i]=(i-1)/B+1,rg[bl[i]]=i;
for(int i=n*2;i;--i)lf[bl[i]]=i;
}
void clear(){
for(int i=1;i<=n+n;i++) val[i]=a[i]=0;
for(int i=1;i<=m;i++) tag[i]=0;
}
void add(int l,int r,ull c){
int lb=bl[l],rb=bl[r];
if(lb==rb){
for(int i=l;i<=r;i++) val[i]+=c*a[i];
return;
}
for(int i=l;i<=rg[lb];i++) val[i]+=c*a[i];
for(int i=lf[rb];i<=r;i++) val[i]+=c*a[i];
for(int i=lb+1;i<=rb-1;i++) tag[i]+=c;
}
ull ask(int x){
return val[x]+tag[bl[x]]*a[x];
}
}
namespace sub1{
int cnt;
int plq[400005],st[200005];
ull val[800005];
vector<node> qry2[2][200005];
void solve(){
for(int l=0;l<2;l++){
int now=1;
blo::clear();
for(int i=1;i<=tot;i++){
st[i]=now;
now+=sa[l].vec[i].size();
for(int j=0;j<sa[l].vec[i].size();j++) blo::a[st[i]+j]=(!l)?vr[sa[l].vec[i][j]]:vl[sa[l].vec[i][j]];
}
for(int i=1;i<=sa[l^1].cnt;i++){
int u=sa[l^1].rk[i];
int bel=sa[l^1].tag[u];
int L=sa[l].vec[bel].size()-sa[l^1].clen[u],R=sa[l].vec[bel].size()-1;
L+=st[bel],R+=st[bel];
blo::add(L,R,occ[bel]*(l==0?vl[u]:vr[u]));
for(auto r:qry2[l][i]){
for(int j=r.x;j<=r.y;j++){
int v=sa[l].rk[j],dis=0;
int bo=sa[l].tag[v];
dis=sa[l].len[rt[l][bo]]-sa[l].len[v];
val[r.id]+=r.w*blo::ask(st[bo]+sa[l].vec[bo].size()-dis-1);
}
}
}
}
}
void work(){
sort(qry.begin(),qry.end(),[&](node x,node y){
if((x.x-1)/B==(y.x-1)/B) return (x.x-1)/B%2==0?x.y<y.y:x.y>y.y;
return (x.x-1)/B<(y.x-1)/B;
});
int nx=0,ny=0;
for(int i=0;i<qry.size();i++){
node r=qry[i];
if(nx<r.x) qry2[0][ny].pb(node(nx+1,r.x,++cnt,1)),nx=r.x;
if(ny<r.y) qry2[1][nx].pb(node(ny+1,r.y,++cnt,1)),ny=r.y;
if(nx>r.x) qry2[0][ny].pb(node(r.x+1,nx,++cnt,-1)),nx=r.x;
if(ny>r.y) qry2[1][nx].pb(node(r.y+1,ny,++cnt,-1)),ny=r.y;
plq[i]=cnt;
}
blo::init();
solve();
for(int i=1;i<=cnt;i++) val[i]+=val[i-1];
for(int i=0;i<qry.size();i++) ans[qry[i].id]+=qry[i].w*val[plq[i]];
}
}
int main(){
n=qread(); q=qread();
scanf("%s",s+1);
for(int i=1;i<=n;i++) wl[i]=qread();
for(int i=1;i<=n;i++) wr[i]=qread();
sa[0].cnt=sa[0].T=sa[1].cnt=sa[1].T=1;
for(int i=1;i<=n;i++) sa[0].addc(s[i]),sa[0].rg[sa[0].ed[i]=sa[0].T]=i;
for(int i=n;i>=1;i--) sa[1].addc(s[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++){
int u=sa[0].pos[i];
int L=sa[0].rg[u]-sa[0].len[u]+1,R=sa[0].rg[u];
int id=sa[1].f(sa[1].ed[L],R-L+1);
if(sa[1].len[id]==R-L+1){
sa[0].tag[u]=sa[1].tag[id]=++tot;
rt[0][tot]=u,rt[1][tot]=id;
occ[tot]=sa[0].siz[u];
}
}
for(int i=sa[0].cnt;i>=2;--i)
{
int 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)
{
int 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=2;i<=sa[0].cnt;--i)
{
int cx=sa[0].pos[i];
sa[0].vec[sa[0].tag[cx]].push_back(cx);
}
for(int i=2;i<=sa[1].cnt;--i)
{
int cx=sa[1].pos[i];
sa[1].vec[sa[1].tag[cx]].push_back(cx);
}
for(int i=tot;i>=1;i--){
for(auto r:sa[0].vec[i]){
for(int v=sa[0].e.head[r];v;v=sa[0].e.nex[v]) vr[r]+=vr[sa[0].e.t[v]];
if(sa[0].len[r]==sa[0].rg[r]) vr[r]+=wr[sa[0].rg[r]];
}
for(auto r:sa[1].vec[i]){
for(int v=sa[1].e.head[r];v;v=sa[1].e.nex[v]) vl[r]+=vl[sa[1].e.t[v]];
if(sa[1].len[r]==n-sa[1].rg[r]+1) vl[r]+=wl[sa[1].rg[r]];
}
}
int x1,y1,x2,y2;
for(int i=1;i<=q;i++){
x1=qread(); y1=qread(); x2=qread(); y2=qread();
int p1=sa[1].f(sa[1].ed[x1],y1-x1+1);
int p0=sa[0].f(sa[0].ed[y2],y2-x2+1);
int l1=sa[0].dfn[p0],r1=sa[0].dfn[p0]+sa[0].sz[p0]-1;
int l2=sa[1].dfn[p1],r2=sa[1].dfn[p1]+sa[1].sz[p1]-1;
if(sa[1].tag[p1]==sa[0].tag[p0]){
int len=sa[0].len[rt[0][sa[1].tag[p1]]]-(sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]+sa[0].rg[rt[0][sa[1].tag[p1]]]-sa[0].rg[p0]);
if(sa[0].clen[p0]-1>=sa[1].rg[p1]-sa[1].rg[rt[1][sa[1].tag[p1]]]&&(y1-x1+1>len||y2-x2+1>len)) ans[i]-=occ[sa[1].tag[p1]]*vl[p1]*vr[p0];
}
else{
subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),r2,i,-vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].clen[p0],r2,i,vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].len[p0]-(y2-x2),l2-1,i,vr[p0]));
subqry[0][sa[0].tag[p0]].pb(node(sa[0].clen[p0],l2-1,i,-vr[p0]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),r1,i,-vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].clen[p1],r1,i,vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].len[p1]-(y1-x1),l1-1,i,vl[p1]));
subqry[1][sa[1].tag[p1]].pb(node(sa[1].clen[p1],l1-1,i,-vl[p1]));
}
qry.pb(node(r1,r2,i,1));
qry.pb(node(r1,l2-1,i,-1));
qry.pb(node(l1-1,r2,i,-1));
qry.pb(node(l1-1,l2-1,i,1));
}
for(int i=1;i<=tot;i++){
for(int k=0;k<2;k++){
bit::tim++;
sort(subqry[k][i].begin(),subqry[k][i].end());
int now=(int)subqry[k][i].size()-1;
while(now>=0&&subqry[k][i][now].x==sa[k^1].vec[i].size()) now--;
for(int j=0;j<sa[k^1].vec[i].size();j++){
int r=sa[k^1].vec[i][j];
bit::add(sa[k^1].dfn[r],k==0?vl[r]:vr[r]);
while(now>=0&&sa[k^1].vec[i].size()-j-1==subqry[k][i][now].x){
node nd=subqry[k][i][now];
ans[nd.id]+=occ[i]*nd.w*bit::ask(nd.y);
now--;
}
}
}
}
sub1::work();
for(int i=1;i<=q;i++) printf("%llu\n",ans[i]);
puts("-");
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 51828kb
input:
500 500 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '15720454042420499810', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #22:
score: 0
Time Limit Exceeded
input:
100000 100000 zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%