Submission #1097459

#TimeUsernameProblemLanguageResultExecution timeMemory
1097459alexander707070Diversity (CEOI21_diversity)C++14
64 / 100
1000 ms116216 KiB
#include<bits/stdc++.h> #define MAXN 300007 using namespace std; const long long bucket_sz=500; long long n,a[MAXN],q; long long br[MAXN],maxs,l,r,p[MAXN],len,bucket[MAXN],pos[MAXN],nxt[MAXN][20],pr[MAXN][20],w[MAXN]; long long ans,mult,sum,s[MAXN],res[MAXN]; struct Fenwick{ long long fenwick[MAXN]; void update(long long x,long long val){ while(x<=maxs){ fenwick[x]+=val; x+=(x & (-x)); } } long long getsum(long long x){ long long res=0; while(x>=1){ res+=fenwick[x]; x^=(x & (-x)); } return res; } }pref,suff,sumpref,sumsuff; struct query{ long long l,r,id; inline friend bool operator < (query fr,query sc){ if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l]; return fr.r<sc.r; } }qs[MAXN]; long long calc(long long x){ return s[x] * ( pref.getsum(x-1)-sumpref.getsum(x-1)*(maxs-x+1) + suff.getsum(maxs-x)-sumsuff.getsum(maxs-x)*x ); } void change(long long x,long long val){ ans-=calc(x); ans-=s[x]*(s[x]-1)/2+s[x]; s[x]+=val; sumpref.update(x,val); sumsuff.update(maxs-x+1,val); pref.update(x,(maxs-x+2)*val); suff.update(maxs-x+1,(x+1)*val); ans+=calc(x); ans+=s[x]*(s[x]-1)/2+s[x]; } void calcdp(){ for(long long j=1;j<20;j++){ for(long long i=1;i<=n;i++){ nxt[i][j]=nxt[nxt[i][j-1]][j-1]; pr[i][j]=pr[pr[i][j-1]][j-1]; } } } void add(long long x){ br[x]++; change(pos[x],1); long long z=pos[x]; for(long long s=19;s>=0;s--){ if(br[w[nxt[z][s]]]<br[x])z=nxt[z][s]; } long long y=w[z]; if(x!=y){ change(pos[x],br[y]-br[x]); change(pos[y],br[x]-br[y]); swap(w[pos[x]],w[pos[y]]); swap(pos[x],pos[y]); } } void rem(long long x){ br[x]--; change(pos[x],-1); long long z=pos[x]; for(long long s=19;s>=0;s--){ if(pr[z][s]!=0 and br[w[pr[z][s]]]>br[x])z=pr[z][s]; } long long y=w[z]; if(x!=y){ change(pos[x],br[y]-br[x]); change(pos[y],br[x]-br[y]); swap(w[pos[x]],w[pos[y]]); swap(pos[x],pos[y]); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(long long i=1;i<=n;i++){ cin>>a[i]; maxs=max(maxs,a[i]); bucket[i]=i/bucket_sz; } for(long long i=1;i<=maxs;i++)pos[i]=w[i]=i; for(long long i=1;i<=maxs;i++){ if(i<=maxs/2)nxt[i][0]=maxs-i+1; else nxt[i][0]=maxs-i+2; } if(maxs%2==1)nxt[maxs/2+1][0]=maxs/2+1; for(long long i=1;i<=maxs;i++)pr[nxt[i][0]][0]=i; calcdp(); for(long long i=1;i<=q;i++){ cin>>qs[i].l>>qs[i].r; qs[i].id=i; } sort(qs+1,qs+q+1); l=1; r=0; for(long long i=1;i<=q;i++){ while(r<qs[i].r){ r++; add(a[r]); } while(l>qs[i].l){ l--; add(a[l]); } while(r>qs[i].r){ rem(a[r]); r--; } while(l<qs[i].l){ rem(a[l]); l++; } res[qs[i].id]=ans; } for(long long i=1;i<=q;i++){ cout<<res[i]<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...