有人不会裸线段树

有人没有pushdown调了两小时裸线段树

早该414了

L (codeforces.com)

题意：

给定一段数，操作有区间加和单点锁定某一值，如果某一位置被锁定，那么区间加不包含这个位置，询问为区间和。

思路：

对于修改查询的DS题，有个普遍的思路是：

先去确定一些询问需要维护的东西

然后再去看修改操作对询问要维护的东西的贡献

对于这道题，有四种操作：

询问只有一种，询问区间和

然后去看修改：每次修改都是把所有s=1的值区间加x

那么这种操作对区间和的贡献就是这个区间的s=1的个数*x

因此可以得出我们还需要维护区间s=1的个数

然后再去想，修改操作对区间cnt的影响

只有1和2操作会对cnt有影响

然后就可以开始写了，我们只需维护区间和和区间s=1的cnt就行了

然后就是pushdown操作

在pushdown操作的时候，往左区间和右区间分别加上对应比例的贡献

Code：

#include 
using namespace std;
#define int long long
using i64 = long long;
const int mxn=1e6+10;
const int mxe=1e6+10;
struct ty{int sum,cnt,lazy;
}tree[mxe<<2];
int n,Q,op,x,l,r;
int a[mxn],s[mxn];
void pushup(int rt){tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;tree[rt].cnt=tree[rt<<1].cnt+tree[rt<<1|1].cnt;
}
void pushdown(int rt){tree[rt<<1].lazy+=tree[rt].lazy;tree[rt<<1|1].lazy+=tree[rt].lazy;tree[rt<<1].sum+=tree[rt<<1].cnt*tree[rt].lazy;tree[rt<<1|1].sum+=tree[rt<<1|1].cnt*tree[rt].lazy;tree[rt].lazy=0;
}
void build(int rt,int l,int r){tree[rt].cnt=r-l+1;if(l==r){tree[rt].sum=a[l];tree[rt].cnt=s[l];return;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);
}
void modify1(int rt,int l,int r,int x){if(s[x]) tree[rt].cnt++;else tree[rt].cnt--;if(l==r){return;}pushdown(rt);int mid=l+r>>1;if(x<=mid) modify1(rt<<1,l,mid,x);else modify1(rt<<1|1,mid+1,r,x);pushup(rt);
}
int query1(int rt,int l,int r,int x,int y){if(x<=l&&r<=y){return tree[rt].cnt;}int mid=l+r>>1;int res=0;if(x<=mid) res+=query1(rt<<1,l,mid,x,y);if(y>mid) res+=query1(rt<<1|1,mid+1,r,x,y);return res;
}
void modify2(int rt,int l,int r,int x,int y,int t){if(x<=l&&r<=y){tree[rt].lazy+=t;tree[rt].sum+=tree[rt].cnt*t;return;}if(tree[rt].lazy!=0) pushdown(rt);int mid=l+r>>1;if(x<=mid) modify2(rt<<1,l,mid,x,y,t);if(y>mid) modify2(rt<<1|1,mid+1,r,x,y,t);pushup(rt);
}
int query2(int rt,int l,int r,int x,int y){if(x<=l&&r<=y){return tree[rt].sum;}if(tree[rt].lazy!=0) pushdown(rt);int mid=l+r>>1;int res=0;if(x<=mid) res+=query2(rt<<1,l,mid,x,y);if(y>mid) res+=query2(rt<<1|1,mid+1,r,x,y);return res;
}
void solve(){cin>>n>>Q;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>s[i];build(1,1,n);while(Q--){cin>>op;if(op==1){cin>>x;s[x]^=1;modify1(1,1,n,x);}else if(op==2){cin>>x;s[x]^=1;modify1(1,1,n,x);}else if(op==3){cin>>l>>r>>x;modify2(1,1,n,l,r,x);}else{cin>>l>>r;cout<>__;while(__--)solve();return 0;
}