data-structure - Rip-Van-Winkle

/*
 * DATE : 2017-07-01
 * Algo :
*/
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(long long i=0; i < n ; i++ )
#define REP(i,n)                for(long long i=0; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define di(x)                   int x; input(x)
#define in(x)                   input(x)
#define in2(x,y)                in(x),in(y)
#define in3(x,y,z)              in(x),in2(y,z)
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("in.txt","r",stdin)
#define WRITE                   freopen("out.txt","w",stdout)
template<class T> inline void input(T &x) {
    register char c = getchar();x = 0;
    int neg = 0;
    for(; ((c<48 || c>57) && c != '-'); c = getchar());
    if(c=='-'){neg = 1;c = getchar();}
    for(; c>47 && c<58 ; c = getchar()){x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x = -x;
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/
const int N = 250005;
long long T[5*N], P[5*N],C[5*N], V[5*N];
long long calc(long long  x,long long y)
{
    return y*(y+1)/2 - (x*(x-1)/2);
}
void upd(int n,int b,int e,int i,int j,int k,long long s)
{
    if(C[n] != C[0]) {
        V[n] = (e-b+1) * C[n];
        if(b!=e) {
            T[lc] = T[rc] = 0;
            P[lc] = P[rc] = 0;
            C[lc] = C[rc] = C[n];
        }
        C[n] = C[0];
    }
    if(T[n] || P[n]) {
        V[n] += calc(b,e) * T[n] + (e-b+1) *  P[n];
        if(b !=e) {
            T[lc] += T[n];
            T[rc] += T[n];
            P[lc] += P[n];
            P[rc] += P[n];
        }
        P[n] = 0;
        T[n] = 0;
    }
    if(b>j||e<i) return;
    if(b>=i&&e<=j){
        if(k==0){
            V[n] = (e-b+1) * s;
            if(b!=e) {
                T[lc] = T[rc] = 0;
                P[lc] = P[rc] = 0;
                C[lc] = C[rc] = s;
            }
        }
        else {
            V[n] += k * calc(b,e) + (e-b+1) * s;
            if(b !=e ) {
                T[lc] += k;
                T[rc] += k;
                P[lc] += s;
                P[rc] += s;
            }
        }
        return;
    }
    int mid = (b+e)/2;
    upd(lc,b,mid,i,j,k,s);
    upd(rc,mid+1,e,i,j,k,s);
    V[n] = V[lc] + V[rc];

}

long long query(int n,int b,int e,int i,int j)
{
    if(C[n] != C[0]) {
        V[n] = (e-b+1) * C[n];
        if(b!=e) {
            T[lc] = T[rc] = 0;
            P[lc] = P[rc] = 0;
            C[lc] = C[rc] = C[n];
        }
        C[n] = C[0];
    }
    if(T[n] || P[n]) {
        V[n] += calc(b,e) * T[n] + (e-b+1) *  P[n];
        if(b !=e) {
            T[lc] += T[n];
            T[rc] += T[n];
            P[lc] += P[n];
            P[rc] += P[n];
        }
        P[n] = 0;
        T[n] = 0;
    }
    if(b>j||e<i) return 0;
    if(b>=i&&e<=j) return V[n];
    int mid = (b+e)/2;
    return query(lc,b,mid,i,j) + query(rc,mid+1,e,i,j);
}
long long A[N];
int main()
{
    ms(C,63);
    int n = 250000,l,r,q,v,cs = 0;
    char ch;
    di(t);
    while(t--) {
        in(q);
        printf("Case %d:\n",++cs);
        for(int i=0;i<q;i++){

            scanf(" %c %d %d ",&ch,&l,&r);
            if(ch == 'A') upd(1,1,n,l,r,1,-(l-1));

            else if(ch =='B') upd(1,1,n,l,r,-1,(r+1));

            else if(ch=='C'){
                scanf(" %d ",&v);
                upd(1,1,n,l,r,0,v);
            }
            else if(ch=='S') printf("%lld\n", query(1,1,n,l,r));
        }
        ms(T,0);
        ms(C,63);
        ms(P,0);
        ms(V,0);
        ms(A,0);

    }
    return 0;
}