hdu1540Tunnel Warfare(线段树区间合并)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1540

此题的D，R操作非常简单，需要注意的就是Q求和操作，在进行求和的时候，需要检查一下所求点是否都位于左右子树的区间内，如果是的话那么就返回左子树的右连续最长加上右子树的左连续最长，（如果不懂可以画图验证一下），如果所求点的区间只位于左子树，与右子树没有相连，那么只需要递归左子树求左子树内的和就可以了，反正如果所求点只位于右子树也是相同操作。

ac代码：

#include
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#include
#include
#include<string>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define inff 0x7fffffff
using namespace std;
const int N = 50000 + 10;
const int M = 1000000 + 10;
const ll mod = 1e9 + 7;

struct node {
    int lsum;
    int rsum;
    int sum;
    //int lazy;
    int len;
}tree[N << 2];

void PushUp(int rt) {

    if (tree[rt << 1].sum == tree[rt << 1].len) {
        tree[rt].lsum = tree[rt << 1].sum + tree[rt << 1 | 1].lsum;
    }
    else {
        tree[rt].lsum = tree[rt << 1].lsum;
    }
    if (tree[rt << 1 | 1].sum == tree[rt << 1 | 1].len) {
        tree[rt].rsum = tree[rt << 1 | 1].sum + tree[rt << 1].rsum;
    }
    else {
        tree[rt].rsum = tree[rt << 1 | 1].rsum;
    }
    tree[rt].sum = tree[rt << 1].rsum + tree[rt << 1 | 1].lsum;
    tree[rt].sum = max(tree[rt << 1].sum, tree[rt].sum);
    tree[rt].sum = max(tree[rt << 1 | 1].sum, tree[rt].sum);

    return;
}

void Build(int l, int r, int rt) {

    tree[rt].len = r - l + 1;
    if (l == r) {
        tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, rt << 1);
    Build(mid + 1, r, rt << 1 | 1);
    PushUp(rt);

    return;
}

//void PushDown(int l, int r, int rt) {
//
//    if (tree[rt].lazy == 0) return;
//    int mid = (l + r) >> 1;
//    if (tree[rt].lazy == 1) {
//        tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = 0;
//        tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = 0;
//        tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 1;
//    }
//    else {
//        tree[rt << 1].sum = tree[rt << 1].lsum = tree[rt << 1].rsum = mid - l + 1;
//        tree[rt << 1 | 1].sum = tree[rt << 1 | 1].lsum = tree[rt << 1 | 1].rsum = r - (mid + 1) + 1;
//        tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = 2;
//    }
//    tree[rt].lazy = 0;
//
//    return;
//}

//void Update_in(int L, int R, int l, int r, int rt) {
//
//    if (l >= L && r <= R) {
//        tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 0;
//        tree[rt].lazy = 1;
//        return;
//    }
//    PushDown(l, r, rt);
//    int mid = (l + r) >> 1;
//    if (L <= mid) Update_in(L, R, l, mid, rt << 1);
//    if (R > mid) Update_in(L, R, mid + 1, r, rt << 1 | 1);
//    PushUp(rt);
//
//    return;
//}
//
//void Update_out(int L, int R, int l, int r, int rt) {
//
//    if (l >= L && r <= R) {
//        tree[rt].sum = tree[rt].lsum = tree[rt].rsum = r - l + 1;
//        tree[rt].lazy = 2;
//        return;
//    }
//    PushDown(l, r, rt);
//    int mid = (l + r) >> 1;
//    if (L <= mid) Update_out(L, R, l, mid, rt << 1);
//    if (R > mid) Update_out(L, R, mid + 1, r, rt << 1 | 1);
//    PushUp(rt);
//
//    return;
//}

void PointUpdate_D(int L, int l, int r, int rt) {

    if (l == r) {
        tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) PointUpdate_D(L, l, mid, rt << 1);
    else PointUpdate_D(L, mid + 1, r, rt << 1 | 1);
    PushUp(rt);

    return;
}

void PointUpdate_R(int L, int l, int r, int rt) {

    if (l == r) {
        tree[rt].sum = tree[rt].lsum = tree[rt].rsum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) PointUpdate_R(L, l, mid, rt << 1);
    else PointUpdate_R(L, mid + 1, r, rt << 1 | 1);
    PushUp(rt);

    return;
}

int Query(int pos, int l, int r, int rt) {

    if (l == r || tree[rt].sum == tree[rt].len) {
        return tree[rt].sum;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        if (pos >= mid - tree[rt << 1].rsum + 1) {
            return tree[rt << 1].rsum + tree[rt << 1 | 1].lsum;
        }
        else {
            return Query(pos, l, mid, rt << 1);
        }
    }
    else {
        if (pos <= mid + tree[rt << 1 | 1].lsum) {
            return tree[rt << 1].rsum + tree[rt << 1 | 1].lsum;
        }
        else {
            return Query(pos, mid + 1, r, rt << 1 | 1);
        }
    }

    return 0;
}

//int Query(int L, int R, int l, int r, int rt) {
//
//    if (l >= L && r <= R) {
//        return sum[rt];
//    }
//    int mid = (l + r) >> 1;
//
//    int ans = 0;
//    if (L <= mid) ans += Query(L, R, l, mid, rt << 1);
//    if (R > mid) ans += Query(L, R, mid + 1, r, rt << 1 | 1);
//
//    return ans;
//}

stack<int>st;
int vis[N];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    while (cin >> n >> m) {
        memset(tree, 0, sizeof(tree));
        memset(vis, 0, sizeof(vis));
        while (!st.empty()) st.pop();
        Build(1, n, 1);
        for (int i = 1; i <= m; i++) {
            char op;
            int x;
            cin >> op;
            if (op == 'D') {
                cin >> x;
                PointUpdate_D(x, 1, n, 1);
                st.push(x);
            }
            else if (op == 'Q') {
                cin >> x;
                cout << Query(x, 1, n, 1) << "\n";
            }
            else {
                if (st.empty()) continue;
                x = st.top();
                PointUpdate_R(x, 1, n, 1);
                st.pop();
                vis[x] = 0;
            }
        }
    }

    return 0;
}
   
线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签