线段树
对于一段操作，操作后会在左端删除一段数，在右端加上一段数
对于每一段操作，维护删除个数del，增加个数ad，增加数的和sum
两端区间合并时，考虑右区间的del会删除左区间的ad
#include#include #include #define maxn 200005using namespace std;int m,Q;struct Calc{ int k,v;}q[maxn],tmp;struct Tree{ int l,r,ad,del,sum;}b[maxn*4];int find(int z,int x){ if(!x) return b[z].sum; if(x>=b[z].ad) return 0; int ls=(z<<1),rs=((z<<1)|1); if(x<=b[rs].ad) return b[z].sum-b[rs].sum+find(rs,x); else return find(ls,x-b[rs].ad+b[rs].del);} void pushup(int z){ b[z].del=b[z<<1].del+max(0,b[z<<1|1].del-b[z<<1].ad); b[z].ad=b[z<<1|1].ad+max(0,b[z<<1].ad-b[z<<1|1].del); b[z].sum=b[z<<1|1].sum+find(z<<1,b[z<<1|1].del);}void build(int l,int r,int z){ b[z].l=l; b[z].r=r; if(l==r) { b[z].ad=b[z].sum=b[z].del=0; if(!q[l].k){ b[z].ad=1; b[z].sum=q[l].v; } else b[z].del=q[l].v; return ; } int mid=(l+r)>>1; build(l,mid,z<<1); build(mid+1,r,z<<1|1); pushup(z);} void maintain(int x,int z){ if(b[z].l==b[z].r) { b[z].ad=b[z].sum=b[z].del=0; if(!tmp.k){ b[z].ad=1; b[z].sum=tmp.v; } else b[z].del=tmp.v; return ; } int mid=(b[z].l+b[z].r)>>1; if(x<=mid) maintain(x,z<<1); else maintain(x,z<<1|1); pushup(z);} inline int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x;}int main(){ int x,y,z; scanf("%d%d",&m,&Q); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].k,&q[i].v); } build(1,m,1); for(int i=1;i<=Q;i++) { x=read(); tmp.k=read(); tmp.v=read(); maintain(x,1); printf("%d\n",b[1].sum); } return 0;}