ZOJ 3324 Machine(線段樹區間合并）
來源：程序員人生 發布時間：2015-08-13 07:57:48 閱讀次數：3594次
這道題網上很多代碼是毛病的，由于后臺數據水，他們可以AC。
比如這組數據
10 3
p 0 9
r 0 5
r 6 9
輸出應當是 0 1 1
所以有的人直接記錄該區間是不是被覆蓋過的方法是毛病的
正確方法應當是記錄這段區間的最小高度（就是最接近初始位置的高度），和最小高度對應的最長左區間和右區間
開1個sum記錄這段區間最小高度的塊數，min_v 記錄該區間最小高度
cover作為怠惰標記下推該區間的子區間需要被壓幾次
#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:
",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 = ⑴;
update(l,r,1,c);
if(node[1].min_v == 0) t = 1;
ans = t * node[1].sum;
printf("%d
",ans);
}
}
return 0;
}
/*
1
10 3
p 0 9
r 0 5
r 6 9
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
