線段樹

對于一段操作，操作后會在左端刪除一段數，在右端加上一段數

對于每一段操作，維護刪除個數del，增加個數ad，增加數的和sum

兩端區間合并時，考慮右區間的del會刪除左區間的ad

#include<iostream> #include<cstdio> #include<cstring> #define maxn 200005 using 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; }

轉載于:https://www.cnblogs.com/hunterxhunterl/p/7780661.html

總結

以上是生活随笔為你收集整理的weed的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。