#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; #define fi first #define se second #define tm aespa int n,m,q; int dn[N],pn[N]; int dm[N],tm[N]; int dq[N],pq[N],tq[N]; ll w[N],ans[N]; int d;//d <= 342000 int Bd_sz,Bm_sz; vector<int>maj_q[N]; vector<int>min_q[N]; ll wj[N],bwj[N]; ll wi[N],bwi[N]; int main(){ ios::sync_with_stdio(false);cin.tie(0); cin >> n >> m >> q; for(int i=1; i<=n ;i++){ cin >> pn[i];dn[i]=i; } int ptr_m=0,ptr_q=0; for(int i=1; i<=m+q ;i++){ int tp;cin >> tp; if(tp==1){ ++ptr_m; cin >> dm[ptr_m] >> w[ptr_m]; tm[ptr_m]=ptr_m; } else{ ++ptr_q; cin >> dq[ptr_q] >> pq[ptr_q]; tq[ptr_q]=ptr_m; } } {//process pos vector<pair<int,int> >haha(n+q); for(int i=1; i<=n ;i++) haha[i-1]={-pn[i],i}; for(int i=1; i<=q ;i++) haha[i+n-1]={-pq[i],n+i}; sort(haha.begin(),haha.end()); int ptr_n=0; vector<int>nd(n+1); for(auto c:haha){ if(c.se<=n){ nd[++ptr_n]=dn[c.se]; pn[ptr_n]=ptr_n; } else{ pq[c.se-n]=ptr_n; } } for(int i=1; i<=n ;i++) dn[i]=nd[i]; } {//process days, should be <=342000 vector<int>hv(n+2,0); hv[1]=1; for(int i=1; i<=m ;i++) hv[dm[i]+1]=1; for(int i=1; i<=q ;i++) hv[dq[i]+1]=1; for(int i=1; i<=n ;i++) hv[i]+=hv[i-1]; d=hv[n]; for(int i=1; i<=n ;i++) dn[i]=hv[dn[i]]; for(int i=1; i<=m ;i++) dm[i]=hv[dm[i]]; for(int i=1; i<=q ;i++) dq[i]=hv[dq[i]]; } {//Compute block sizes Bd_sz=1; while(Bd_sz<d/Bd_sz) Bd_sz++; Bm_sz=1; while(2LL*q*Bm_sz*Bm_sz<5LL*n*m && Bm_sz<=m) ++Bm_sz; } for(int i=1; i<=q ;i++){ if(pq[i]!=0) maj_q[tq[i]/Bm_sz].push_back(i); min_q[pq[i]].push_back(i); } auto cmp = [&](int k1,int k2){ return pq[k1]<pq[k2]; }; for(int b=1; b<=m/Bm_sz ;b++){//annoying term dm/Bm_sz, get rid? int jl=(b-1)*Bm_sz+1; int jr=min(m,b*Bm_sz); for(int j=jl; j<=jr ;j++){//+w[j] on [1..dm[j]] int cur_b=dm[j]/Bd_sz; for(int r=1; r<=cur_b ;r++) bwj[r]+=w[j]; for(int r=(cur_b)*Bd_sz+1; r<=dm[j] ;r++) wj[r]+=w[j]; } if(maj_q[b].empty()) continue; sort(maj_q[b].begin(),maj_q[b].end(),cmp); int ptr_q=0; for(int i=1; i<=n ;i++){//compute major n*m/Bm_sz + q*sqrt(d) int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; ll frog=wj[dn[i]]+bwj[cur_b]; wi[dn[i]]+=frog; bwi[cur_b]+=frog; while(ptr_q<maj_q[b].size() && pq[maj_q[b][ptr_q]]==i){ int k=maj_q[b][ptr_q++]; int cur_b=dq[k]/Bd_sz; for(int r=1; r<=cur_b ;r++) ans[k]+=bwi[r]; for(int r=cur_b*Bd_sz+1; r<=dq[k] ;r++) ans[k]+=wi[r]; } } for(int i=1; i<=n ;i++){ int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; wi[dn[i]]=0; bwi[cur_b]=0; } } for(int r=1; r<=d ;r++) wi[r]=bwi[r]=0; int b_tot=(d+Bd_sz-1)/Bd_sz; for(int i=1; i<=n ;i++){//compute minor n*sqrt(d) + q*Bm_sz int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; for(int r=cur_b+1; r<=b_tot ;r++) bwi[r]++; for(int r=dn[i]; r<=cur_b*Bd_sz ;r++) wi[r]++; for(auto k:min_q[i]){//compute minor q*Bm_sz //cout << "hi " << i << ' ' << k << ' ' << pq[k] << ' ' << tq[k] << endl; int cur_b=tq[k]/Bm_sz; for(int j=cur_b*Bm_sz+1; j<=tq[k] ;j++){ int dd=min(dm[j],dq[k]); ans[k]+=(bwi[(dd+Bd_sz-1)/Bd_sz]+wi[dd])*w[j]; } } } for(int i=1; i<=q ;i++) cout << ans[i] << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; #define fi first #define se second #define tm aespa int n,m,q; int dn[N],pn[N]; int dm[N],tm[N]; int dq[N],pq[N],tq[N]; ll w[N],ans[N]; int d;//d <= 342000 int Bd_sz,Bm_sz; vector<int>maj_q[N]; vector<int>min_q[N]; ll wj[N],bwj[N]; ll wi[N],bwi[N]; int main(){ ios::sync_with_stdio(false);cin.tie(0); cin >> n >> m >> q; for(int i=1; i<=n ;i++){ cin >> pn[i];dn[i]=i; } int ptr_m=0,ptr_q=0; for(int i=1; i<=m+q ;i++){ int tp;cin >> tp; if(tp==1){ ++ptr_m; cin >> dm[ptr_m] >> w[ptr_m]; tm[ptr_m]=ptr_m; } else{ ++ptr_q; cin >> dq[ptr_q] >> pq[ptr_q]; tq[ptr_q]=ptr_m; } } {//process pos vector<pair<int,int> >haha(n+q); for(int i=1; i<=n ;i++) haha[i-1]={-pn[i],i}; for(int i=1; i<=q ;i++) haha[i+n-1]={-pq[i],n+i}; sort(haha.begin(),haha.end()); int ptr_n=0; vector<int>nd(n+1); for(auto c:haha){ if(c.se<=n){ nd[++ptr_n]=dn[c.se]; pn[ptr_n]=ptr_n; } else{ pq[c.se-n]=ptr_n; } } for(int i=1; i<=n ;i++) dn[i]=nd[i]; } {//process days, should be <=342000 vector<int>hv(n+2,0); hv[1]=1; for(int i=1; i<=m ;i++) hv[dm[i]+1]=1; for(int i=1; i<=q ;i++) hv[dq[i]+1]=1; for(int i=1; i<=n ;i++) hv[i]+=hv[i-1]; d=hv[n]; for(int i=1; i<=n ;i++) dn[i]=hv[dn[i]]; for(int i=1; i<=m ;i++) dm[i]=hv[dm[i]]; for(int i=1; i<=q ;i++) dq[i]=hv[dq[i]]; } {//Compute block sizes Bd_sz=1; while(Bd_sz<d/Bd_sz) Bd_sz++; Bm_sz=1; while(2LL*q*Bm_sz*Bm_sz<5LL*n*m && Bm_sz<=m) ++Bm_sz; } for(int i=1; i<=q ;i++){ if(pq[i]!=0) maj_q[tq[i]/Bm_sz].push_back(i); min_q[pq[i]].push_back(i); } auto cmp = [&](int k1,int k2){ return pq[k1]<pq[k2]; }; for(int b=1; b<=m/Bm_sz ;b++){//annoying term dm/Bm_sz, get rid? int jl=(b-1)*Bm_sz+1; int jr=min(m,b*Bm_sz); for(int j=jl; j<=jr ;j++){//+w[j] on [1..dm[j]] int cur_b=dm[j]/Bd_sz; for(int r=1; r<=cur_b ;r++) bwj[r]+=w[j]; for(int r=(cur_b)*Bd_sz+1; r<=dm[j] ;r++) wj[r]+=w[j]; } if(maj_q[b].empty()) continue; sort(maj_q[b].begin(),maj_q[b].end(),cmp); int ptr_q=0; for(int i=1; i<=n ;i++){//compute major n*m/Bm_sz + q*sqrt(d) int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; ll frog=wj[dn[i]]+bwj[cur_b]; wi[dn[i]]+=frog; bwi[cur_b]+=frog; while(ptr_q<maj_q[b].size() && pq[maj_q[b][ptr_q]]==i){ int k=maj_q[b][ptr_q++]; int cur_b=dq[k]/Bd_sz; for(int r=1; r<=cur_b ;r++) ans[k]+=bwi[r]; for(int r=cur_b*Bd_sz+1; r<=dq[k] ;r++) ans[k]+=wi[r]; } } for(int i=1; i<=n ;i++){ int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; wi[dn[i]]=0; bwi[cur_b]=0; } } for(int r=1; r<=d ;r++) wi[r]=bwi[r]=0; int b_tot=(d+Bd_sz-1)/Bd_sz; for(int i=1; i<=n ;i++){//compute minor n*sqrt(d) + q*Bm_sz int cur_b=(dn[i]+Bd_sz-1)/Bd_sz; for(int r=cur_b+1; r<=b_tot ;r++) bwi[r]++; for(int r=dn[i]; r<=cur_b*Bd_sz ;r++) wi[r]++; for(auto k:min_q[i]){//compute minor q*Bm_sz //cout << "hi " << i << ' ' << k << ' ' << pq[k] << ' ' << tq[k] << endl; int cur_b=tq[k]/Bm_sz; for(int j=cur_b*Bm_sz+1; j<=tq[k] ;j++){ int dd=min(dm[j],dq[k]); ans[k]+=(bwi[(dd+Bd_sz-1)/Bd_sz]+wi[dd])*w[j]; } } } for(int i=1; i<=q ;i++) cout << ans[i] << '\n'; } |