区间成段更新的问题,虽然明白了,但是却感觉写不出什么东西来,还是得多做点题加深感悟
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #include <map> #include <limits> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 100001; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; LL col[maxn<<2],sum[maxn<<2]; void PushUP(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void PushDown(int rt,int len){ if(col[rt]){ col[rt<<1]+=col[rt]; col[rt<<1|1]+=col[rt]; sum[rt<<1]+=(len-(len>>1))*col[rt]; sum[rt<<1|1]+=(len>>1)*col[rt]; col[rt]=0; } } void build(int l,int r,int rt){ col[rt]=0; if(l==r){ scanf("%lld",&sum[rt]); return ; } int m=(l+r)>>1; build(lson); build(rson); PushUP(rt); } void update(int L,int R,int c,int l,int r,int rt){ if(L<= l && R>=r){ col[rt]+=c; sum[rt]+=(r-l+1)*c; return ; } PushDown(rt,r-l+1); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if( R>m) update(L,R,c,rson); PushUP(rt); } LL query(int L,int R,int l,int r,int rt){ if(L<= l && R>=r){ return sum[rt]; } PushDown(rt,r-l+1); int m=(l+r)>>1; LL ret=0; if(L<=m) ret+=query(L,R,lson); if(R> m) ret+=query(L,R,rson); return ret; } int main(){ int N,M; SD(N),SD(M); build(1,N,1); while(M--){ char op[5]; scanf("%s",op); int L,R,c; if(op[0]=='Q'){ scanf("%d%d",&L,&R); printf("%lld\n",query(L,R,1,N,1)); }else{ scanf("%d%d%d",&L,&R,&c); update(L,R,c,1,N,1); } } }