陈村九江网站建设,风格网站,顺德网站制作案例信息,专业网站制作公司案例HDU - 1540 POJ - 2892 题意#xff1a;n个点#xff0c;有3种操作D a表示摧毁a这个点#xff0c;R 表示修复上一个点#xff0c;Q x表示查询x所在的区间没被摧毁的连续最大区间 思路#xff1a;线段树区间合并#xff0c;区间合并主要就是对lsum rsum 和sum的动态维护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) coutx UUUUUendl;
#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 (rt1)
#define rrt (rt1|1)
#define len (r-l1)
using namespace std;
const long long INF 1e181LL;
const int inf 1e91e8;
const int N1e5100;
const ll mod1e97;int n,sum[N1],lsum[N1],rsum[N1],lazy[N1];
void push_up(int rt, int m){int rmm1, lmm-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 rmm1, lmm-rm;if(lazy[rt]0){lmrm0;}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(lr){sum[rt]lsum[rt]rsum[rt]1;return;}lazy[rt]-1;int midlr1;creat(lrt,l,mid);creat(rrt,mid1,r);push_up(rt, len);
}void update(int rt, int l, int r, int L, int R, int v){if(lL rR){int mlen;lazy[rt]v;if(!v) m0; //coutmendl;sum[rt]lsum[rt]rsum[rt]m;return;}if(lazy[rt]!-1) push_down(rt, len);int midlr1;if(Lmid) update(lrt, l, mid, L, R, v);if(Rmid) update(rrt, mid1, r, L, R, v);push_up(rt, len);
}int query(int rt, int l, int r, int x){if(lr) return sum[rt];if(lazy[rt]!-1) push_down(rt, len);int midlr1;if(lsum[rt]x) return lsum[rt];else if(n-rsum[rt]1x) return rsum[rt];else if(mid-rsum[lrt]1x midlsum[rrt] x ) return rsum[lrt]lsum[rrt];else if(xmid) return query(lrt, l, mid, x);else return query(rrt, mid1, r, x);
}int main(){//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);char c;int x,m;while(cinnm){creat(1,1,n);int l0, d[N];while(m--){cinc;if(cR){xd[l--];update(1,1,n,x,x,1);}else{cinx;if(cD){d[l]x;update(1,1,n,x,x,0);}else{coutquery(1,1,n,x)endl;}}}}return 0;
} 转载于:https://www.cnblogs.com/max88888888/p/7271434.html
