QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#757414#4255. Sone2I_be_wanna100 ✓640ms41168kbC++1418.9kb2024-11-17 06:52:102024-11-17 06:52:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-17 06:52:11]
  • 评测
  • 测评结果：100
  • 用时：640ms
  • 内存：41168kb
查看
  • [2024-11-17 06:52:10]
  • 提交

answer

#include<bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;const int N=1e5+10;const int M=(N<<1);mt19937 rnd(time(0));inline int read(){char ch=getchar();int x=0;while(!isdigit(ch)){ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x;}struct SA{int n,m,s[N],sa[M],rk[M],id[M],px[M],ht[M],mn[M][20],lrk[M],cnt[M];inline bool cmp(int x,int y,int w){return lrk[x]==lrk[y]&&lrk[x+w]==lrk[y+w];}inline int lcp(int x,int y){if(x==0||y==0)return 0;if(x==y)return n-sa[x]+1;if(x>y)swap(x,y);x++;int tmp=__lg(y-x+1);return min(mn[x][tmp],mn[y-(1<<tmp)+1][tmp]);}inline void init(){int i,j,k,p,w;for(i=1;i<=n;++i)cnt[rk[i]=s[i]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;for(w=1;;w<<=1,m=p){for(i=n,p=0;i>n-w;--i)id[++p]=i;for(i=1;i<=n;++i)if(sa[i]>w)id[++p]=sa[i]-w;for(i=1;i<=m;++i)cnt[i]=0;for(i=1;i<=n;++i)cnt[px[i]=rk[id[i]]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[px[i]]--]=id[i];for(i=1;i<=n;++i)lrk[i]=rk[i];for(i=1,p=0;i<=n;++i)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;if(p==n){for(i=1;i<=n;++i)sa[rk[i]]=i;break;}}for(i=1,k=0;i<=n;++i){if(k)k--;while(i+k<=n&&sa[rk[i]-1]+k<=n&&s[sa[rk[i]-1]+k]==s[i+k])k++;ht[rk[i]]=k;}for(i=1;i<=n;++i)mn[i][0]=ht[i];for(j=1;j<=16;++j)for(i=1;i+(1<<j)-1<=n;++i)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}inline int check(int x,int y,int p,int q){if(x==0||p==0)return 0;int l,r,mid,xl,xr,pos;l=1,r=rk[x];while(l+1<r){mid=(l+r)>>1;if(lcp(mid,rk[x])>=y-x+1)r=mid;else l=mid;}if(lcp(l,rk[x])>=y-x+1)xl=l;else xl=r;l=rk[x],r=n;while(l+1<r){mid=(l+r)>>1;if(lcp(rk[x],mid)>=y-x+1)l=mid;else r=mid;}if(lcp(rk[x],r)>=y-x+1)xr=r;else xr=l;if(rk[sa[xl]+y-x+1]<=rk[p]){l=xl,r=xr;while(l+1<r){mid=(l+r)>>1;if(rk[sa[mid]+y-x+1]<=rk[p])l=mid;else r=mid;}if(rk[sa[r]+y-x+1]<=rk[p])pos=r;else pos=l;if(lcp(rk[sa[pos]+y-x+1],rk[p])>=q-p+1)return sa[pos];}if(rk[sa[xr]+y-x+1]>=rk[p]){l=xl,r=xr;while(l+1<r){mid=(l+r)>>1;if(rk[sa[mid]+y-x+1]>=rk[p])r=mid;else l=mid;}if(rk[sa[l]+y-x+1]>=rk[p])pos=l;else pos=r;if(lcp(rk[p],rk[sa[pos]+y-x+1])>=q-p+1)return sa[pos];}return 0;}}sa;struct node{int mx,val;node(int a=0,int b=0){mx=a;val=b;}node operator+(const node&tmp)const{if(mx<tmp.mx)return tmp;else if(mx>tmp.mx)return node(mx,val);else return node(mx,val+tmp.val);}};int n,Q,m,s[N],t[N],nxt[N],f[N],mp[N];node bz[N][20];struct Cover{struct Node{int s,l,r;Node(int a=0,int b=0,int c=0){s=a;l=b;r=c;}bool operator<(const Node&tmp)const{return s<tmp.s;}};set<Node>S;node t[N<<2];void build(int rt,int l,int r){t[rt]=node(0,0);if(l==r)return;int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);}void update(int rt,int l,int r,int x,node val){if(l==r)return t[rt]=val,void();int mid=(l+r)>>1;if(x<=mid)update(ls,l,mid,x,val);else update(rs,mid+1,r,x,val);t[rt]=t[ls]+t[rs];}node query(int rt,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return t[rt];int mid=(l+r)>>1;node res=node(0,0);if(ql<=mid)res=res+query(ls,l,mid,ql,qr);if(qr>mid)res=res+query(rs,mid+1,r,ql,qr);return res;}node calc(vector<Node>&vec){int l=vec[0].l,r=vec[0].r;int len=nxt[r];if(l==1)len=r-l+1;while(len>r-l+1)len=nxt[len];node res=node(0,0);for(int i=16;i>=0;--i){if(l+(1<<i)-1>r-len)continue;res=res+bz[l][i];l+=(1<<i);}if(vec.size()==1)res=res+node(len,!!len);else if(vec.size()==2){int tmp;while(len){tmp=len+min(sa.lcp(sa.rk[vec[1].l],sa.rk[len+1]),vec[1].r-vec[1].l+1);res=res+node(tmp,1);len=nxt[len];}}else{int tmp,mem;while(len){mem=sa.lcp(sa.rk[vec[1].l],sa.rk[len+1]);if(mem>=vec[1].r-vec[1].l+1){mem=len+vec[1].r-vec[1].l+1;tmp=mem+min(sa.lcp(sa.rk[vec[2].l],sa.rk[mem+1]),vec[2].r-vec[2].l+1);}else tmp=len+mem;res=res+node(tmp,1);len=nxt[len];}}return res;}void init(){S.clear();build(1,1,n);for(int i=1;i<=n;++i){if(mp[s[i]]==0)S.insert(Node(i,0,0));else{int j=i,o=mp[s[i]],tmp;while(j<n&&mp[s[j+1]]&&(tmp=sa.check(o,o+j-i,mp[s[j+1]],mp[s[j+1]]),tmp))o=tmp,j++;S.insert(Node(i,o,o+j-i));i=j;}}auto it=S.begin();vector<Node>vec;while(it!=S.end()){if((*it).l==0){update(1,1,n,(*it).s,node(0,1));it++;continue;}else{vec.clear();vec.push_back(*it);it++;if(it!=S.end()&&(*it).l){vec.push_back(*it);it++;if(it!=S.end()&&(*it).l)vec.push_back(*it);it--;}it--;update(1,1,n,(*it).s,calc(vec));it++;}}}void change(int x){auto it=S.upper_bound(Node(x,0,0));it--;vector<Node>mem;if(it!=S.begin()){it--;mem.push_back(*it);if(it!=S.begin()){it--;mem.push_back(*it);if(it!=S.begin()){it--;mem.push_back(*it);it++;}it++;}it++;}reverse(mem.begin(),mem.end());for(auto o:mem)S.erase(S.find(o));Node now=(*it);if(x>now.s)mem.push_back(Node(now.s,now.l,now.l+x-now.s-1));mem.push_back(Node(x,mp[s[x]],mp[s[x]]));if(x<now.s+now.r-now.l)mem.push_back(Node(x+1,now.l+x-now.s+1,now.r));it++;bool pd=false;if(it!=S.end())mem.push_back(*it),pd=true;it--;S.erase(S.find(now));if(pd)S.erase(S.find(mem.back()));vector<Node>ex;for(int i=0;i<mem.size();++i){int j=i,o=mem[i].l,tmp;while(j+1<mem.size()&&mem[j+1].l&&(tmp=sa.check(o,o+mem[j+1].s-mem[i].s-1,mem[j+1].l,mem[j+1].r),tmp)){o=tmp;j++;update(1,1,n,mem[j].s,node(0,0));}ex.push_back(Node(mem[i].s,o,o+mem[j].s+mem[j].r-mem[j].l-mem[i].s));i=j;}for(auto o:ex)S.insert(o);vector<Node>vec;for(auto o:ex){it=S.lower_bound(o);if(o.l==0){update(1,1,n,o.s,node(0,1));continue;}else{vec.clear();vec.push_back(o);it++;if(it!=S.end()&&(*it).l){vec.push_back(*it);it++;if(it!=S.end()&&(*it).l)vec.push_back(*it);it--;}it--;update(1,1,n,o.s,calc(vec));}}}node work(int l,int r){auto itl=S.upper_bound(Node(l,0,0));itl--;auto itr=S.upper_bound(Node(r,0,0));itr--;auto it=itr;for(int i=0;i<4;++i){if(it==S.begin())break;it--;}if((*it).s<=(*itl).s){it=itl;vector<Node>mem;Node tmp;while(it!=S.end()&&(*it).s<=(*itr).s){tmp=(*it);if(tmp.s<l){int del=l-tmp.s;tmp.s+=del;tmp.l+=del;}if(tmp.s+tmp.r-tmp.l>r){int del=tmp.s+tmp.r-tmp.l-r;tmp.r-=del;}mem.push_back(tmp);it++;}vector<Node>ex;for(int i=0;i<mem.size();++i){int j=i,o=mem[i].l,tmp;while(j+1<mem.size()&&mem[j+1].l&&(tmp=sa.check(o,o+mem[j+1].s-mem[i].s-1,mem[j+1].l,mem[j+1].r),tmp))o=tmp,j++;ex.push_back(Node(mem[i].s,o,o+mem[j].s+mem[j].r-mem[j].l-mem[i].s));i=j;}vector<Node>vec;node res=node(0,0);Node now;for(int i=0;i<ex.size();++i){now=ex[i];if(now.l==0)res=res+node(0,1);else{vec.clear();vec.push_back(now);int j=i+1;if(j<ex.size()&&ex[j].l){vec.push_back(ex[j]);j++;if(j<ex.size()&&ex[j].l)vec.push_back(ex[j]);}res=res+calc(vec);}}return res;}else{Node nowl=(*itl);if(nowl.s<l){int del=l-nowl.s;nowl.s+=del;nowl.l+=del;}itl++;Node nxtl=(*itl);int tmp=sa.check(nowl.l,nowl.r,nxtl.l,nxtl.r);int L,R;node res=node(0,0);if(tmp){L=nxtl.s+nxtl.r-nxtl.l+1;nowl.l=tmp;nowl.r=nowl.l+nxtl.s+nxtl.r-nxtl.l-nowl.s;vector<Node>vec;vec.push_back(nowl);itl++;if(itl!=S.end()&&(*itl).l){vec.push_back(*itl);itl++;if(itl!=S.end()&&(*itl).l)vec.push_back(*itl);}res=res+calc(vec);}else{L=nxtl.s;if(nowl.l){vector<Node>vec;vec.push_back(nowl);if(nxtl.l){vec.push_back(nxtl);itl++;if(itl!=S.end()&&(*itl).l)vec.push_back(*itl);}res=res+calc(vec);}}it=itr;it--;Node nowr=(*itr),nxtr=(*it);if(nowr.s+nowr.r-nowr.l>r){int del=nowr.s+nowr.r-nowr.l-r;nowr.r-=del;}tmp=sa.check(nxtr.l,nxtr.r,nowr.l,nowr.r);if(tmp){nxtr.l=tmp;nxtr.r=nxtr.l+nowr.s+nowr.r-nowr.l-nxtr.s;vector<Node>vec;vec.push_back(nxtr);res=res+calc(vec);it--;if((*it).l){vec.clear();vec.push_back(*it);vec.push_back(nxtr);res=res+calc(vec);}it--;if((*it).l){vec.clear();vec.push_back(*it);it++;if((*it).l){vec.push_back(*it);vec.push_back(nxtr);}res=res+calc(vec);it--;}R=(*it).s-1;}else{vector<Node>vec;if(nowr.l){vec.clear();vec.push_back(nowr);res=res+calc(vec);}if(nxtr.l){vec.clear();vec.push_back(nxtr);if(nowr.l)vec.push_back(nowr);res=res+calc(vec);}it--;if((*it).l){vec.clear();vec.push_back(*it);if(nxtr.l){vec.push_back(nxtr);if(nowr.l)vec.push_back(nowr);}res=res+calc(vec);}R=(*it).s-1;}res=res+query(1,1,n,L,R);return res;}}}T;int main(){int ID=read();n=read();for(int i=1;i<=n;++i)s[i]=read();sa.n=sa.m=m=read();for(int i=1;i<=m;++i)t[i]=sa.s[i]=read(),mp[t[i]]=i;sa.init();for(int i=2,j=0;i<=m;++i){while(j&&t[j+1]!=t[i])j=nxt[j];if(t[j+1]==t[i])j++;nxt[i]=j;}for(int i=1,j=0;i<=n;++i){while(j&&(j==m||t[j+1]!=s[i]))j=nxt[j];if(t[j+1]==s[i])j++;f[i]=j;}for(int i=1;i<=m;++i)bz[i][0]=node(sa.lcp(sa.rk[1],sa.rk[i]),1);for(int j=1;j<=16;++j)for(int i=1;i+(1<<j)-1<=m;++i)bz[i][j]=bz[i][j-1]+bz[i+(1<<(j-1))][j-1];T.init();Q=read();int x,y,z,p,q;while(Q--){x=read();if(x==1){y=read();z=read();s[y]=z;T.change(y);printf("%d %d\n",T.t[1].mx,T.t[1].val);}else if(x==2){y=read();z=read();node res=T.work(y,z);printf("%d %d\n",res.mx,res.val);}else if(x==3){y=read();z=read();printf("%d\n",sa.lcp(sa.rk[y],sa.rk[z]));}else{y=read();z=read();p=read();q=read();if(sa.check(y,z,p,q))puts("yes");else puts("no");}}return 0;}
/*
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;const int N=1e5+10;const int M=(N<<1);mt19937 rnd(time(0));inline int read(){char ch=getchar();int x=0;while(!isdigit(ch)){ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x;}struct SA{int n,m,s[N],sa[M],rk[M],id[M],px[M],ht[M],mn[M][20],lrk[M],cnt[M];inline bool cmp(int x,int y,int w){return lrk[x]==lrk[y]&&lrk[x+w]==lrk[y+w];}inline int lcp(int x,int y){if(x==0||y==0)return 0;if(x==y)return n-sa[x]+1;if(x>y)swap(x,y);x++;int tmp=__lg(y-x+1);return min(mn[x][tmp],mn[y-(1<<tmp)+1][tmp]);}inline void init(){int i,j,k,p,w;for(i=1;i<=n;++i)cnt[rk[i]=s[i]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;for(w=1;;w<<=1,m=p){for(i=n,p=0;i>n-w;--i)id[++p]=i;for(i=1;i<=n;++i)if(sa[i]>w)id[++p]=sa[i]-w;for(i=1;i<=m;++i)cnt[i]=0;for(i=1;i<=n;++i)cnt[px[i]=rk[id[i]]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[px[i]]--]=id[i];for(i=1;i<=n;++i)lrk[i]=rk[i];for(i=1,p=0;i<=n;++i)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;if(p==n){for(i=1;i<=n;++i)sa[rk[i]]=i;break;}}for(i=1,k=0;i<=n;++i){if(k)k--;while(i+k<=n&&sa[rk[i]-1]+k<=n&&s[sa[rk[i]-1]+k]==s[i+k])k++;ht[rk[i]]=k;}for(i=1;i<=n;++i)mn[i][0]=ht[i];for(j=1;j<=16;++j)for(i=1;i+(1<<j)-1<=n;++i)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}inline int check(int x,int y,int p,int q){if(x==0||p==0)return 0;int l,r,mid,xl,xr,pos;l=1,r=rk[x];while(l+1<r){mid=(l+r)>>1;if(lcp(mid,rk[x])>=y-x+1)r=mid;else l=mid;}if(lcp(l,rk[x])>=y-x+1)xl=l;else xl=r;l=rk[x],r=n;while(l+1<r){mid=(l+r)>>1;if(lcp(rk[x],mid)>=y-x+1)l=mid;else r=mid;}if(lcp(rk[x],r)>=y-x+1)xr=r;else xr=l;if(rk[sa[xl]+y-x+1]<=rk[p]){l=xl,r=xr;while(l+1<r){mid=(l+r)>>1;if(rk[sa[mid]+y-x+1]<=rk[p])l=mid;else r=mid;}if(rk[sa[r]+y-x+1]<=rk[p])pos=r;else pos=l;if(lcp(rk[sa[pos]+y-x+1],rk[p])>=q-p+1)return sa[pos];}if(rk[sa[xr]+y-x+1]>=rk[p]){l=xl,r=xr;while(l+1<r){mid=(l+r)>>1;if(rk[sa[mid]+y-x+1]>=rk[p])r=mid;else l=mid;}if(rk[sa[l]+y-x+1]>=rk[p])pos=l;else pos=r;if(lcp(rk[p],rk[sa[pos]+y-x+1])>=q-p+1)return sa[pos];}return 0;}}sa;struct node{int mx,val;node(int a=0,int b=0){mx=a;val=b;}node operator+(const node&tmp)const{if(mx<tmp.mx)return tmp;else if(mx>tmp.mx)return node(mx,val);else return node(mx,val+tmp.val);}};int n,Q,m,s[N],t[N],nxt[N],f[N],mp[N];node bz[N][20];struct Cover{struct Node{int s,l,r;Node(int a=0,int b=0,int c=0){s=a;l=b;r=c;}bool operator<(const Node&tmp)const{return s<tmp.s;}};set<Node>S;node t[N<<2];void build(int rt,int l,int r){t[rt]=node(0,0);if(l==r)return;int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);}void update(int rt,int l,int r,int x,node val){if(l==r)return t[rt]=val,void();int mid=(l+r)>>1;if(x<=mid)update(ls,l,mid,x,val);else update(rs,mid+1,r,x,val);t[rt]=t[ls]+t[rs];}node query(int rt,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return t[rt];int mid=(l+r)>>1;node res=node(0,0);if(ql<=mid)res=res+query(ls,l,mid,ql,qr);if(qr>mid)res=res+query(rs,mid+1,r,ql,qr);return res;}node calc(vector<Node>&vec){int l=vec[0].l,r=vec[0].r;int len=nxt[r];if(l==1)len=r-l+1;while(len>r-l+1)len=nxt[len];node res=node(0,0);for(int i=16;i>=0;--i){if(l+(1<<i)-1>r-len)continue;res=res+bz[l][i];l+=(1<<i);}if(vec.size()==1)res=res+node(len,!!len);else if(vec.size()==2){int tmp;while(len){tmp=len+min(sa.lcp(sa.rk[vec[1].l],sa.rk[len+1]),vec[1].r-vec[1].l+1);res=res+node(tmp,1);len=nxt[len];}}else{int tmp,mem;while(len){mem=sa.lcp(sa.rk[vec[1].l],sa.rk[len+1]);if(mem>=vec[1].r-vec[1].l+1){mem=len+vec[1].r-vec[1].l+1;tmp=mem+min(sa.lcp(sa.rk[vec[2].l],sa.rk[mem+1]),vec[2].r-vec[2].l+1);}else tmp=len+mem;res=res+node(tmp,1);len=nxt[len];}}return res;}void init(){S.clear();build(1,1,n);for(int i=1;i<=n;++i){if(mp[s[i]]==0)S.insert(Node(i,0,0));else{int j=i,o=mp[s[i]],tmp;while(j<n&&mp[s[j+1]]&&(tmp=sa.check(o,o+j-i,mp[s[j+1]],mp[s[j+1]]),tmp))o=tmp,j++;S.insert(Node(i,o,o+j-i));i=j;}}auto it=S.begin();vector<Node>vec;while(it!=S.end()){if((*it).l==0){update(1,1,n,(*it).s,node(0,1));it++;continue;}else{vec.clear();vec.push_back(*it);it++;if(it!=S.end()&&(*it).l){vec.push_back(*it);it++;if(it!=S.end()&&(*it).l)vec.push_back(*it);it--;}it--;update(1,1,n,(*it).s,calc(vec));it++;}}}void change(int x){auto it=S.upper_bound(Node(x,0,0));it--;vector<Node>mem;if(it!=S.begin()){it--;mem.push_back(*it);if(it!=S.begin()){it--;mem.push_back(*it);if(it!=S.begin()){it--;mem.push_back(*it);it++;}it++;}it++;}reverse(mem.begin(),mem.end());for(auto o:mem)S.erase(S.find(o));Node now=(*it);if(x>now.s)mem.push_back(Node(now.s,now.l,now.l+x-now.s-1));mem.push_back(Node(x,mp[s[x]],mp[s[x]]));if(x<now.s+now.r-now.l)mem.push_back(Node(x+1,now.l+x-now.s+1,now.r));it++;bool pd=false;if(it!=S.end())mem.push_back(*it),pd=true;it--;S.erase(S.find(now));if(pd)S.erase(S.find(mem.back()));vector<Node>ex;for(int i=0;i<mem.size();++i){int j=i,o=mem[i].l,tmp;while(j+1<mem.size()&&mem[j+1].l&&(tmp=sa.check(o,o+mem[j+1].s-mem[i].s-1,mem[j+1].l,mem[j+1].r),tmp)){o=tmp;j++;update(1,1,n,mem[j].s,node(0,0));}ex.push_back(Node(mem[i].s,o,o+mem[j].s+mem[j].r-mem[j].l-mem[i].s));i=j;}for(auto o:ex)S.insert(o);vector<Node>vec;for(auto o:ex){it=S.lower_bound(o);if(o.l==0){update(1,1,n,o.s,node(0,1));continue;}else{vec.clear();vec.push_back(o);it++;if(it!=S.end()&&(*it).l){vec.push_back(*it);it++;if(it!=S.end()&&(*it).l)vec.push_back(*it);it--;}it--;update(1,1,n,o.s,calc(vec));}}}node work(int l,int r){auto itl=S.upper_bound(Node(l,0,0));itl--;auto itr=S.upper_bound(Node(r,0,0));itr--;auto it=itr;for(int i=0;i<4;++i){if(it==S.begin())break;it--;}if((*it).s<=(*itl).s){it=itl;vector<Node>mem;Node tmp;while(it!=S.end()&&(*it).s<=(*itr).s){tmp=(*it);if(tmp.s<l){int del=l-tmp.s;tmp.s+=del;tmp.l+=del;}if(tmp.s+tmp.r-tmp.l>r){int del=tmp.s+tmp.r-tmp.l-r;tmp.r-=del;}mem.push_back(tmp);it++;}vector<Node>ex;for(int i=0;i<mem.size();++i){int j=i,o=mem[i].l,tmp;while(j+1<mem.size()&&mem[j+1].l&&(tmp=sa.check(o,o+mem[j+1].s-mem[i].s-1,mem[j+1].l,mem[j+1].r),tmp))o=tmp,j++;ex.push_back(Node(mem[i].s,o,o+mem[j].s+mem[j].r-mem[j].l-mem[i].s));i=j;}vector<Node>vec;node res=node(0,0);Node now;for(int i=0;i<ex.size();++i){now=ex[i];if(now.l==0)res=res+node(0,1);else{vec.clear();vec.push_back(now);int j=i+1;if(j<ex.size()&&ex[j].l){vec.push_back(ex[j]);j++;if(j<ex.size()&&ex[j].l)vec.push_back(ex[j]);}res=res+calc(vec);}}return res;}else{Node nowl=(*itl);if(nowl.s<l){int del=l-nowl.s;nowl.s+=del;nowl.l+=del;}itl++;Node nxtl=(*itl);int tmp=sa.check(nowl.l,nowl.r,nxtl.l,nxtl.r);int L,R;node res=node(0,0);if(tmp){L=nxtl.s+nxtl.r-nxtl.l+1;nowl.l=tmp;nowl.r=nowl.l+nxtl.s+nxtl.r-nxtl.l-nowl.s;vector<Node>vec;vec.push_back(nowl);itl++;if(itl!=S.end()&&(*itl).l){vec.push_back(*itl);itl++;if(itl!=S.end()&&(*itl).l)vec.push_back(*itl);}res=res+calc(vec);}else{L=nxtl.s;if(nowl.l){vector<Node>vec;vec.push_back(nowl);if(nxtl.l){vec.push_back(nxtl);itl++;if(itl!=S.end()&&(*itl).l)vec.push_back(*itl);}res=res+calc(vec);}}it=itr;it--;Node nowr=(*itr),nxtr=(*it);if(nowr.s+nowr.r-nowr.l>r){int del=nowr.s+nowr.r-nowr.l-r;nowr.r-=del;}tmp=sa.check(nxtr.l,nxtr.r,nowr.l,nowr.r);if(tmp){nxtr.l=tmp;nxtr.r=nxtr.l+nowr.s+nowr.r-nowr.l-nxtr.s;vector<Node>vec;vec.push_back(nxtr);res=res+calc(vec);it--;if((*it).l){vec.clear();vec.push_back(*it);vec.push_back(nxtr);res=res+calc(vec);}it--;if((*it).l){vec.clear();vec.push_back(*it);it++;if((*it).l){vec.push_back(*it);vec.push_back(nxtr);}res=res+calc(vec);it--;}R=(*it).s-1;}else{vector<Node>vec;if(nowr.l){vec.clear();vec.push_back(nowr);res=res+calc(vec);}if(nxtr.l){vec.clear();vec.push_back(nxtr);if(nowr.l)vec.push_back(nowr);res=res+calc(vec);}it--;if((*it).l){vec.clear();vec.push_back(*it);if(nxtr.l){vec.push_back(nxtr);if(nowr.l)vec.push_back(nowr);}res=res+calc(vec);}R=(*it).s-1;}res=res+query(1,1,n,L,R);return res;}}}T;int main(){int ID=read();n=read();for(int i=1;i<=n;++i)s[i]=read();sa.n=sa.m=m=read();for(int i=1;i<=m;++i)t[i]=sa.s[i]=read(),mp[t[i]]=i;sa.init();for(int i=2,j=0;i<=m;++i){while(j&&t[j+1]!=t[i])j=nxt[j];if(t[j+1]==t[i])j++;nxt[i]=j;}for(int i=1,j=0;i<=n;++i){while(j&&(j==m||t[j+1]!=s[i]))j=nxt[j];if(t[j+1]==s[i])j++;f[i]=j;}for(int i=1;i<=m;++i)bz[i][0]=node(sa.lcp(sa.rk[1],sa.rk[i]),1);for(int j=1;j<=16;++j)for(int i=1;i+(1<<j)-1<=m;++i)bz[i][j]=bz[i][j-1]+bz[i+(1<<(j-1))][j-1];T.init();Q=read();int x,y,z,p,q;while(Q--){x=read();if(x==1){y=read();z=read();s[y]=z;T.change(y);printf("%d %d\n",T.t[1].mx,T.t[1].val);}else if(x==2){y=read();z=read();node res=T.work(y,z);printf("%d %d\n",res.mx,res.val);}else if(x==3){y=read();z=read();printf("%d\n",sa.lcp(sa.rk[y],sa.rk[z]));}else{y=read();z=read();p=read();q=read();if(sa.check(y,z,p,q))puts("yes");else puts("no");}}return 0;}
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;const int N=1e5+10;const int M=(N<<1);mt19937 rnd(time(0));inline int read(){char ch=getchar();int x=0;while(!isdigit(ch)){ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x;}struct SA{int n,m,s[N],sa[M],rk[M],id[M],px[M],ht[M],mn[M][20],lrk[M],cnt[M];inline bool cmp(int x,int y,int w){return lrk[x]==lrk[y]&&lrk[x+w]==lrk[y+w];}inline int lcp(int x,int y){if(x==0||y==0)return 0;if(x==y)return n-sa[x]+1;if(x>y)swap(x,y);x++;int tmp=__lg(y-x+1);return min(mn[x][tmp],mn[y-(1<<tmp)+1][tmp]);}inline void init(){int i,j,k,p,w;for(i=1;i<=n;++i)cnt[rk[i]=s[i]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[rk[i]]--]=i;for(w=1;;w<<=1,m=p){for(i=n,p=0;i>n-w;--i)id[++p]=i;for(i=1;i<=n;++i)if(sa[i]>w)id[++p]=sa[i]-w;for(i=1;i<=m;++i)cnt[i]=0;for(i=1;i<=n;++i)cnt[px[i]=rk[id[i]]]++;for(i=1;i<=m;++i)cnt[i]+=cnt[i-1];for(i=n;i>=1;--i)sa[cnt[px[i]]--]=id[i];for(i=1;i<=n;++i)lrk[i]=rk[i];for(i=1,p=0;i<=n;++i)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;if(p==n){for(i=1;i<=n;++i)sa[rk[i]]=i;break;}}for(i=1,k=0;i<=n;++i){if(k)k--;while(i+k<=n&&sa[rk[i]-1]+k<=n&&s[sa[rk[i]-1]+k]==s[i+k])k++;ht[rk[i]]=k;}for(i=1;i<=n;++i)mn[i][0]=ht[i];for(j=1;j<=16;++j)for(i=1;i+(1<<j)-1<=n;++i)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);}inline int check(int x,int y,int p,int q){if(x==0||p==0)return 0;int l,r,mid,xl,xr,pos;l=1,r=rk[x];while(l+1<r){mid=(l+r)>>1;if(lcp(mid,rk[x])>=y-x+1)r=mid;else l=mid;}if(lcp(l,rk[x])>=y-x+1)xl=l;else xl=r;l=rk[x],r=n;while(l+1<r){mid=(l+r)>>1;if(lcp(rk[x],mid)>=y-x+1)l=mid;else r=mid;}if(lcp(rk[x],r)>=y-x+1)xr=r;else xr=l;if(rk[sa[xl]+y-x+1]<=rk[p]){l=xl,r=xr;while(l+1<r){mid=(l+r)>>1;if(rk[sa[mid]+y%d\n",T.t[1].mx,T.t[1].val);}else if(x==2){y=read();z=read();node res=T.work(y,z);printf("%d %d\n",res.mx,res.val);}else if(x==3){y=read();z=read();printf("%d\n",sa.lcp(sa.rk[y],sa.rk[z]));}else{y=read();z=read();p=read();q=read();if(sa.check(y,z,p,q))puts("yes");else puts("no");}}return 0;}*/
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

