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

#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 */