QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#757414	#4255. Sone2	I_be_wanna	100 ✓	640ms	41168kb	C++14	18.9kb	2024-11-17 06:52:10	2024-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;}*/

Source code, Language: C++14

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

Details

Tip: Click on the bar to expand more detailed information

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

result:

ok 191355 tokens

Extra Test:

score: 0

Extra Test Passed