大雪过后，KK决定在春秋大道的某些区间上堆雪人。现在KK遇到了一道统计雪人高度的难题，请你帮帮他吧。注：KK堆雪人前春秋大道上是没有雪人的即所有位置雪人高度为0。
大雪过后，KK决定在春秋大道的某些区间上堆雪人。现在KK遇到了一道统计雪人高度的难题，请你帮帮他吧。注：KK堆雪人前春秋大道上是没有雪人的即所有位置雪人高度为0。
给定一个整数t，表示有t(t<=5)组测试数据。每组测试数据有两个整数N(1<=N<=200000)，表示N次操作。
操作分四种: U1 x y v [x, y]位置的雪人高度减v
U2 x y v [x, y]位置的雪人高度加v
Q1 x y 查询[x, y]之间雪人的最大高度 Q2 x y 查询[x, y]之间雪人的最小高度
注: (|x|, |y|<=2^30, |v|<=100)
若上面的操作使某个位置的雪人高度为负，我们认为这种情况是合法的。
对每个查询输出结果，结果占一行。结果保证不会超int。
1 2 U2 -1000 1000 1 Q1 1000 10001
1
写了一半，现扔着
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define lson root<<1,l,mid
#define rson root<<1,mid+1,r
#define V(root) tree[root].v
#define HI(root) tree[root].hi
#define LW(root) tree[root].lw
#define LAZY(root) tree[root].lazy
#define pushup1 HI=max(tree[root<<1].v,tree[root<<1|1].v)
#define pushup2 LW=min(tree[root<<1].v,tree[root<<1|1].v)
#define ll root<<1
#define rr root<<1|1
const int MAXN=400000;
typedef long long LL;
struct Node{
LL hi,lw;
int lazy;
};
Node tree[MAXN<<2];
void pushdown(int root){
if(LAZY(root)){
LAZY(ll)+=LAZY(root);
LAZY(rr)+=LAZY(root);
HI(ll)+=LAZY(root);
HI(rr)+=LAZY(root);
LW(ll)+=LAZY(root);
LW(rr)+=LAZY(root);
LAZY(root)=0;
}
}
void update(int L,int R,int v,int root,int l,int r){
int mid=(l+r)>>1;
if(l>=L&&r<=R){
LAZY(root)+=v;
VAL(root)=v;
HI(root)+=v;
LW(root)+=v;
return ;
}
pushdown(root);
if(mid>=R)update(L,R,v,lson);
else if(mid<L)update(L,R,v,rson);
else{
update(L,mid,v,lson);
update(mid+1,R,v,rson);
}
push1;push2;
}
void query(int x,int y,int root,int l,int r){
int mid=(l+r)>>1;
if(l>=x&&r<=y){
mi=min(mi,LW(root));
mx=max(mx,HI(root));
return;
}
pushdown(root);
if(mid>=x)query(x,y,lson);
if(mid<y)qiery(x,y,rson);
}
int main(){
int T,N,x,y,v;
char s[5];
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%s",s);
if(strcmp(s,"U1")){
scanf("%d%d%d",&x,&y,&v);
}
}
}
return 0;
}
原文：http://www.cnblogs.com/handsomecui/p/5022461.html