ZOJ 3324 Machine(线段树区间合并）

本文主要是介绍ZOJ 3324 Machine(线段树区间合并），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题网上很多代码是错误的，由于后台数据水，他们可以AC。

比如这组数据

10 3

p 0 9

r 0 5

r 6 9

输出应该是 0 1 1

所以有的人直接记录该区间是否被覆盖过的方法是错误的

正确方法应该是记录这段区间的最小高度（就是最接近初始位置的高度），和最小高度对应的最长左区间和右区间

开一个sum记录这段区间最小高度的块数，min_v 记录该区间最小高度

cover作为懒惰标记下推该区间的子区间需要被压几次

KinderRiven

C

Accepted

6776

170

C++ (g++ 4.7.2)

3285

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 20005;
const int maxd = 55555;
struct Input{char op[5];int x,y;
}input[maxn];
int Hash[maxd],cnt,ret;
void Hash_init(){sort(Hash,Hash + cnt);cnt = unique(Hash,Hash + cnt) - Hash;int t = cnt;for(int i = 1; i < t; i++)if(Hash[i - 1] + 1 != Hash[i]) Hash[cnt++] = Hash[i - 1] + 1;sort(Hash,Hash + cnt);
}
int HASH(int t){return lower_bound(Hash,Hash + cnt,t) - Hash;
}
struct Node{int l,r;int lx,rx,min_v,sum,cover;int mid(){return (l + r) >> 1;}int len(){return r - l + 1;}
}node[maxd << 2];
void build(int l,int r,int pos){node[pos].l = l;node[pos].r = r;node[pos].lx = node[pos].rx = node[pos].len();node[pos].min_v = 0;node[pos].sum = 1;node[pos].cover = 0;if(l == r) return;int mid = node[pos].mid();build(l,mid,lson);build(mid + 1,r,rson);
}
void pushdown(int pos){if(node[pos].cover){node[lson].cover += node[pos].cover;node[rson].cover += node[pos].cover;node[lson].min_v += node[pos].cover;node[rson].min_v += node[pos].cover;node[pos].cover = 0;}
}
void pushup(int pos){node[pos].min_v = min(node[lson].min_v,node[rson].min_v);if(node[lson].min_v == node[rson].min_v){node[pos].lx = node[lson].lx;node[pos].rx = node[rson].rx;if(node[pos].lx == node[lson].len()) node[pos].lx += node[rson].lx;if(node[pos].rx == node[rson].len()) node[pos].rx += node[lson].rx;node[pos].sum = node[lson].sum + node[rson].sum;if(node[lson].rx && node[rson].lx)node[pos].sum --;}else if(node[lson].min_v < node[rson].min_v){node[pos].lx = node[lson].lx;node[pos].rx = 0;node[pos].sum = node[lson].sum;}else{node[pos].rx = node[rson].rx;node[pos].lx = 0;node[pos].sum = node[rson].sum;}
}
void update(int l,int r,int pos,int d){if(l <= node[pos].l && node[pos].r <= r){node[pos].cover += d;node[pos].min_v += d;return;}pushdown(pos);int mid = node[pos].mid();if(l <= mid)update(l,r,lson,d);if(r  > mid)update(l,r,rson,d);pushup(pos);
}
int main(){int T,Case = 1;scanf("%d",&T);while(T--){int n,m;cnt = 0;ret = 0;scanf("%d%d",&n,&m);Hash[cnt++] = 0;Hash[cnt++] = n - 1;for(int i = 0; i < m; i++){scanf("%s%d%d",input[i].op,&input[i].x,&input[i].y);Hash[cnt++] = input[i].x;Hash[cnt++] = input[i].y;}Hash_init();build(0,cnt - 1,1);printf("Case #%d:\n",Case++);for(int i = 0; i < m; i++){int l = HASH(input[i].x),r = HASH(input[i].y),c,t = 0,ans;if(input[i].op[0] == 'p') c = 1;else  c = -1;update(l,r,1,c);if(node[1].min_v == 0) t = 1;ans = t * node[1].sum;printf("%d\n",ans);}}return 0;
}
/*
1
10 3
p 0 9
r 0 5
r 6 9
*/

这篇关于ZOJ 3324 Machine(线段树区间合并）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---