区间修改 查询等 详见注释
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<set> #include<string> #include<stack> #include<map> using namespace std; const int INF=0x3f3f3f3f; typedef pair<int, int> P; typedef long long ll; #define fi first/ #define se scond #define me(x) memset(x, -1, sizeof(x)) #define mem(x) memset(x, 0, sizeof(x)) #define sc(x) scanf("%lld", &x) #define sca(x,y) scanf("%lld%lld", &x, &y) #define pr(x) printf("%lld ", x) #define pri(x) printf("%lld ", x) #define fo(i,n) for(i=0; i<n; i++) #define rfo(i,n) for(i=n-1; i>=0; i--) #define N 2000000 + 5 ll tree[N*4]; ll lazy[N*4]; void push_up(ll rt) { tree[rt]=tree[rt<<1] + tree[rt<<1|1]; } //向下传lazy标记 void push_down(ll rt, ll len) { lazy[rt<<1] += lazy[rt]; //左右子树标记更新 lazy[rt<<1|1] += lazy[rt]; //左右子树数值更新 tree[rt<<1] += (len-(len>>1)) * lazy[rt];//奇数长度 左子树更长 tree[rt<<1|1] += (len>>1) * lazy[rt]; lazy[rt]=0;//取消该节点标记 } /* //建树 1 2 3 4 5 6 7 8 9 12 13 e.g. n=6 data:1 2 3 4 5 6 tree[8]=1 tree[9]=2 tree[5]=3 tree[12]=4 tree[13]=5 tree[7]=6 */ void build(ll rt, ll l, ll r) { if(l==r) { cin>>tree[rt]; return ; } ll m=r+l >> 1; build(rt<<1, l, m); build(rt<<1|1, m+1, r); push_up(rt); //向上更新父节点 } //单点更新 /* void update(ll rt, ll l, ll r, ll p, ll x, ll k) { if(l==r) { if(k==1) tree[rt]+=x; else tree[rt]-=x; return ; } ll m = l+r >>1; if(p<=m) update(rt<<1, l, m, p, x, k); else update(rt<<1|1, m+1, r, p, x, k); push_up(rt); } */ //区间更新 void Update(ll rt, ll l, ll r, ll p, ll L, ll R) { if(L<=l && r<=R) //缩到指定区间 更新 { tree[rt]+=(r-l+1)*p; lazy[rt]+=p; //更新标记 return ; } if(lazy[rt]) push_down(rt, r-l+1); //及时下传标记 ll m= r+l >> 1; if(L<=m) Update(rt<<1, l, m, p, L, R); if(R>m) Update(rt<<1|1, m+1, r, p, L, R); push_up(rt); } //区间查询 ll query(ll rt, ll l, ll r, ll L, ll R) { if(L<=l && r<=R) { return tree[rt]; } ll s=0; if(lazy[rt]) push_down(rt,r-l+1); //及时下传标记 ll m = r+l >>1; if(L<=m) s+=query(rt<<1, l, m, L, R); if(R>m) s+=query(rt<<1|1, m+1, r, L, R); return s; } int main() { ll i, j , k; ll n, m; ll L, R, p; cin>>n>>m; build(1,1,n); //for(i=1; i<=20; i++) cout<<i<<' '<<tree[i]<<endl; fo(i,m) { char c; cin>>c; if(c=='Q') { cin>>L>>R; if(L>R) swap(L,R); k=query(1,1,n,L,R); cout<<k<<endl; } else if(c=='C') { cin>>L>>R; if(L>R) swap(L,R); cin>>p; Update(1,1,n,p,L,R); } } }