Codeforces 923 B. Producing Snow

http://codeforces.com/contest/923/problem/B

 

题意：

有n天，每天产生一堆体积为Vi的雪，每天所有雪堆体积减少Ti

当某一堆剩余体积vi<=Ti时，体积减少vi，雪堆消失

codeforces网址、问每天所有雪堆一共减少多少体积

 

fhq treap

把<=Ti的分裂出来，计算和

>Ti 的 Ti*个数

 

#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;#define N 100005int a[N],t[N];
int id[N];int tot;
int root,fa[N],ch[N][2],pri[N];
int siz[N],val[N];
long long sum[N],tag[N];void read(int &x)
{x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}int newnode(int v)
{siz[++tot]=1;sum[tot]=v;val[tot]=v;pri[tot]=id[tot];return tot;
}void update(int x)
{siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}void tagging(int x,int y)
{val[x]-=y;sum[x]-=1LL*siz[x]*y;tag[x]+=y;
}void down(int x)
{if(ch[x][0]) tagging(ch[x][0],tag[x]);if(ch[x][1]) tagging(ch[x][1],tag[x]);tag[x]=0;
}void split(int now,int k,int &x,int &y)
{if(!now) x=y=0;else{if(tag[now]) down(now);if(val[now]<=k){x=now;split(ch[now][1],k,ch[x][1],y);}else{y=now;split(ch[now][0],k,x,ch[y][0]);}update(now);}
}int merge(int x,int y)
{if(x && tag[x]) down(x);if(y && tag[y]) down(y);if(!x || !y)  return x+y;if(pri[x]<pri[y]){ch[x][1]=merge(ch[x][1],y);update(x);return x;}else{ch[y][0]=merge(x,ch[y][0]);update(y);return y;}
}int main()
{int n;read(n);for(int i=1;i<=n;++i) read(a[i]);for(int i=1;i<=n;++i) read(t[i]);for(int i=1;i<=n+2;++i) id[i]=i;random_shuffle(id+1,id+n+1);int x,y,z;for(int i=1;i<=n;++i) {//insert(a[i]);
        split(root,a[i],x,y);root=merge(merge(x,newnode(a[i])),y);split(root,t[i],x,y);cout<<sum[x]+1LL*t[i]*siz[y]<<' ';if(y) tagging(y,t[i]);root=y;}return 0;
}