Paste: test

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;typedef pair<int, int> PII;const int N = 100000+10;#define lson step << 1#define rson (step << 1) | 1#define INF 0x3f3f3f3fstruct Node {    int left,right;    ll sum,lazy;}L[N << 2];void pushUp(int step){    step >>= 1;    while(step){        L[step].sum = L[lson].sum + L[rson].sum;        step = (step >> 1);    }}void work(int step){    L[lson].lazy = -1;    L[rson].lazy = -1;    L[lson].sum = 0;    L[rson].sum = 0;    L[step].lazy = 0;}void pushDown(int step){    ll tmp = L[step].lazy;    if(L[lson].lazy == -1 && L[lson].left != L[lson].right){        work(lson);    }    if(L[rson].lazy == -1 && L[rson].left != L[rson].right){        work(rson);    }    L[lson].lazy += tmp;    L[rson].lazy += tmp;    L[lson].sum += (L[lson].right - L[lson].left + 1) * tmp;    L[rson].sum += (L[rson].right - L[rson].left + 1) * tmp;    L[step].lazy = 0;}void init(int step,int l,int r){    L[step].left = l;    L[step].right = r;    L[step].sum = 0;    L[step].lazy = 0;    if(l == r)        return;    int m = (l+r)>>1;    init(lson, l ,m);    init(rson, m+1, r);}ll querys(int step,int l,int r){    if(l > r)return 0;    if(L[step].lazy != 0){        if(L[step].lazy == -1){            L[lson].lazy = -1;            L[rson].lazy = -1;            L[lson].sum = 0;            L[rson].sum = 0;            L[step].lazy = 0;        }        else        pushDown(step);    }    if(L[step].left == l && L[step].right == r){        ll a = L[step].sum;        return a;    }    int m = (L[step].left + L[step].right) >> 1;    if( r < m ) {        return querys(lson, l, r);    }    if( l > m ) {        return querys(rson, l, r);    }    return querys(lson, l, m) + querys(rson, m+1, r);}void update(int step,int p,int w){    if(L[step].left == L[step].right){        L[step].sum = w;        pushUp(step);        return ;    }    int m = (L[step].left + L[step].right) >> 1;    if(p <= m)update(lson, p, w);    else update(rson, p, w);}void update(int step,int l,int r,ll w){    if(l > r)return ;    if(L[step].lazy != 0){        if(L[step].lazy == -1){            L[lson].lazy = -1;            L[rson].lazy = -1;            L[lson].sum = 0;            L[rson].sum = 0;            L[step].lazy = 0;        }        else{            pushDown(step);        }    }    if(L[step].left == l && L[step].right == r){        L[step].lazy += w;        L[step].sum += w * (r-l+1);        pushUp(step);        return;    }    int m = (L[step].left + L[step].right) >> 1;    if( r < m ) {        update(lson, l, r , w);        return;    }    if( l > m ){        update(rson, l, r , w);        return;    }    update(lson, l, m , w);    update(rson, m+1, r, w);    }void update2(int step,int l,int r,int w){    if(l > r)return ;    if(L[step].lazy != 0){        if(L[step].lazy == -1)return;        pushDown(step);    }    if(L[step].left == l && L[step].right == r){        L[step].lazy = -1;        L[step].sum = 0;        pushUp(step);        return;    }    int m = (L[step].left + L[step].right) >> 1;    if( r <= m ) {        update2(lson, l, r , w);        return;    }    if( l > m ){        update2(rson, l, r , w);        return;    }    update2(lson, l, m , w);    update2(rson, m+1, r, w);    }int n,Q;char buf[100];int main(){    while(~scanf("%d %d",&n,&Q)){        init(1, 1, n);        for(int i=1;i<=n;i++){            int x;            scanf("%d",&x);            update(1, i, x);        }        for(int i=0;i<Q;i++){            scanf("%s",buf);            int l,r;            scanf("%d%d",&l,&r);            if(buf[0] == 'r'){                ll ans = querys(1, l, r);                update2(1, l, r, 0);                printf("%lld\n",ans);            }else{                int w;                scanf("%d",&w);                update(1, l, r, w);            }        }    }    return 0;}/* 5 4 1 2 3 4 5 r 1 5 a 1 5 1 r 5 5*/