HDU 1540 Tunnel Warfare——特殊查询的线段树

HDU 1540 Tunnel Warfare——特殊查询的线段树

一定要注意查询范围，以及及时变动查询位置，具体参考代码query函数

#include #include #include #include #include using namespace std;const int maxn = 1e5;stack last;int n, q;struct SegTree { bool is_all0; int maxL, maxR, max0;}segTree[maxn<<2];void pushup(int root) { segTree[root].is_all0 = segTree[root<<1].is_all0 && segTree[root<<1|1].is_all0; segTree[root].maxL = segTree[root<<1].maxL + (segTree[root<<1].is_all0 ? segTree[root<<1|1].maxL : 0); segTree[root].maxR = segTree[root<<1|1].maxR + (segTree[root<<1|1].is_all0 ? segTree[root<<1].maxR : 0); segTree[root].max0 = max(segTree[root<<1].maxR + segTree[root<<1|1].maxL, max(segTree[root<<1].max0, segTree[root<<1|1].max0));}void build(int L, int R, int root) { if (L == R) { segTree[root].is_all0 = true; segTree[root].maxL = segTree[root].maxR = segTree[root].max0 = 1; return; } int mid = (L + R)>>1; build(L, mid, root<<1); build(mid + 1, R, root<<1|1); pushup(root);}void update_node(int L, int R, int root, int pos, int val) { if (L == R) { segTree[root].is_all0 = val; segTree[root].maxL = segTree[root].maxR = segTree[root].max0 = val; return; } int mid = (L + R)>>1; if (pos <= mid) { update_node(L, mid, root<<1, pos, val); } else { update_node(mid + 1, R, root<<1|1, pos, val); } pushup(root);}int query(int L, int R, int root, int pos) { if (L == R || segTree[root].max0 == 0 || segTree[root].max0 == R - L + 1) { return segTree[root].max0; } int mid = (L + R)>>1; if (pos <= mid) { if (pos >= mid - segTree[root<<1].maxR + 1) { return query(L, mid, root<<1, pos) + query(mid + 1, R, root<<1|1, mid + 1); } else { return query(L, mid, root<<1, pos); } } else { if (pos <= mid + segTree[root<<1|1].maxL) { return query(mid + 1, R, root<<1|1, pos) + query(L, mid, root<<1, mid); } else { return query(mid + 1, R, root<<1|1, pos); } }}int main(){ while (scanf("%d %d", &n, &q) == 2) { build(1, n, 1); while (!last.empty()) last.pop(); while (q--) { char c; cin >> c; if (c == 'D') { int x; scanf("%d", &x); last.push(x); update_node(1, n, 1, x, 0); } else if (c == 'R') { int x = last.top(); last.pop(); update_node(1, n, 1, x, 1); } else { int x; scanf("%d", &x); printf("%d\n", query(1, n, 1, x)); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。