AAhaoxuan's blog

By AAhaoxuan, history, 2 months ago, In English

My code's time complexity is right. But the constant is so large that it's TLE. Who can help me.


#include<cstdio> #define N 100005 #define NN 135 #define _ 800 int n,m,a[N],va[N],p[N],cnt[N],cnt2[NN]; struct kuai{ int v[NN],va[N],vc[NN],vac[N]; int r[N]; }k[NN]; inline void reco(){ for(int i=0;i<NN;i++)k[0].vc[i]=k[0].v[i]; for(int i=0;i<N;i++)k[0].vac[i]=k[0].va[i]; for(int i=1;i<NN;i++){ for(int j=0;j<NN;j++)k[i].vc[j]=k[i-1].vc[j]+k[i].v[j]; for(int j=0;j<N;j++)k[i].vac[j]=k[i-1].vac[j]+k[i].va[j]; } } inline void recoo(int x,int y){ k[0].vc[x/_]=k[0].v[x/_]; k[0].vc[y/_]=k[0].v[y/_]; k[0].vac[x]=k[0].va[x]; k[0].vac[y]=k[0].va[y]; for(int i=1;i<NN;i++){ k[i].vc[x/_]=k[i].v[x/_]+k[i-1].vc[x/_]; k[i].vc[y/_]=k[i].v[y/_]+k[i-1].vc[y/_]; k[i].vac[x]=k[i].va[x]+k[i-1].vac[x]; k[i].vac[y]=k[i].va[y]+k[i-1].vac[y]; } } int qu(int now){ if(p[now]!=now)p[now]=qu(p[now]); return p[now]; } bool bb[100005],b2[100005]; inline void rebuild(int id,int x,int y,int l,int r){//printf("(%d %d %d)",id,l,r); if(l>r)return; k[id].v[x/_]-=k[id].va[x]; k[id].va[x]=k[id].r[x]=0; for(int i=id*_;i<(id+1)*_&&i<=n;i++){ if(va[qu(i)]==x&&i>=l&&i<=r)bb[i]=1; else if(va[qu(i)]==x)b2[i]=1; } for(int i=id*_;i<(id+1)*_&&i<=n;i++){ if(bb[i]){ if(!k[id].r[y])k[id].r[y]=i,va[i]=y; p[i]=k[id].r[y]; k[id].v[y/_]++; k[id].va[y]++; bb[i]=0; } else if(b2[i]){ if(!k[id].r[x])k[id].r[x]=i,va[i]=x; p[i]=k[id].r[x]; k[id].v[x/_]++; k[id].va[x]++; b2[i]=0; } } } inline void read(int &a) { a=0;char c; while((c=getchar())<48); do a=(a<<3)+(a<<1)+(c^48); while((c=getchar())>47); } inline void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0'); } inline void gor(int ll,int rr,int x,int y){ for(int i=ll;i<=rr;i++){ if(k[i].r[y])p[k[i].r[x]]=k[i].r[y]; else k[i].r[y]=k[i].r[x],va[k[i].r[y]]=y; k[i].r[x]=0; int tt=k[i].va[x]; k[i].v[x/_]-=tt; k[i].va[x]-=tt; k[i].v[y/_]+=tt; k[i].va[y]+=tt; } } int main(){ // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); read(n),read(m); for(int i=1;i<=n;i++){ read(a[i]); int nowk=i/_,kn=a[i]/_; k[nowk].va[a[i]]++; k[nowk].v[kn]++; if(!k[nowk].r[a[i]]) k[nowk].r[a[i]]=i,va[i]=a[i]; p[i]=k[nowk].r[a[i]]; } reco(); while(m--){ int op,l,r,K,x,y; read(op),read(l),read(r); if(op==2){ read(K); bool b=0; int ll=-1,rr=-1; for(int i=l;i<=r;i++){ if(i%_==0){ ll=i/_; break; } //printf("^%d",va[qu(i)]); cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++; if(i==r)b=1; } if(!b)for(int i=r;i>=l;i--){ if((i+1)%_==0){ rr=i/_; break; } cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++; } if((ll==-1||rr==-1)||ll>rr){ int dd=0,sum=0; for(int i=0;i<NN;i++){ if(sum+cnt2[i]>=K)break; sum+=cnt2[i];dd+=_; } for(;;dd++){ if(sum+cnt[dd]>=K){ write(dd); break; } sum+=cnt[dd]; } } else{ int dd=0,sum=0; for(int i=0;i<NN;i++){ if(sum+cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i]>=K)break; sum+=cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i];dd+=_; } for(;dd<N;dd++){ if(sum+cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd]>=K){ write(dd); break; } sum+=cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd]; } } for(int i=l;i<=r;i++){ if(i%_==0)break; cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0; } for(int i=r;i>=l;i--){ if((i+1)%_==0)break; cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0; } putchar('\n'); } else{ read(x),read(y); if(x==y)continue; int ll=(l-1)/_+1,rr=(r+1)/_-1; if(ll>rr+1){ rebuild(rr+1,x,y,l,r); recoo(x,y); continue; } rebuild(ll-1,x,y,l,ll*_-1); rebuild(rr+1,x,y,(rr+1)*_,r); gor(ll,rr,x,y); recoo(x,y); } } }

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By AAhaoxuan, history, 2 months ago, In English

Given a sequence $$$( A )$$$ , where each element $$$( A_i )$$$ is a randomly chosen integer from $$$( 0 )$$$ to $$$( 2^k - 1 )$$$ , what is the probability that there exists a subsequence of $$$( A )$$$ whose XOR sum is equal to $$$0$$$ ?

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it