Cogs快速红包变换

#include<iostream>
#include<cstdio>
#define inf 1<<30
using namespace std;
int the_a[100010];
int n,m;
struct node
{
	int sum,lazy,covy;
	int maxn,minn;
	int maxnum,minnum; 
}tree[4*100010];
void down(int i,int l,int r)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(tree[i].covy!=-1)
	{
		tree[lson].covy=tree[i].covy;
		tree[lson].lazy=0;
		tree[lson].sum=(mid-l+1)*tree[i].covy;
		tree[lson].maxn=tree[lson].minn=tree[i].covy;
		tree[lson].maxnum=tree[lson].minnum=(mid-l+1);
		mid++;
		tree[rson].covy=tree[i].covy;
		tree[rson].lazy=0;
		tree[rson].sum=(r-mid+1)*tree[i].covy;
		tree[rson].maxn=tree[rson].minn=tree[i].covy;
		tree[rson].maxnum=tree[rson].minnum=(r-mid+1);
		tree[i].covy=-1;
	}
	mid=(l+r)>>1;
	if(tree[i].lazy!=0)
	{
		tree[lson].sum+=tree[i].lazy*(mid-l+1);
		tree[lson].lazy+=tree[i].lazy;
		tree[lson].minn+=tree[i].lazy;
		tree[lson].maxn+=tree[i].lazy;
		mid++;
		tree[rson].sum+=tree[i].lazy*(r-mid+1);
		tree[rson].lazy+=tree[i].lazy;
		tree[rson].minn+=tree[i].lazy;
		tree[rson].maxn+=tree[i].lazy;
		tree[i].lazy=0;
	}
}
void up(int i)
{
	int lson=i<<1,rson=lson|1;
	tree[i].sum=tree[lson].sum+tree[rson].sum;
	if(tree[lson].maxn>tree[rson].maxn)
	{
		tree[i].maxn=tree[lson].maxn;
		tree[i].maxnum=tree[lson].maxnum;
	}
	else
	{
		if(tree[lson].maxn<tree[rson].maxn)
		{
			tree[i].maxn=tree[rson].maxn;
			tree[i].maxnum=tree[rson].maxnum;
		}
		else
		{
			tree[i].maxn=tree[lson].maxn;
			tree[i].maxnum=tree[lson].maxnum+tree[rson].maxnum;
		}
	}
	if(tree[lson].minn<tree[rson].minn)
	{
		tree[i].minn=tree[lson].minn;
		tree[i].minnum=tree[lson].minnum;
	}
	else
	{
		if(tree[rson].minn<tree[lson].minn)
		{
			tree[i].minn=tree[rson].minn;
			tree[i].minnum=tree[rson].minnum;
		}
		else
		{
			tree[i].minn=tree[lson].minn;
			tree[i].minnum=tree[lson].minnum+tree[rson].minnum;
		}
	}
}
void buid(int now,int l,int r)
{
	int lson=now<<1,rson=lson|1,mid=(l+r)>>1;
	tree[now].lazy=0;
	tree[now].covy=-1;
	tree[now].maxnum=0;
	tree[now].minnum=0;
	tree[now].maxn=0;
	tree[now].minn=0;
	if(l==r)
	{
		tree[now].sum=the_a[l];
		tree[now].maxn=the_a[l];
	    tree[now].minn=the_a[l];
	    tree[now].maxnum=1;
	    tree[now].minnum=1;
	    return;
	}
	buid(lson,l,mid);
	mid++;
	buid(rson,mid,r);
	up(now);
}
void add(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return;
	if(u<=l&&v>=r)
	{
		tree[i].sum+=(r-l+1)*what;
		tree[i].minn+=what;
		tree[i].maxn+=what;
		tree[i].lazy+=what;
		return;
	}
	down(i,l,r);
	add(lson,l,mid,u,min(mid,v),what);
	mid++;
	add(rson,mid,r,max(u,mid),v,what);
	up(i);
}
int ask(int i,int l,int r,int u,int v)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(l>v||r<u) return 0;
	if(u<=l&&r<=v)
	{
		return tree[i].sum;
	}
	down(i,l,r);
	int re=0;
	re+=ask(lson,l,mid,u,min(v,mid));
	mid++;
	re+=ask(rson,mid,r,max(mid,u),v);
	up(i);
	return re;
}
void change(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(l>v||r<u) return ;
	if(u<=l&&r<=v)
	{
		tree[i].lazy=0;
		tree[i].covy=what;
		tree[i].sum=(r-l+1)*what;
		tree[i].minn=tree[i].maxn=what;
		tree[i].maxnum=tree[i].minnum=(r-l+1);
		return;
	}
	down(i,l,r);
	change(lson,l,mid,u,min(v,mid),what);
	mid++;
	change(rson,mid,r,max(u,mid),v,what);
	up(i);
}
int ask_max(int i,int l,int r,int u,int v)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return -1;
    if(u<=l&&v>=r)
    {
    	return tree[i].maxn;
	}
	int re=-1;
	down(i,l,r);
	re=max(re,ask_max(lson,l,mid,u,min(mid,v)));
	mid++;
	re=max(re,ask_max(rson,mid,r,max(u,mid),v));
    up(i);
	return re;
}
int ask_min(int i,int l,int r,int u,int v)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return inf;
	if(u<=l&&v>=r)
	{
		return tree[i].minn;
	}
	int re=inf;
	down(i,l,r);
	re=min(re,ask_min(lson,l,mid,u,min(mid,v)));
	mid++;
	re=min(re,ask_min(rson,mid,r,max(u,mid),v));
	up(i);
	return re;
}
int ask_maxn(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return 0;
    if(u<=l&&v>=r)
    {
    	if(tree[i].maxn==what)
    	{
    		return tree[i].maxnum;
		}
		else return 0;
	}
	int re=0;
	re+=ask_maxn(lson,l,mid,u,min(mid,v),what);
	mid++;
	re+=ask_maxn(rson,mid,r,max(u,mid),v,what);
	return re;
}
int ask_minn(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return 0;
    if(u<=l&&v>=r)
    {
    	if(tree[i].minn==what)
    	{
    		return tree[i].minnum;
		}
		else return 0;
	}
	int re=0;
	re+=ask_minn(lson,l,mid,u,min(mid,v),what);
	mid++;
	re+=ask_minn(rson,mid,r,max(u,mid),v,what);
	return re;
}
void cbmax(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return;
    if(u<=l&&v>=r)
    {
    	if(tree[i].minn>=what) return;
    	if(tree[i].maxn<=what)
    	{
    		change(1,1,n,u,v,what);
    		return;
		}
		down(i,l,r);
		cbmax(lson,l,mid,l,mid,what);
		mid++;
		cbmax(rson,mid,r,mid,r,what);
		up(i);
		return;
	}
	down(i,l,r);
	cbmax(lson,l,mid,u,min(mid,v),what);
	mid++;
	cbmax(rson,mid,r,max(u,mid),v,what);
    up(i);
}
void cbmin(int i,int l,int r,int u,int v,int what)
{
	int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
	if(r<u||l>v) return;
    if(u<=l&&v>=r)
    {
    	if(tree[i].maxn<=what) return;
    	if(tree[i].minn>=what)
    	{
    		change(1,1,n,u,v,what);
			return;
		}
		down(i,l,r);
		cbmin(lson,l,mid,l,mid,what);
		mid++;
		cbmin(rson,mid,r,mid,r,what);
		up(i);
		return;
	}
	down(i,l,r);
	cbmin(lson,l,mid,u,min(mid,v),what);
	mid++;
	cbmin(rson,mid,r,max(u,mid),v,what);
	up(i);
}
int read() 
{
    int out=0,flag=1;
    char c=getchar();
    while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
    while(c>=48&&c<=57)
    {
        out=out*10+c-48;
        c=getchar();
    }
    return out*flag;
}
int main()
{
	freopen("redbag.in","r",stdin);
	freopen("redbag.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) the_a[i]=read();
	buid(1,1,n);
	m=read();
	for(int i=1;i<=m;++i)
	{
		char cz[10];
		int u,v,a;
		scanf("%s",cz+1);
		if(cz[1]=='C')
		{
			u=read();
			v=read();
			a=read();
			if(cz[2]=='a')
			{
				add(1,1,n,u,v,a);
			}
			if(cz[2]=='c')
			{
				change(1,1,n,u,v,a);
			}
			if(cz[5]=='x'&&cz[2]=='b')
			{
				cbmax(1,1,n,u,v,a);
			}
			if(cz[5]=='n'&&cz[2]=='b')
			{
				cbmin(1,1,n,u,v,a);
			}
		}
		if(cz[1]=='Q')
		{
			u=read();
			v=read();
			if(cz[2]=='s') printf("%d\n",ask(1,1,n,u,v));
			if(cz[2]=='w')
			{
				if(cz[5]=='x') printf("%d\n",ask_max(1,1,n,u,v));
				if(cz[5]=='n') printf("%d\n",ask_min(1,1,n,u,v));
			}
			if(cz[2]=='n')
			{
				if(cz[5]=='x') 
				{
					int zz=ask_max(1,1,n,u,v);
				    printf("%d\n",ask_maxn(1,1,n,u,v,zz));
				}
				if(cz[5]=='n')
				{
					int zz=ask_min(1,1,n,u,v);
					printf("%d\n",ask_minn(1,1,n,u,v,zz));
				}
			}
		}
	}
	return 0;
}