快速红包变换 - Pine - 425139

记录编号	425139	评测结果	AAAAAAAAAAT
题目名称	快速红包变换	最终得分	90
用户昵称	Pine	是否通过	未通过
代码语言	C++	运行时间	1.745 s
提交时间	2017-07-14 18:37:30	内存使用	11.00 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#define lc (o << 1)
#define rc ((o << 1) + 1)
#define mid ((l + r) >> 1)
#define N 100005 * 4
#define R register
using namespace std;

struct node1{
	int num,value;
};
struct node2{
	int sum,addv,setv;
	node1 Max,Min;
}a[N];
int n,m;

inline int read()
{
    R int data=0,w=1;R char ch=0;
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data*w;
}

inline node1 merge_max(node1 x, node1 y)
{
	if(x.value > y.value)return x;
	if(x.value < y.value)return y;
	return (node1){x.num + y.num, y.value};
}

inline node1 merge_min(node1 x,node1 y)
{
	if(x.value < y.value)return x;
	if(x.value > y.value)return y;
	return (node1){x.num + y.num, y.value};
}

inline void update(int o,int l,int r)
{
	a[o].sum = a[lc].sum + a[rc].sum;
	a[o].Max = merge_max(a[lc].Max,a[rc].Max);
	a[o].Min = merge_min(a[lc].Min,a[rc].Min);
}

inline void build(int o,int l,int r)
{
	a[o].addv = 0;a[o].setv = -1;
	if(l == r)
	{
		scanf("%d",&a[o].sum);
		a[o].Max = (node1){1,a[o].sum};
		a[o].Min = (node1){1,a[o].sum};
		return ;
	}
	build(lc,l,mid);build(rc,mid + 1,r);
	update(o,l,r);
}

inline void ADD(int o,int l,int r,int k)
{
	a[o].addv += k;a[o].Max.value += k;a[o].Min.value += k;
	a[o].sum += k * (r - l + 1);
}

inline void CHANGE(int o,int l,int r,int k)
{
	a[o].addv = 0;
	a[o].Max.value = a[o].Min.value = k;
	a[o].Max.num = a[o].Min.num = r - l + 1;
	a[o].sum = k * (r - l + 1);
	a[o].setv = k;
}

inline void push_down(int o,int l,int r)
{
	if(a[o].setv != -1)
	{
		CHANGE(lc,l,mid,a[o].setv);
		CHANGE(rc,mid + 1,r,a[o].setv);
		a[o].setv = -1;
	}
	if(a[o].addv)
	{
		ADD(lc,l,mid,a[o].addv);
		ADD(rc,mid + 1,r,a[o].addv);
		a[o].addv = 0;
	}
}

void add(int o,int l,int r,int x,int y,int k)
{
	if(x <= l && y >= r)
	{
		ADD(o,l,r,k);
		return;
	}
	push_down(o,l,r);
	if(x <= mid)add(lc,l,mid,x,y,k);
	if(y > mid)add(rc,mid + 1,r,x,y,k);
	update(o,l,r);
}

void change(int o,int l,int r,int x,int y,int k)
{
	if(x <= l && y >= r)
	{
		CHANGE(o,l,r,k);
		return;
	}
	push_down(o,l,r);
	if(x <= mid)change(lc,l,mid,x,y,k);
	if(y > mid) change(rc,mid + 1,r,x,y,k);
	update(o,l,r);
}

void bmax(int o,int l,int r,int x,int y,int k)
{
	if(l == r)
	{
		a[o].sum = max(a[o].sum,k);
		a[o].Min.value = a[o].Max.value = a[o].sum;
		return ;
	}
	if(x <= l && y >= r)
	{
		if(a[o].Max.value <= k)CHANGE(o,l,r,k);
		if(a[o].Min.value >= k)return ;
	}
	push_down(o,l,r);
	if(x <= mid)bmax(lc,l,mid,x,y,k);
	if(y > mid)bmax(rc,mid + 1,r,x,y,k);
	update(o,l,r);
}

