fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /******** Fenwick: kth-alive ********/
  5. struct BIT {
  6.     int n; vector<int> f;
  7.     BIT(int n=0){init(n);}
  8.     void init(int N){ n=N; f.assign(n+1,0); }
  9.     void add(int i,int v){ for(; i<=n; i+=i&-i) f[i]+=v; }
  10.     int kth(int k){                 // smallest idx with pref >= k
  11.         int idx=0; int bit=1<<20;   // enough for n <= 1e6
  12.         while(bit){
  13.             int nxt=idx+bit;
  14.             if(nxt<=n && f[nxt]<k){ idx=nxt; k-=f[nxt]; }
  15.             bit>>=1;
  16.         }
  17.         return idx+1;
  18.     }
  19. };
  20.  
  21. /******** DSU ********/
  22. struct DSU{
  23.     vector<int> p, sz;
  24.     DSU(int n=0){init(n);}
  25.     void init(int n){ p.resize(n+1); iota(p.begin(),p.end(),0); sz.assign(n+1,1); }
  26.     int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
  27.     int unite(int a,int b){
  28.         a=find(a); b=find(b);
  29.         if(a==b) return a;
  30.         if(sz[a]<sz[b]) swap(a,b);
  31.         p[b]=a; sz[a]+=sz[b]; return a;
  32.     }
  33. };
  34.  
  35. /******** SegTree Max(h) ********/
  36. struct SegMax{
  37.     int n; vector<long long> mx;
  38.     SegMax(int N=0){init(N);}
  39.     void init(int N){ n=1; while(n<N) n<<=1; mx.assign(2*n,LLONG_MIN/4); }
  40.     void build(const vector<long long>& a){
  41.         int N=(int)a.size()-1;
  42.         for(int i=1;i<=N;i++) mx[n+i-1]=a[i];
  43.         for(int i=n-1;i>=1;i--) mx[i]=max(mx[i<<1],mx[i<<1|1]);
  44.     }
  45.     long long getMax(int l,int r){
  46.         if(l>r) return LLONG_MIN/4;
  47.         l+=n-1; r+=n-1; long long res=LLONG_MIN/4;
  48.         while(l<=r){
  49.             if(l&1) res=max(res,mx[l++]);
  50.             if(!(r&1)) res=max(res,mx[r--]);
  51.             l>>=1; r>>=1;
  52.         }
  53.         return res;
  54.     }
  55.     // first t in [L..R] with max(L..t) >= H; if none -> R+1
  56.     int firstPrefixAtLeast(int L,int R,long long H){
  57.         if(getMax(L,R) < H) return R+1;
  58.         int lo=L, hi=R, ans=R+1;
  59.         while(lo<=hi){
  60.             int mid=(lo+hi)>>1;
  61.             if(getMax(L,mid) >= H){ ans=mid; hi=mid-1; }
  62.             else lo=mid+1;
  63.         }
  64.         return ans;
  65.     }
  66.     // last t in [L..R] with max(t..R) >= H; if none -> L-1
  67.     int lastSuffixAtLeast(int L,int R,long long H){
  68.         if(getMax(L,R) < H) return L-1;
  69.         int lo=L, hi=R, ans=L-1;
  70.         while(lo<=hi){
  71.             int mid=(lo+hi)>>1;
  72.             if(getMax(mid,R) >= H){ ans=mid; lo=mid+1; }
  73.             else hi=mid-1;
  74.         }
  75.         return ans;
  76.     }
  77. };
  78.  
  79. /******** SegTree assign + sum (water level) ********/
  80. struct SegAssignSum{
  81.     int n;
  82.     struct Node{ long long sum,tag; int len; };
  83.     vector<Node> st;
  84.     SegAssignSum(int N=0){init(N);}
  85.     void init(int N){
  86.         n=1; while(n<N) n<<=1;
  87.         st.assign(2*n,{0,LLONG_MIN/4,0});
  88.         for(int i=n;i<2*n;i++) st[i].len=1;
  89.         for(int i=n-1;i>=1;i--) st[i].len=st[i<<1].len+st[i<<1|1].len;
  90.     }
  91.     void build(const vector<long long>& a){
  92.         int N=(int)a.size()-1;
  93.         for(int i=1;i<=N;i++) st[n+i-1].sum=a[i];
  94.         for(int i=n-1;i>=1;i--) st[i].sum=st[i<<1].sum+st[i<<1|1].sum;
  95.     }
  96.     void apply(int p,long long v){ st[p].sum=v*st[p].len; st[p].tag=v; }
  97.     void push(int p){
  98.         if(st[p].tag>LLONG_MIN/8){
  99.             apply(p<<1,st[p].tag); apply(p<<1|1,st[p].tag); st[p].tag=LLONG_MIN/4;
  100.         }
  101.     }
  102.     void pull(int p){ st[p].sum=st[p<<1].sum+st[p<<1|1].sum; }
  103.     void assign(int p,int L,int R,int l,int r,long long v){
  104.         if(l>R||r<L) return;
  105.         if(l<=L && R<=r){ apply(p,v); return; }
  106.         push(p);
  107.         int M=(L+R)>>1;
  108.         assign(p<<1,L,M,l,r,v);
  109.         assign(p<<1|1,M+1,R,l,r,v);
  110.         pull(p);
  111.     }
  112.     void assign(int l,int r,long long v){ if(l<=r) assign(1,1,n,l,r,v); }
  113.     long long sum(int p,int L,int R,int l,int r){
  114.         if(l>R||r<L) return 0;
  115.         if(l<=L && R<=r) return st[p].sum;
  116.         push(p);
  117.         int M=(L+R)>>1;
  118.         return sum(p<<1,L,M,l,r)+sum(p<<1|1,M+1,R,l,r);
  119.     }
  120.     long long sum(int l,int r){ if(l>r) return 0; return sum(1,1,n,l,r); }
  121. };
  122.  
  123. int main(){
  124.     ios::sync_with_stdio(false);
  125.     cin.tie(nullptr);
  126.  
  127.     int n; 
  128.     if(!(cin>>n)) return 0;
  129.     vector<long long> h(n+1);
  130.     for(int i=1;i<=n;i++) cin>>h[i];
  131.     vector<int> k(n);
  132.     for(int i=1;i<=n-1;i++) cin>>k[i];
  133.  
  134.     // DSU meta
  135.     DSU dsu(n+5);
  136.     vector<int> L(n+5), R(n+5);
  137.     vector<long long> mx(n+5), cap(n+5,0);
  138.     vector<int> limL(n+5), limR(n+5); // processed suffix/prefix borders
  139.  
  140.     for(int i=1;i<=n;i++){
  141.         dsu.p[i]=i; dsu.sz[i]=1;
  142.         L[i]=R[i]=i; mx[i]=h[i];
  143.         limL[i]=R[i]+1; // processed suffix from limL..R (empty)
  144.         limR[i]=L[i]-1; // processed prefix from L..limR (empty)
  145.     }
  146.  
  147.     // segment trees
  148.     SegMax segH(n+2); segH.build(h);
  149.     SegAssignSum segW(n+2); segW.init(n+2); segW.build(h); // water level (start = heights)
  150.  
  151.     auto mergeReps = [&](int a,int b)->int{
  152.         a=dsu.find(a); b=dsu.find(b);
  153.         long long H = min(mx[a], mx[b]);
  154.         long long extra = 0;
  155.  
  156.         // Pour into left segment 'a' from the right up to where prefix_max >= H
  157.         int t0 = segH.firstPrefixAtLeast(L[a], R[a], H);   // t0 in [L..R] or R+1
  158.         int l1 = max(t0, L[a]);
  159.         int r1 = min(limL[a]-1, R[a]);
  160.         if(l1 <= r1){
  161.             long long old = segW.sum(l1, r1);
  162.             segW.assign(l1, r1, H);
  163.             extra += H*1ll*(r1-l1+1) - old;
  164.             limL[a] = l1;            // now processed down to l1
  165.         }
  166.  
  167.         // Pour into right segment 'b' from the left up to where suffix_max >= H
  168.         int u0 = segH.lastSuffixAtLeast(L[b], R[b], H);    // u0 in [L..R] or L-1
  169.         int l2 = max(L[b], limR[b]+1);
  170.         int r2 = min(u0, R[b]);
  171.         if(l2 <= r2){
  172.             long long old = segW.sum(l2, r2);
  173.             segW.assign(l2, r2, H);
  174.             extra += H*1ll*(r2-l2+1) - old;
  175.             limR[b] = r2;            // now processed up to r2
  176.         }
  177.  
  178.         int c = dsu.unite(a,b);
  179.         L[c]=L[a]; R[c]=R[b];
  180.         mx[c]=max(mx[a],mx[b]);
  181.         cap[c]=cap[a]+cap[b]+extra;
  182.         limL[c]=limL[a]; limR[c]=limR[b];
  183.         return c;
  184.     };
  185.  
  186.     // maintain current order of segments with BIT + linked list
  187.     BIT bit(n);
  188.     vector<int> nxt(n+2), prv(n+2), alive(n+2,0), posRep(n+2);
  189.     bit.init(n);
  190.     for(int i=1;i<=n;i++){
  191.         alive[i]=1; bit.add(i,1);
  192.         nxt[i]=i+1; prv[i]=i-1;
  193.         posRep[i]=i;
  194.     }
  195.     nxt[0]=1; prv[n+1]=n;
  196.  
  197.     auto rightNeighbor = [&](int i){ return nxt[i]; };
  198.     auto erasePos = [&](int i){
  199.         int Lft=prv[i], Rgt=nxt[i];
  200.         nxt[Lft]=Rgt; prv[Rgt]=Lft;
  201.         if(alive[i]){ alive[i]=0; bit.add(i,-1); }
  202.     };
  203.  
  204.     for(int step=1; step<=n-1; ++step){
  205.         int kth = k[step];
  206.         int pos = bit.kth(kth);          // vị trí của đoạn thứ k
  207.         int posR = rightNeighbor(pos);   // đoạn k+1 (phải kề)
  208.         int u = posRep[pos];
  209.         int v = posRep[posR];
  210.  
  211.         int nr = mergeReps(u, v);
  212.         cout << cap[dsu.find(nr)] << '\n';
  213.  
  214.         posRep[pos] = dsu.find(nr);
  215.         erasePos(posR);                  // xóa đoạn k+1 khỏi trật tự
  216.     }
  217.     return 0;
  218. }
  219.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
8
9 1 8 1 5 2 3 6
3 3 1 3 3 2 1
stdout
copy 
-7
-7
-8
-1
-4
-11
-19
https://ideone.com/dFOA46
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!