Submission #1049504

#TimeUsernameProblemLanguageResultExecution timeMemory
1049504PoonYaPatDiversity (CEOI21_diversity)C++14
64 / 100
7067 ms243296 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; //sl : increase from l //sr : increase from r const int mx=300000,MID=150000,sq=1350; struct NN { ll sum,sl,sr,cnt; } s[1<<21]; int ccnt[mx+5],posi[mx+5],num[mx+5]; NN merge(NN a, NN b) { NN res; res.sum=a.sum+b.sum; res.cnt=a.cnt+b.cnt; res.sl=a.sl+a.cnt*b.sum+b.sl; res.sr=b.sr+b.cnt*a.sum+a.sr; return res; } ll fast2_query(int l, int r, int idx, int x) { if (x>r) return s[idx].sr+s[idx].sum*(ll)(x-r); if (x<l) return s[idx].sl+s[idx].sum*(ll)(l-x); if (l==r) { s[idx]={ccnt[l],ccnt[l],ccnt[l],1}; return ccnt[l]; } int mid=(l+r)/2; ll res1=fast2_query(l,mid,2*idx,x); ll res2=fast2_query(mid+1,r,2*idx+1,x); s[idx]=merge(s[2*idx],s[2*idx+1]); return res1+res2; } int level[mx+5],have[mx+5],idx_seq=-1; //range of box that has been used vector<int> seq; deque<int> dq[mx+5]; ll ans=0; void sw(int a, int b) { swap(num[a],num[b]); posi[num[a]]=a; posi[num[b]]=b; } void add(int val) { if (!have[val]) { ++idx_seq; int pos=seq[idx_seq]; //the position of the seg-tree to be added ccnt[pos]=1; posi[val]=pos; num[pos]=val; dq[1].push_back(pos); ans+=fast2_query(1,mx,1,pos); } else { int pos=posi[val], cnt=ccnt[pos]; //increase from cnt to cnt+1 int max_pos=dq[cnt].front(); sw(pos,max_pos); //increase from cnt to cnt+1 dq[cnt].pop_front(); dq[cnt+1].push_back(max_pos); ++ccnt[max_pos]; ans+=fast2_query(1,mx,1,max_pos); } ++have[val]; } void del(int val) { int pos=posi[val], cnt=ccnt[pos]; int min_pos=dq[cnt].back(); sw(pos,min_pos); dq[cnt].pop_back(); if (cnt==1) --idx_seq; else dq[cnt-1].push_front(min_pos); --ccnt[min_pos]; ans-=(fast2_query(1,mx,1,min_pos)+1); --have[val]; } int n,q,a[mx+5]; struct Query { int l,r,idx; bool operator<(Query other) const { return pii(l/sq,((l/sq)&1) ? -r : +r)<pii(other.l/sq,((other.l/sq)&1) ? -other.r : +other.r); } }; vector<Query> ques; ll Ans[50005]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int ll=MID,rr=MID; level[MID]=0; seq.push_back(MID); for (int i=1; i<mx; ++i) { if (i%2==0) level[--ll]=i, seq.push_back(ll); else level[++rr]=i, seq.push_back(rr); } cin>>n>>q; for (int i=0; i<n; ++i) cin>>a[i]; for (int i=0; i<q; ++i) { int l,r; cin>>l>>r; ques.push_back({--l,--r,i}); } sort(ques.begin(),ques.end()); int cur_l=0; int cur_r=-1; for (auto q : ques) { while (cur_l>q.l) add(a[--cur_l]); while (cur_r<q.r) add(a[++cur_r]); while (cur_l<q.l) del(a[cur_l++]); while (cur_r>q.r) del(a[cur_r--]); Ans[q.idx]=ans; } for (int i=0; i<q; ++i) cout<<Ans[i]<<"\n"; }
#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...