hdu1540/poj2892 線段數區間合并

HDU - 1540

POJ - 2892?

題意：n個點，有3種操作D a表示摧毀a這個點，R 表示修復上一個點，Q x表示查詢x所在的區間沒被摧毀的連續最大區間

思路：線段樹區間合并，區間合并主要就是對lsum rsum 和sum的動態維護，注意合并的條件，寫的時候主要注意push_up和push_down，還有對于不同的查詢query的寫法不一樣，update和creat和普通的線段樹差不多，這里查詢x所在區間可行的最大區間，每一個節點（子樹）可以知道的連續區間只有lsum[rt],rsum[rt] 和 rsum[lrt]+lsum[rrt] ，所以只能從這3個區間入手，每次判斷x是否被某個連續的區間所覆蓋即可

AC代碼：

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#pragma comment(linker, "/STACK:102400000,102400000")
#define ll long long
#define endl ("\n")
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a,x) memset(a,x,sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define ft (frist)
#define sd (second)
#define lrt (rt<<1)
#define rrt (rt<<1|1)
#define len (r-l+1)
using namespace std;
const long long INF = 1e18+1LL;
const int inf = 1e9+1e8;
const int N=1e5+100;
const ll mod=1e9+7;int n,sum[N<<1],lsum[N<<1],rsum[N<<1],lazy[N<<1];
void push_up(int rt, int m){int rm=m>>1, lm=m-rm;lsum[rt]=lsum[lrt], rsum[rt]=rsum[rrt];if(lsum[rt]==lm){lsum[rt]+=lsum[rrt];}if(rsum[rt]==rm){rsum[rt]+=rsum[lrt];}sum[rt]=max(sum[lrt],sum[rrt]);sum[rt]=max(sum[rt],rsum[lrt]+lsum[rrt]);
}void push_down(int rt, int m){int rm=m>>1, lm=m-rm;if(lazy[rt]==0){lm=rm=0;}sum[lrt]=lsum[lrt]=rsum[lrt]=lm;sum[rrt]=lsum[rrt]=rsum[rrt]=rm;lazy[lrt]=lazy[rrt]=lazy[rt];lazy[rt]=-1;
}void creat(int rt, int l, int r){if(l==r){sum[rt]=lsum[rt]=rsum[rt]=1;return;}lazy[rt]=-1;int mid=l+r>>1;creat(lrt,l,mid);creat(rrt,mid+1,r);push_up(rt, len);
}void update(int rt, int l, int r, int L, int R, int v){if(l>=L && r<=R){int m=len;lazy[rt]=v;if(!v) m=0; //cout<<m<<endl;sum[rt]=lsum[rt]=rsum[rt]=m;return;}if(lazy[rt]!=-1) push_down(rt, len);int mid=l+r>>1;if(L<=mid) update(lrt, l, mid, L, R, v);if(R>mid) update(rrt, mid+1, r, L, R, v);push_up(rt, len);
}int query(int rt, int l, int r, int x){if(l==r) return sum[rt];if(lazy[rt]!=-1) push_down(rt, len);int mid=l+r>>1;if(lsum[rt]>=x) return lsum[rt];else if(n-rsum[rt]+1<=x) return rsum[rt];else if(mid-rsum[lrt]+1<=x && mid+lsum[rrt] >=x ) return rsum[lrt]+lsum[rrt];else if(x<=mid) return query(lrt, l, mid, x);else return query(rrt, mid+1, r, x);
}int main(){//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);char c;int x,m;while(cin>>n>>m){creat(1,1,n);int l=0, d[N];while(m--){cin>>c;if(c=='R'){x=d[l--];update(1,1,n,x,x,1);}else{cin>>x;if(c=='D'){d[++l]=x;update(1,1,n,x,x,0);}else{cout<<query(1,1,n,x)<<endl;}}}}return 0;
}

?