详细


Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 3ms
memory: 31688kb

input:

1
1000
2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 299 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 824 1...

output:

46 1
12 2
46 1
46 1
73 1
100 1
51 1
100 1
100 1
73 1
0
73 1
73 1
73 1
73 1
73 1
19 1
51 1
73 1
73 1
73 1
44 1
51 1
51 1
73 1
22 2
73 1
46 1
0
73 1
yes
57 1
73 1
73 1
73 1
73 1
73 1
73 1
73 1
73 1
51 1
yes
73 1
51 1
73 1
30 1
73 1
73 1
15 1
73 1
73 1
73 1
73 1
46 1
73 1
65 1
0
73 1
12 1
3 1
73 1
73 1...

result:

ok 1911 tokens

Test #2:

score: 5
Accepted
time: 3ms
memory: 32508kb

input:

2
1000
3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 406 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 98 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 970 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 ...

output:

62 1
93 1
62 3
93 1
62 2
65 1
93 1
93 1
93 1
93 1
93 1
62 2
1
93 1
93 1
62 2
62 2
62 3
42 1
93 1
93 1
62 2
44 1
93 1
62 2
93 1
62 1
93 1
72 1
72 1
62 1
72 1
23 1
72 1
no
62 2
72 1
72 1
72 1
62 3
72 1
72 1
72 1
no
43 1
72 1
62 2
40 1
62 2
8 1
62 2
62 2
0
62 2
62 1
62 1
62 1
62 2
62 2
62 1
62 2
5
62 1...

