12436

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define ll long long
#define sz 250005

using namespace std;

struct segment{
	ll left,right;
	ll len;

	ll first_inc,last_inc;
	ll totalAB;

	bool isSetvalue;
	ll cary;
	ll sum;

};

segment arr[sz*4];


void changeAB(ll frist_incr,ll last_incr,int node,ll step)
{
	arr[node].totalAB += step;
	arr[node].first_inc += frist_incr;
	arr[node].last_inc += last_incr;
	arr[node].sum += ((frist_incr+last_incr)*arr[node].len)/2;
}

void changeC(int node,ll val)
{
	arr[node].sum = arr[node].len*val;
	arr[node].isSetvalue=1;
	arr[node].cary=val;

	arr[node].totalAB=0;
	arr[node].first_inc=0;
	arr[node].last_inc=0;
}

void propagate(int node)
{
	ll add1 = arr[node].first_inc;
	ll add2 = arr[node].last_inc;
	ll step = arr[node].totalAB;

	if(arr[node].isSetvalue)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		changeC(Left,arr[node].cary);
		changeC(Right,arr[node].cary);
		arr[node].isSetvalue=0;
		arr[node].cary=0;
	}
	if(add1 || add2 || step)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		ll mid=add1+step*(arr[Left].len-1);
		changeAB(add1,mid,Left,step);
		changeAB(mid+step,add2,Right,step);

		arr[node].first_inc=0;
		arr[node].last_inc=0;
		arr[node].totalAB=0;
	}

}

//update node for the range
void updateAB(int node,int i,int j,ll step)
{
	ll Left=arr[node].left,Right=arr[node].right,mid;
	ll first_inc,last_inc;
	if(i>Right || j<Left)
	{
		return;
	}
	if(i<=Left && j>=Right)
	{
		ll k = step;
		if(step>=0)
		{
			first_inc = (Left-i+1);
			last_inc  = (Right-i+1);
		}
		else
		{
			first_inc = (j-Left+1);
			last_inc  = (j-Right+1);
		}
		changeAB(first_inc,last_inc,node,k);
		return;
	}
	else
	{
		propagate(node);
		Left=2*node;
		Right=(node<<1) | 1;
		updateAB(Left, i, j,step);
		updateAB(Right, i, j,step);
		arr[node].sum = arr[Left].sum+arr[Right].sum;
		return;
	}
	return;
}

void updateC(int node,int i,int j,ll val)
{
	ll Left,Right,mid;
	ll b=arr[node].left;
	ll e=arr[node].right;
	if(i>e || j<b)
	return;
	else if(i<=b && j>=e)
	{
		arr[node].sum = (val*(e-b+1));
		arr[node].cary=val;
		arr[node].isSetvalue=1;

		arr[node].totalAB=0;
		arr[node].first_inc=0;
		arr[node].last_inc=0;
		return;
	}
	else
	{
		propagate(node);
		Left = 2*node;
		Right = Left+1;
		mid = (b+e)>>1;
		updateC(Left,i,j,val);
		updateC(Right,i,j,val);
		arr[node].sum = (arr[Left].sum+arr[Right].sum);
		return;
	}
	return;
}

ll query(int node,int i,int j)
{
	ll b = arr[node].left;
	ll e = arr[node].right;

	if(i>e || j<b)
	{
		return 0;
	}
	if(i<=b && j>=e)
	{
		return arr[node].sum;
	}
	propagate(node);
	ll Left = node<<1;
	ll Right = Left+1;

	ll p1 = query(Left, i, j);
	ll p2 = query(Right, i, j);
	return p1+p2;
}


void _init(int b,int e,int node)
{
	arr[node].sum=0; arr[node].len=e-b+1;
	arr[node].totalAB=0;
	arr[node].cary=0;
	arr[node].first_inc=0; arr[node].last_inc=0;
	arr[node].isSetvalue=0;
	arr[node].left=b;arr[node].right=e;
	if(b!=e)
	{
		int mid=(b+e)/2;
		_init(b,mid,node<<1);
		_init(mid+1,e,(node<<1)|1);
	}
}
int main()
{
	int t;
	string s;
	int start,end,val;

	while(scanf("%d",&t)!=EOF)
	{
		_init(1,sz-5,1);
		while(t--)
		{
			cin>>s;
			if(s[0]=='A')
			{
				cin>>start>>end;
				updateAB(1,start,end,1);//+1 increment increasing ascending order
			}
			else if(s[0]=='B')
			{
				cin>>start>>end;
				updateAB(1,start,end,-1);//-1 increment decreasing ascending order
			}
			else if(s[0]=='C')
			{
				cin>>start>>end>>val;
				updateC(1,start,end,val);
			}
			else if(s[0]=='S')
			{
				cin>>start>>end;
				cout<<query(1,start,end)<<"\n";
			}
		}
	}

	return 0;
}

Some good links to learn segmented data structure:  click here