using namespace std;
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define maxn 300001

int a[maxn], s[maxn];
bool full[maxn];

inline void update(int n, int l, int r, int ql, int qr, int v)
{
	if(ql==l && r==qr)
	{
		full[n]=true;
		a[n]=v;
		s[n]=v*(r-l+1);
		return ;
	}
	
	int m=(l+r)>>1, L=n<<1, R=L+1;
	
	if(full[n])
	{
		full[L]=full[R]=true;
		s[L]=a[n]*(m-l+1);
		s[R]=a[n]*(r-(m+1)+1);
		a[L]=a[R]=a[n];
		full[n]=false;
	}
	
	if(ql<=m) update(L, l, m, ql, min(qr,m), v);
	if(qr>m)  update(R, m+1, r, max(ql,m+1), qr, v);

	s[n]=s[L]+s[R];
}

inline int query(int n, int l, int r, int ql, int qr)
{
	if(full[n]) return a[n]*(qr-ql+1);
	if(ql==l && r==qr) return s[n];
	
	int m=(l+r)>>1, L=n<<1, R=L+1;
	int v=0;
	if(ql<=m) v+=query(L, l, m, ql, min(qr,m));
	if(qr>m) v+=query(R, m+1, r, max(ql,m+1), qr);
	return v;
}

inline void baga()
{
	int p=(rand()%100000)+1;
	int q=(rand()%100000)+1;
	if(p>q){ int t=p;p=q;q=t;}
	
	update(1, 1, 100000, p, q, rand()%1000);
	
}

int main()
{
	srand(time(0));
	int n=100;
	update(1, 1, n, 2, 5,1);
	update(1, 1, n, 4, 6, 3);
	printf("%d\n", query(1, 1, n, 3, 6));
	
	double t=clock();
	for(int i=1;i<=100000;++i) baga();
	
	printf("%lf\n", (clock()-t)/(double)CLOCKS_PER_SEC);
	return 0;
}