result:

ok 1915 tokens

Test #3:

score: 5
Accepted
time: 180ms
memory: 31308kb

input:

3
100000
1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1...

output:

100 979
100 978
4
100 978
100 977
100 976
100 975
100 974
100 973
100 972
100 971
100 971
100 970
100 969
100 968
100 967
100 966
100 966
100 965
100 965
9
100 964
no
100 964
100 963
100 962
100 961
100 960
100 959
100 958
100 957
100 956
100 955
yes
100 954
100 954
100 953
100 952
100 951
100 950
1...

result:

ok 191356 tokens

Test #4:

score: 5
Accepted
time: 189ms
memory: 31344kb

input:

4
100000
1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1...

output:

100 979
100 978
100 977
100 976
100 975
100 974
100 974
100 973
no
100 972
100 971
100 970
100 970
100 969
100 968
100 967
100 966
no
100 965
100 964
100 963
100 962
100 961
100 960
100 959
100 959
0
100 958
100 957
100 957
100 957
100 956
100 955
100 954
100 953
0
100 952
2
100 951
100 950
100 950
...

result:

ok 191356 tokens

Test #5:

score: 5
Accepted
time: 94ms
memory: 32496kb

input:

5
100000
5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3...

output:

30 3312
30 1774
30 3311
30 2286
0
30 365
30 3310
30 3309
30 3308
30 3307
30 3306
30 3305
30 1856
30 387
30 1033
30 3304
30 1681
30 3303
30 3302
30 3302
30 3301
30 3300
30 845
30 544
30 2719
30 3299
30 1344
30 3298
30 3298
yes
30 3297
30 3296
30 3295
30 473
30 3294
30 3293
30 3292
yes
30 859
30 3291
...