void bmin(int o,int l,int r,int x,int y,int k)
{
	if(l == r)
	{
		a[o].sum = min(a[o].sum,k);
		a[o].Min.value = a[o].Max.value = a[o].sum;
		return ;
	}
	if(x <= l && y >= r)
	{
		if(a[o].Min.value >= k)CHANGE(o,l,r,k);
		if(a[o].Max.value <= k)return ;
	}
	push_down(o,l,r);
	if(x <= mid)bmin(lc,l,mid,x,y,k);
	if(y > mid)bmin(rc,mid + 1,r,x,y,k);
	update(o,l,r);
}

int _sum(int o,int l,int r,int x,int y)
{
	if(x <= l && y >= r)return a[o].sum;
	push_down(o,l,r);
	int ans = 0;
	if(x <= mid)ans += _sum(lc,l,mid,x,y);
	if(y > mid)ans += _sum(rc,mid + 1,r,x,y);
	return ans;
}

node1 _nmax(int o,int l,int r,int x,int y)
{
	if(x <= l && y >= r)return a[o].Max;
	push_down(o,l,r);
	node1 ans = {0,0};
	if(x <= mid)ans = _nmax(lc,l,mid,x,y);
	if(y > mid)ans = merge_max(ans, _nmax(rc,mid + 1,r,x,y));
	return ans;
}

node1 _nmin(int o,int l,int r,int x,int y)
{
	if(x <= l && y >= r)return a[o].Min;
	push_down(o,l,r);
	node1 ans = {0,1e9};
	if(x <= mid) ans = _nmin(lc,l,mid,x,y);
	if(y > mid)ans = merge_min(ans, _nmin(rc,mid + 1,r,x,y));
	return ans;
}

int main()
{
	freopen("redbag.in","r",stdin);
	freopen("redbag.out","w",stdout);
	n = read();
	build(1,1,n);
	m = read();
	for(int i = 1;i <= m;i ++)
	{
		R char a[10];
		scanf("%s",a);
		if(a[0] == 'C' && a[1] == 'a')
		{
			R int x,y,k;
			x = read();y = read();k = read();
			add(1,1,n,x,y,k);
		}
		if(a[0] == 'C' && a[1] == 'c')
		{
			R int x,y,k;
			x = read();y = read();k = read();
			change(1,1,n,x,y,k);
		}
		if(a[0] == 'C' && a[1] == 'b' && a[3] == 'a')
		{
			R int x,y,k;
			x = read();y = read();k = read();
			bmax(1,1,n,x,y,k);
		}
		if(a[0] == 'C' && a[1] == 'b' && a[3] == 'i')
		{
			R int x,y,k;
			x = read();y = read();k = read();
			bmin(1,1,n,x,y,k);
		}
		if(a[0] == 'Q' && a[1] == 's')
		{
			R int x,y;
			x = read();y = read();
			printf("%d\n",_sum(1,1,n,x,y));
		}
		if(a[0] == 'Q' && a[1] == 'w' && a[3] == 'a')
		{
			R int x,y;
			x = read();y = read();
			printf("%d\n",_nmax(1,1,n,x,y).value);
		}
		if(a[0] == 'Q' && a[1] == 'w' && a[3] == 'i')
		{
			R int x,y;
			x = read();y = read();
			printf("%d\n",_nmin(1,1,n,x,y).value);
		}
		if(a[0] == 'Q' && a[1] == 'n' && a[3] == 'a')
		{
			int x,y;
			x = read();y = read();
			printf("%d\n",_nmax(1,1,n,x,y).num);
		}
		if(a[0] == 'Q' && a[1] == 'n' && a[3] == 'i')
		{
			int x,y;
			x = read();y = read();
			printf("%d\n",_nmin(1,1,n,x,y).num);
		}
	}
	return 0;
}