1721: 感恩节KK专场——雪人的高度
时间限制: 1 Sec 内存限制: 128 MB 提交: 81 解决: 35 [提交][状态][讨论版]
题目描述
大雪过后，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
题解：由于雪人高度可能出现负值，值太大。
所以是离散化线段树，先把更新询问都存起来，把出现的元素都存在c数组里，最后进行操作；
注意lazy线段树，更新询问都要lazy；
无力，这个sb线段树，一直出问题； 4
4
U2 -1000 -50 100
U1 -500 -10 1000
Q1 -1000 -20
Q2 -1000 -11
100
-1000
这组数据过不了，感觉是lazy的问题。。。但是找不出来、。。。。。。。
这个题错的啊。。。。最终终于发现问题了，还是return的问题。。。看来自己的线段树真的不适合返回值。。。。
AC代码：：：：：：
#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|1,mid+1,r
#define V(x) tree[x].v
#define HI(x) tree[x].hi
#define LW(x) tree[x].lw
#define LAZY(x) tree[x].lazy
#define ll root<<1
#define rr root<<1|1
const int MAXN=400000;
typedef long long LL;
const int INF=0x3f3f3f3f;
struct Node{
int hi,lw;
int lazy;
};
Node tree[MAXN<<2];
struct DT{
int l,r,v,q;
}a[MAXN];
int c[MAXN];
int mi,mx;
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;
HI(root)+=v;
LW(root)+=v;
return ;
}
pushdown(root);
if(mid>=L)update(L,R,v,lson);
if(mid<R)update(L,R,v,rson);
/*else{
update(L,mid,v,lson);
update(mid+1,R,v,rson);
}*/
HI(root)=max(HI(ll),HI(rr));
LW(root)=min(LW(ll),LW(rr));
}
void query(int x,int y,int root,int l,int r){
int mid=(l+r)>>1;
if(l>=x&&r<=y){
//if(q==1)return HI(root);
//else return LW(root);
mi=min(mi,LW(root));
mx=max(mx,HI(root));
return;
}
pushdown(root);
// printf("%d %d\n",LW(root),HI(root));
//int ans=(q==1?-INF:INF);
if(mid>=x){
//if(q==1)return max(ans,query(x,y,lson,q));
//else return min(ans,query(x,y,lson,q));
query(x,y,lson);
}
if(mid<y){
//if(q==1)return max(ans,query(x,y,rson,q));
//else return min(ans,query(x,y,rson,q));
query(x,y,rson);
}
/*else{
if(q==1)
return max(query(x,mid,lson,q),query(mid+1,y,rson,q));
else return min(query(x,mid,lson,q),query(mid+1,y,rson,q));
}*/
}
int main(){
int T,N,x,y,v;
char s[5];
scanf("%d",&T);
while(T--){
mem(tree,0);
scanf("%d",&N);
int k1=0,k=0;
for(int i=0;i<N;i++){
scanf("%s",s);
if(strcmp(s,"U1")==0){
scanf("%d%d%d",&a[k1].l,&a[k1].r,&a[k1].v);
a[k1].v=-a[k1].v;a[k1].q=0;
c[k++]=a[k1].l;c[k++]=a[k1].r;
k1++;//把这个SB放错位置了。。。错了心碎啊
}
else if(strcmp(s,"U2")==0){
scanf("%d%d%d",&a[k1].l,&a[k1].r,&a[k1].v);
a[k1].q=0;
c[k++]=a[k1].l;c[k++]=a[k1].r;
k1++;
}
else if(strcmp(s,"Q1")==0){
scanf("%d%d",&a[k1].l,&a[k1].r);
a[k1].v=0;a[k1].q=1;
c[k++]=a[k1].l;c[k++]=a[k1].r;
k1++;
}
else{
scanf("%d%d",&a[k1].l,&a[k1].r);
a[k1].v=1;a[k1].q=2;
c[k++]=a[k1].l;c[k++]=a[k1].r;
k1++;
}
}
sort(c,c+k);
k=unique(c,c+k)-c;
//for(int i=0;i<k;i++)printf("%d ",c[i]);puts("");
//printf("%d\n",k);
for(int i=0;i<k1;i++){
int l=lower_bound(c,c+k,a[i].l)-c,r=lower_bound(c,c+k,a[i].r)-c;
if(l>r)swap(l,r);
// printf("%d %d\n",l,r);
if(a[i].q==0)
update(l+1,r+1,a[i].v,1,1,k);
else{
mi=INF;mx=-INF;
query(l+1,r+1,1,1,k);
if(a[i].q==1)printf("%d\n",mx);
else printf("%d\n",mi);
}
}
}
return 0;
}
又写了遍感觉挺水的；
不过要注意l，r的大小问题；
extern "C++"{
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned u;
typedef unsigned long long ull;
#define mem(x,y) memset(x,y,sizeof(x))
void SI(double &x){scanf("%lf",&x);}
void SI(int &x){scanf("%d",&x);}
void SI(LL &x){scanf("%lld",&x);}
void SI(u &x){scanf("%u",&x);}
void SI(ull &x){scanf("%llu",&x);}
void SI(char *s){scanf("%s",s);}
void PI(int x){printf("%d",x);}
void PI(double x){printf("%lf",x);}
void PI(LL x){printf("%lld",x);}
void PI(u x){printf("%u",x);}
void PI(ull x){printf("%llu",x);}
void PI(char *s){printf("%s",s);}
#define NL puts("");
#define ll root<<1
#define rr root<<1|1
#define lson ll,l,mid
#define rson rr,mid+1,r
const int INF=0x3f3f3f3f;
const int MAXN=;
int tree[MAXN << ];
int lazy[MAXN << ];
int mintree[MAXN << ];
}
int ans;
void pushup(int root){
//tree[root] = tree[ll] + tree[rr];
tree[root] = max(tree[ll],tree[rr]);
mintree[root] = min(mintree[ll],mintree[rr]);
}
void pushdown(int root){
if(lazy[root]){
lazy[ll] += lazy[root];
lazy[rr] += lazy[root];
// tree[ll]=lazy[root]*(mid-l+1);
// tree[rr]=lazy[root]*(r-mid);
tree[ll] += lazy[root];
tree[rr] += lazy[root];
mintree[ll] += lazy[root];
mintree[rr] += lazy[root];
lazy[root] = ;
}
}
void build(int root,int l,int r){
int mid = (l + r) >> ;
lazy[root] = ;
tree[root] = mintree[root] = ;
if(l == r)
return ;
build(lson);
build(rson);
pushup(root);
}
void update(int root,int l,int r,int L,int R,int C){
if(l >= L && r <= R){//由于是最大最小值，这里要注意
tree[root] += C;
mintree[root] += C;
lazy[root] += C;
return ;
}
int mid = (l + r) >> ;
pushdown(root);
if(mid >= L)
update(lson,L,R,C);
if(mid < R)
update(rson,L,R,C);
pushup(root);
}
void query(int root,int l,int r,int L,int R,int t){
int mid = (l + r) >> ;
if(l >= L && r <= R){
if(t == )
ans = max(ans,tree[root]);
else
ans = min(ans,mintree[root]);
return;
}
pushdown(root);
if(mid >= L)
query(lson,L,R,t);
if(mid < R)
query(rson,L,R,t);
}
struct Node{
int p,l,r,v;
}dt[MAXN];
int a[MAXN << ];
int main(){
//assert(false);
int T,N;
SI(T);
char s[];
while(T--){
SI(N);
int tp = ;
for(int i=;i<N;i++){
SI(s);
if(strcmp(s,"U1") == )
dt[i].p = -;
else if(strcmp(s,"U2") == )
dt[i].p = ;
else if(strcmp(s,"Q1") == )
dt[i].p = ;
else if(strcmp(s,"Q2") == )
dt[i].p = ;
SI(dt[i].l);SI(dt[i].r);
if(s[] == 'U')
SI(dt[i].v);
a[tp++] = dt[i].l;
a[tp++] = dt[i].r;
}
sort(a,a + tp);
int k = unique(a,a + tp) - a;
build(,,k);
for(int i = ;i < N;i++){
int l = lower_bound(a,a + k , dt[i].l) - a;
int r = lower_bound(a ,a + k , dt[i].r) - a;
if(l > r)
swap(l,r); //注意l可能比r大。。。。。
l++; r++;
if(dt[i].p < )
update(,,k,l,r,dt[i].v * dt[i].p);
else{
if(dt[i].p == )
ans = -0xfffffff;
else
ans = 0xfffffff;
query(,,k,l,r,dt[i].p);
PI(ans);NL
}
}
}
return ;
}