result:

ok 191359 tokens

Test #6:

score: 5
Accepted
time: 104ms
memory: 30188kb

input:

6
100000
2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2...

output:

30 33114
30 12379
30 33114
30 33104
30 23307
30 33094
30 33084
30 1497
no
30 33074
30 13431
30 33064
30 19
30 33054
30 33044
30 4288
30 10728
30 33034
30 6847
30 33024
30 10621
30 33014
30 10308
1
30 11959
30 3935
30 19153
30 33004
30 32994
30 2789
30 32984
30 32984
0
30 21909
30 32984
30 10889
30 3...

result:

ok 191357 tokens

Test #7:

score: 5
Accepted
time: 45ms
memory: 39732kb

input:

7
100000
1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
0
1
4
1
5
1
12
2
7
3
4
4
0
0
1
0
1
3
2
2
2
1
3
0
3
2
3
2
7
0
2
1
1
3
78193
0
5
2
8
7
10
4
4
2
1
0
0
1
1
9
0
1
2
1
7
10
0
0
0
6
0
0
4
7
4
3
1
2
0
0
1
12
2
0
2
5
3
1
0
3
4
7
1
0
9
4
1
5
2
6
23
0
12
6
6
0
2
8
4
2
5
2
1
0
3
10
8
0
2
5
1
2
6
5
9
1
0
0
9
4
3
0
5
0
0
6
4
4
0
1
3
13
0
2
4
1
5
2
0
5
4
2
1
...

