E - Tunnel Warfare HDU - 1540
对这个题目的思考：首先我们已经意识到这个是一个线段树，要利用线段树来解决问题，但是怎么解决呢，这个摧毁和重建的操作都很简单，但是这个查询怎么查呢，
这个是不是要判断这一个点左边和右边最远的距离，然后相加起来就可以了，所以就是维护一个区间最左边和最右边的值，然后把他们合并就是最大值。
这个最左边的值 pre_max = 子左节点的 pre_max
如果这个 pre_max==len 那就可以合并子右节点的 pre_max
最右值同理
这个都知道了就只剩下细心一点写这个题目了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <string> #include <stack> #include <iostream> #include <map> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 1e5 + 10; typedef long long ll; struct node { int l, r, len; int pre_max, last_max; }tree[maxn*4]; void push_up(int id) { tree[id].pre_max = tree[id << 1].pre_max; tree[id].last_max = tree[id << 1 | 1].last_max; if (tree[id << 1].len == tree[id << 1].pre_max) tree[id].pre_max += tree[id<<1|1].pre_max; if (tree[id << 1 | 1].len == tree[id << 1 | 1].last_max) tree[id].last_max += tree[id << 1].last_max; // printf("tree[%d].max=%d tree[%d].min=%d ", id, tree[id].pre_max, id, tree[id].last_max); // printf("tree[%d].max=%d tree[%d].min=%d ", id << 1, tree[id << 1].pre_max, id << 1, tree[id << 1].last_max); // printf("tree[%d].max=%d tree[%d].min=%d ", id << 1 | 1, tree[id << 1 | 1].pre_max, id << 1 | 1, tree[id << 1 | 1].last_max); } void build(int id,int l,int r) { tree[id].l = l; tree[id].r = r; tree[id].len = r - l + 1; if(l==r) { tree[id].last_max = tree[id].pre_max = 1; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); push_up(id); } void update(int id,int pos,int val) { //printf("id=%d pos=%d val=%d ", id, pos, val); int l = tree[id].l; int r = tree[id].r; if(l==r) { tree[id].last_max = tree[id].pre_max = val; return; } int mid = (l + r) >> 1; if (pos <= mid) update(id << 1, pos, val); else update(id << 1 | 1, pos, val); push_up(id); } int query_pre(int id,int x,int y) { int l = tree[id].l; int r = tree[id].r; //printf("id=%d l=%d r=%d x=%d y=%d ", id, l, r, x, y); if(x<=l&&y>=r) return tree[id].pre_max; int mid = (l + r) >> 1; int ans = 0, res = 0; if (x <= mid) ans = query_pre(id << 1, x, y); if (y > mid) res = query_pre(id << 1 | 1, x, y); // printf("id=%d res=%d ans=%d ", id, res, ans); if (ans >= mid - x + 1) return ans += res;//这个区间长度就是mid-x+1 因为mid 是在里面的所以要+1 return ans; } int query_last(int id, int x, int y) { int l = tree[id].l; int r = tree[id].r; //printf("id=%d l=%d r=%d x=%d y=%d ", id, l, r, x, y); if (x <= l && y >= r) return tree[id].last_max; int mid = (l + r) >> 1; int ans = 0, res = 0; if (x <= mid) ans = query_last(id << 1, x, y); if (y > mid) res = query_last(id << 1 | 1, x, y); //printf("Ans=%d res=%d ", ans, res); if (res >= y - mid) res += ans;//区间长度为 y-mid mid不在里面 return res; } int main() { int m, n; while(scanf("%d%d", &n, &m)!=EOF) { stack<int>sta; build(1, 1, n); while(m--) { char s[10]; int x; scanf("%s", s); if(s[0]=='D') { scanf("%d", &x); sta.push(x); update(1, x, 0); } else if(s[0]=='R') { if(!sta.empty()) { int num = sta.top(); sta.pop(); update(1, num, 1); } } else if(s[0]=='Q') { scanf("%d", &x); int ans = query_pre(1, x, n); ans += query_last(1, 1, x); if(ans) printf("%d ", ans - 1); else printf("0 "); } } } return 0; }
对这个题目的思考：这个题目不太会写，对于区间合的基本套路还是不太熟悉，这个题目看了题解之后(推荐题解 题解传送门）还是很清楚的。
我们知道这个是一个区间合并的线段树，和区间息息相关，这个要求长度为 w 的最左边的区间，还要求起点。
长度确定，所以我们就一个域是求最大长度的，因为要最左边的区间，而且我们要求最大长度就有合并操作，
所以我们要确定一个从左边开始最长的和从右边开始最长的，这个就和上面的差不多。
这个就是大致思路，剩下就是一些细节了。
一定要仔细点写，然后wa到哭
#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <string> #include <stack> #include <iostream> #include <map> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 1e5 + 10; typedef long long ll; struct node { int l, r, lazy, len; int pre_max, last_max, max; }tree[maxn * 4]; void push_up(int id) { tree[id].pre_max = tree[id << 1].pre_max; tree[id].last_max = tree[id << 1 | 1].last_max; if (tree[id << 1].pre_max == tree[id << 1].len) tree[id].pre_max += tree[id << 1 | 1].pre_max; if (tree[id << 1 | 1].last_max == tree[id << 1 | 1].len) tree[id].last_max += tree[id << 1].last_max; tree[id].max = max(max(tree[id<<1].max, tree[id<<1|1].max), tree[id << 1].last_max + tree[id << 1 | 1].pre_max); //printf("tree[%d].pre_max=%d tree[%d].last_max=%d ", id, tree[id].pre_max, id, tree[id].last_max); } void build(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].lazy = -1; tree[id].len = tree[id].last_max = tree[id].pre_max = tree[id].max = r - l + 1; //printf("tree[%d].pre_max=%d tree[%d].last_max=%d ", id, tree[id].pre_max, id, tree[id].last_max); if (l == r) return; int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); } void push_down(int id) { if (tree[id].lazy != -1) { tree[id << 1].lazy = tree[id << 1 | 1].lazy = tree[id].lazy; if (tree[id].lazy) { tree[id << 1].last_max = tree[id << 1].pre_max = tree[id << 1].max = tree[id << 1].len; tree[id << 1 | 1].last_max = tree[id << 1 | 1].pre_max = tree[id << 1 | 1].max = tree[id << 1 | 1].len; } else { tree[id << 1].last_max = tree[id << 1].pre_max = tree[id << 1].max = 0; tree[id << 1 | 1].last_max = tree[id << 1 | 1].pre_max = tree[id << 1 | 1].max = 0; } tree[id].lazy = -1; } } void update(int id, int x, int y, int val) { // printf("id=%d x=%d y=%d val=%d ", id, x, y, val); int l = tree[id].l; int r = tree[id].r; if (x == l && y == r) { tree[id].lazy = val; if (val) tree[id].last_max = tree[id].pre_max = tree[id].max = tree[id].len; else tree[id].last_max = tree[id].pre_max = tree[id].max = 0; return; } push_down(id); int mid = (l + r) >> 1; if (y <= mid) update(id << 1, x, y, val); else if (mid + 1 <= x) update(id << 1 | 1, x, y, val); else { update(id << 1, x, mid, val); update(id << 1 | 1, mid + 1, y, val); } push_up(id); } int query(int id, int val) { int l = tree[id].l; int r = tree[id].r; //printf("id=%d l=%d r=%d ", id, l, r); if (l == r) return l; int mid = (l + r) >> 1; push_down(id); if (tree[id << 1].max >= val) return query(id << 1, val); //printf("id1=%d ", id); if (tree[id << 1].last_max + tree[id << 1 | 1].pre_max >= val) return mid - tree[id << 1].last_max + 1; //printf("tree[%d].last=%d tree[%d].pre=%d id2=%d ", id<<1,tree[id<<1].last_max,id<<1|1,tree[id<<1|1].pre_max,id); return query(id << 1 | 1, val); } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { build(1, 1, n); while (m--) { int opt, x, y; scanf("%d", &opt); if (opt == 1) { scanf("%d", &x); if (tree[1].max < x) { printf("0 "); continue; } int ans = query(1, x); if (ans) update(1, ans, ans + x - 1, 0); printf("%d ", ans); } else { scanf("%d%d", &x, &y); update(1, x, x + y - 1, 1); } } } return 0; }
G - 约会安排
这个题目 ：
如果是 DS 就是普通的查找，如果找到就输出最靠前的时间点，这个和上面的操作很像，然后更新。
如果是 NS 就要进行两次查找，第一次是普通查找，没有找到就是二级查找，这个二级查找就是一种覆盖，然后更新。
如果是 study 那就是清空为0 的操作。
这个就是相当于建了两棵树，一颗女神树，一颗基友树，处理女神树的时候要更新基友树，但是处理基友树就不需要更新女神树。
这个题目一定要注意 输出答案
描述中的“如果找到，就说“X,let’s fly”（此处，X为开始时间）…"
和Output中的 “X,let's fly”
里的“ ’ ”和 “ ' ” 不是一个符号，别复制错了！！！
#include <cstdio>//描述中的“如果找到，就说“X,let’s fly”（此处，X为开始时间）…" #include <cstdlib>//和Output中的 “X, let's fly” #include <cstring>//里的“ ’ ”和 “ ' ” 不是一个符号，别复制错了！！！ #include <queue> #include <vector> #include <algorithm> #include <string> #include <stack> #include <iostream> #include <map> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 1e5 + 10; typedef long long ll; struct node { int len; int lsum, rsum, sum;//1 级的 int lmax, rmax, max;//2 级的 }tree[maxn * 8]; void build(int id, int l, int r) { tree[id].max = tree[id].lmax = tree[id].rmax = r - l + 1; tree[id].len = tree[id].lsum = tree[id].rsum = tree[id].sum = r - l + 1; if (l == r) return; int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); } void push_up(int id) { tree[id].lsum = tree[id << 1].lsum; tree[id].rsum = tree[id << 1 | 1].rsum; if (tree[id << 1].lsum == tree[id << 1].len) tree[id].lsum += tree[id << 1 | 1].lsum; if (tree[id << 1 | 1].rsum == tree[id << 1 | 1].len) tree[id].rsum += tree[id << 1].rsum; tree[id].sum = max(max(tree[id << 1].sum, tree[id << 1 | 1].sum), tree[id << 1].rsum + tree[id << 1 | 1].lsum); tree[id].sum = max(tree[id].sum, tree[id].lsum); tree[id].sum = max(tree[id].sum, tree[id].rsum); tree[id].lmax = tree[id << 1].lmax; tree[id].rmax = tree[id << 1 | 1].rmax; if (tree[id << 1].lmax == tree[id << 1].len) tree[id].lmax += tree[id << 1 | 1].lmax; if (tree[id << 1 | 1].rmax == tree[id << 1 | 1].len) tree[id].rmax += tree[id << 1].rmax; tree[id].max = max(max(tree[id << 1].max, tree[id << 1 | 1].max), tree[id << 1].rmax + tree[id << 1 | 1].lmax); tree[id].max = max(tree[id].max, tree[id].lmax); tree[id].max = max(tree[id].max, tree[id].rmax); } void push_down(int id) { if(tree[id].max==tree[id].len) { tree[id << 1].max = tree[id << 1].lmax = tree[id << 1].rmax = tree[id << 1].len; tree[id << 1 | 1].max = tree[id << 1 | 1].lmax = tree[id << 1 | 1].rmax = tree[id << 1 | 1].len; } if(tree[id].max==0) { tree[id << 1].max = tree[id << 1].lmax = tree[id << 1].rmax = 0; tree[id << 1 | 1].max = tree[id << 1 | 1].lmax = tree[id << 1 | 1].rmax = 0; } if(tree[id].sum==tree[id].len) { tree[id << 1].sum = tree[id << 1].lsum = tree[id << 1].rsum = tree[id << 1].len; tree[id << 1 | 1].sum = tree[id << 1 | 1].lsum = tree[id << 1 | 1].rsum = tree[id << 1 | 1].len; } if(tree[id].sum==0) { tree[id << 1].sum = tree[id << 1].lsum = tree[id << 1].rsum = 0; tree[id << 1 | 1].sum = tree[id << 1 | 1].lsum = tree[id << 1 | 1].rsum = 0; } } void update(int id, int l, int r, int x, int y, int val) { if (x <= l && y >= r) { if (val == 2) { tree[id].max = tree[id].lmax = tree[id].rmax = 0; tree[id].sum = tree[id].lsum = tree[id].rsum = 0; } if (val == 1) { tree[id].sum = tree[id].lsum = tree[id].rsum = 0; } if (val == 0) { tree[id].max = tree[id].lmax = tree[id].rmax = tree[id].len; tree[id].sum = tree[id].lsum = tree[id].rsum = tree[id].len; } return; } push_down(id); int mid = (l + r) >> 1; if (x <= mid) update(id << 1, l, mid, x, y, val); if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, val); push_up(id); } int query_1(int id, int l, int r, int val) { if (l == r) return l; int mid = (l + r) >> 1; push_down(id); if (tree[id << 1].sum >= val) return query_1(id << 1, l, mid, val); if (tree[id << 1].rsum + tree[id << 1 | 1].lsum >= val) return mid - tree[id << 1].rsum + 1; return query_1(id << 1 | 1, mid + 1, r, val); } int query_2(int id,int l,int r,int val) { if (l == r) return l; int mid = (l + r) >> 1; push_down(id); if (tree[id << 1].max >= val) return query_2(id << 1, l, mid, val); if (tree[id << 1].rmax + tree[id << 1 | 1].lmax >= val) return mid - tree[id << 1].rmax + 1; return query_2(id << 1 | 1, mid + 1, r, val); } int main() { int t; scanf("%d", &t); for(int cas=1;cas<=t;cas++) { int n, m, x, y; scanf("%d%d", &n, &m); build(1, 1, n); printf("Case %d: ", cas); while(m--) { char s[10]; scanf("%s", s); if(s[0]=='D') { scanf("%d", &x); if(tree[1].sum<x) { printf("fly with yourself "); continue; } int ans = query_1(1, 1, n, x); printf("%d,let's fly ", ans); update(1, 1, n, ans, x + ans - 1, 1); } if(s[0]=='N') { scanf("%d", &x); if(tree[1].sum>=x) { int ans = query_1(1, 1, n, x); printf("%d,don't put my gezi ", ans); update(1, 1, n, ans, x + ans - 1, 2); continue; } if(tree[1].max<x) { printf("wait for me "); continue; } int ans = query_2(1,1,n,x); printf("%d,don't put my gezi ", ans); update(1, 1, n, ans, x + ans - 1, 2); } if(s[0]=='S') { scanf("%d%d", &x, &y); update(1, 1, n, x, y, 0); printf("I am the hope of chinese chengxuyuan!! "); } } } }