result:

ok 100000 tokens

Test #8:

score: 5
Accepted
time: 52ms
memory: 39440kb

input:

8
100000
1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0
8
5
2
0
8
4
8
1
2
0
2
0
1
9
1
0
0
0
2
2
0
0
3
0
4
3
1
5
1
5
2
3
11
8
2
3
3
6
2
0
3
0
1
1
1
3
1
0
16
8
0
0
8
13
4
0
3
0
3
0
0
0
0
0
4
7
2
0
2
8
10
0
0
0
4
0
8
2
0
0
7
1
3
5
9
1
0
2
4
0
8
0
3
2
4
1
3
0
0
1
1
5
8
1
0
0
2
4
2
0
3
0
1
3
0
2
0
1
2
15
0
5
2
13
0
3
0
0
0
1
1
3
4
1
1
2
0
4
2
2
14
1
4
5
9
0...

result:

ok 100000 tokens

Test #9:

score: 5
Accepted
time: 58ms
memory: 39060kb

input:

9
100000
1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 1 1 1 1 1 3 1 3 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1...

output:

no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
no
no
no
no
no
no
...

result:

ok 100000 tokens

Test #10:

score: 5
Accepted
time: 68ms
memory: 40940kb

input:

10
100000
1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 ...

output:

no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
...

result:

ok 100000 tokens

Test #11:

score: 5
Accepted
time: 555ms
memory: 41168kb

input:

11
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 ...

output:

76221 1
50830 1
72471 1
72471 1
54048 1
54048 1
54048 1
22048 1
16493 1
47298 1
50708 1
26958 1
38307 1
33000 1
no
33000 1
33000 1
33000 1
14143 1
33000 1
23657 1
12221 1
no
12093 1
12221 1
12157 1
12208 1
12221 1
12073 1
12221 1
12221 1
2
12221 1
5907 1
12221 1
11458 1
12221 1
12221 1
11073 1
12208...

result:

ok 191357 tokens

Test #12:

score: 5
Accepted
time: 527ms
memory: 39048kb

input:

12
100000
1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 ...

output:

64431 1
61681 1
2343 1
3
43431 1
43431 1
43431 1
34516 1
13424 1
43431 1
43431 1
43431 1
21116 1
15931 1
9601 1
43431 1
14281 1
34223 1
34223 1
34223 1
28030 1
28030 1
22280 1
22280 1
18969 1
12780 1
3
15719 1
15719 1
14280 1
9181 1
1767 1
3128 1
14280 1
15719 1
12455 1
14280 1
15719 1
12530 1
15719...

result:

ok 191360 tokens

Test #13:

score: 5
Accepted
time: 530ms
memory: 38980kb

input:

13
100000
1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 ...

output:

46658 1
52000 1
yes
17323 1
47823 1
47823 1
41266 1
14143 1
41266 1
27407 1
27407 1
no
13016 1
27407 1
18907 1
15987 1
19753 1
12073 1
19954 1
19954 1
4
19954 1
5907 1
19611 1
15987 1
19954 1
19954 1
15954 1
19954 1
8
14861 1
13
7407 1
4664 1
5959 1
19954 1
17204 1
2343 1
1
17204 1
14861 1
14477 1
1...

result:

ok 191356 tokens

Test #14:

score: 5
Accepted
time: 553ms
memory: 39620kb

input:

14
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 ...

output:

70250 1
28488 1
24024 1
9601 1
40253 1
14281 1
29750 1
25473 1
28738 1
29750 1
29750 1
29750 1
29750 1
29750 1
12780 1
0
29738 1
19344 1
14753 1
12297 1
2253 1
5378 1
14280 1
19344 1
12455 1
14280 1
19344 1
12530 1
19344 1
14753 1
19344 1
19344 1
8738 1
14753 1
19344 1
14753 1
19344 1
no
9323 1
1934...

result:

ok 191360 tokens

Test #15:

score: 5
Accepted
time: 535ms
memory: 39444kb

input:

15
100000
5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...

output:

no
26093 1
71500 1
19840 1
39524 1
41208 1
13823 1
71500 1
55111 1
1
47611 1
6840 1
35861 1
25622 1
47611 1
24860 1
15954 1
24860 1
2
24860 1
0
8340 1
7664 1
5959 1
24860 1
24860 1
2343 1
7
24860 1
24860 1
24860 1
19516 1
9610 1
24860 1
24860 1
24860 1
10204 1
12360 1
9601 1
24860 1
11281 1
24860 1
...

result:

ok 191357 tokens

Test #16:

score: 5
Accepted
time: 526ms
memory: 38824kb

input:

16
100000
1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 ...

output:

73250 1
73250 1
65250 1
17300 1
5
46378 1
46378 1
39293 1
15297 1
2253 1
5378 1
22245 1
46378 1
12455 1
32398 1
46378 1
26208 1
37676 1
37676 1
37676 1
37676 1
7675 1
37676 1
33926 1
33926 1
24426 1
no
9323 1
24426 1
19344 1
19344 1
7142 1
19344 1
19344 1
19344 1
no
6343 1
19344 1
10844 1
15987 1
15...

result:

ok 191358 tokens

Test #17:

score: 5
Accepted
time: 499ms
memory: 39388kb

input:

17
100000
5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 ...

output:

14991 1
14991 1
0
14991 1
14991 1
14991 1
14991 1
9321 1
14991 1
85 1
14991 1
14991 1
3389 1
14991 1
14991 1
8171 1
14991 1
14991 1
14991 1
7300 1
1
14991 1
3241 1
14991 1
14991 1
14991 1
3078 1
14991 1
14991 1
1
14991 1
14991 1
8171 1
13776 1
2319 1
no
11969 1
11156 1
11969 1
8324 1
8324 1
8324 1
y...

result:

ok 191357 tokens

Test #18:

score: 5
Accepted
time: 640ms
memory: 39776kb

input:

18
100000
4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 ...

output:

6664 1
10003 376
10003 376
10003 91
10003 91
1
10003 91
0
10003 91
4612 1
2737 1
10003 91
10003 91
2411 1
0
8229 1
8229 1
8229 1
7466 1
8229 1
7466 1
7466 1
7466 1
7466 1
5884 1
6935 1
7466 1
7125 1
7466 1
7466 1
7466 1
7466 1
7466 1
7125 1
7125 1
7125 1
7125 1
2156
7125 1
7125 1
7125 1
3133 1
1693 ...

result:

ok 191358 tokens

Test #19:

score: 5
Accepted
time: 487ms
memory: 38964kb

input:

19
100000
1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 ...

output:

5837 1
7018 1
6352 1
7018 1
6352 1
7018 1
1
7018 1
7018 1
7018 1
7018 1
7018 1
5837 1
5837 1
7018 1
6549 1
5837 1
5565 1
5837 1
4716 1
7018 1
5074 1
7018 1
4979 1
1478
6948 1
no
4716 1
6948 1
6948 1
6726 1
6948 1
5837 1
5837 1
5837 1
5837 1
4076 1
no
5837 1
5837 1
5837 1
85 1
5837 1
5837 1
4288 1
49...

result:

ok 191356 tokens

Test #20:

score: 5
Accepted
time: 302ms
memory: 39864kb

input:

20
100000
2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 ...

output:

1608 1
no
10002 1
4364 1
8329 1
10002 1
8329 1
10002 1
no
2957 1
10002 1
10002 1
10002 1
6406 1
10002 1
10002 1
10002 1
no
5719 1
10002 1
6406 1
6406 1
5719 1
3748 1
10002 1
10002 1
0
10002 1
3316 1
5719 1
5719 1
10002 1
10002 1
6162 1
10002 1
0
5719 1
0
4726 1
2804 1
2895 1
10002 1
10002 1
1223 1
1...

result:

ok 191355 tokens

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-05 05:12:48 | 开源项目