待更新

线段树讲解(未读)
线段树模板(未读)

模板

求区间总和

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 111111;
int add[maxn<<2];
LL sum[maxn<<2];

void PushUp(int k) {
    // 根据子结点更新父结点
    sum[k] = sum[k<<1] + sum[k<<1|1];
}

void PushDown(int k,int m) {
    // 根据父结点更新子结点
    if (add[k]) {
        // 根据标记修改子结点
        add[k<<1] += add[k];
        add[k<<1|1] += add[k];
        sum[k<<1] += add[k] * (m - (m >> 1));
        sum[k<<1|1] += add[k] * (m >> 1);
        // 取消标记
        add[k] = 0;
    }
}

void build(int l,int r,int k) {
    // 初始化
    add[k] = 0;
    if (l == r) {
        scanf("%lld", &sum[k]);
        return ;
    }
    // 递归建树
    int m = (l + r) >> 1;
    build(l, m, k << 1);
    build(m+1, r, k << 1 | 1);
    // 更新父结点
    PushUp(k);
}

void update(int L, int R, int c, int l, int r, int k) {
    if (L <= l && r <= R) {
        // 如果搜索区间在目标区间之内就直接修改
        add[k] += c;
        sum[k] += (LL)c * (r - l + 1);
        return ;
    }
    // 更新子结点
    PushDown(k , r - l + 1);
    // 递归更新
    int m = (l + r) >> 1;
    if (L <= m)
        update(L, R, c, l, m, k << 1);
    if (m < R)
        update(L, R, c, m+1, r, k << 1 | 1);
    // 更新父结点
    PushUp(k);
}

LL query(int L,int R,int l,int r,int k) {
    // 查询区间总和
    if (L <= l && r <= R)
        // 如果搜索区间在目标区间之内就直接修改
        return sum[k];
    // 更新子结点
    PushDown(k , r - l + 1);
    // 递归找总和
    int m = (l + r) >> 1;
    LL ans = 0;
    if (L <= m) ans += query(L , R , l, m, k << 1);
    if (m < R) ans += query(L , R , m+1, r, k << 1 | 1);
    return ans;
}

int main() {
    int n, Q;
    scanf("%d%d", &n, &Q);
    build(1, n, 1);
    while (Q--) {
        char op[2];
        int a , b , c;
        scanf("%s",op);
        if (op[0] == 'Q') {
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a , b , 1, n, 1));
        } else {
            scanf("%d%d%d",&a,&b,&c);
            update(a , b , c , 1, n, 1);
        }
    }
    return 0;
}

A - 敌兵布阵

HDU - 1166

题意

线段树裸题。
只要做一个树上单点的数据维护和数据查找就可以了。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 400005;
int n, ans;
struct {
    int l, r, n;
}segTree[maxn];

void init() {
    int k;
    for (k = 1; k < n; k <<= 1);
    for (int i = k; i < k << 1; ++i) {
        segTree[i].l = segTree[i].r = i - k + 1;
        segTree[i].n = 0;
    }
    for (int i = k - 1; i > 0; --i) {
        segTree[i].l = segTree[2 * i].l;
        segTree[i].r = segTree[2 * i + 1].r;
        segTree[i].n = 0;
    }
}

void insert(int i, int x, int m) {
    if (x >= segTree[i].l && x <= segTree[i].r)
        segTree[i].n += m;
    if (segTree[i].l == segTree[i].r)
        return;
    int mid = (segTree[i].l + segTree[i].r) / 2;
    if (x > mid)
        insert(2 * i + 1, x, m);
    else
        insert(2 * i, x, m);
}

void find(int x, int y, int i) {
    if (segTree[i].l == x && segTree[i].r == y){
        ans += segTree[i].n;
        return;
    }
    if (segTree[i].l == segTree[i].r)
        return;
    int mid = (segTree[i].l + segTree[i].r) / 2;
    if (x > mid)
        find(x, y, 2 * i + 1);
    else if (y <= mid)
        find(x, y, 2 * i);
    else{
        find(x, mid, 2 * i);
        find(mid + 1, y, 2 * i + 1);
    }
}

int main() {
    int t, cas = 0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        int w;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w);
            insert(1, i, w);
        }
        char op[6]; int a, b;
        printf("Case %d:\n", ++cas);
        while (scanf("%s", op) && op[0] != 'E') {
            scanf("%d%d", &a, &b);
            if (op[0] == 'Q') {
                ans = 0;
                find(a, b, 1);
                printf("%d\n", ans);
            }
            else if (op[0] == 'A')
                insert(1, a, b);
            else
                insert(1, a, -b);
        }
    }
    return 0;
}

C - A Simple Problem with Integers

POJ - 3468

题意

线段树裸题。套模板。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 111111;
int add[maxn<<2];
LL sum[maxn<<2];

void PushUp(int k) {
    // 根据子结点更新父结点
    sum[k] = sum[k<<1] + sum[k<<1|1];
}

void PushDown(int k,int m) {
    // 根据父结点更新子结点
    if (add[k]) {
        // 根据标记修改子结点
        add[k<<1] += add[k];
        add[k<<1|1] += add[k];
        sum[k<<1] += add[k] * (m - (m >> 1));
        sum[k<<1|1] += add[k] * (m >> 1);
        // 取消标记
        add[k] = 0;
    }
}

void build(int l,int r,int k) {
    // 初始化
    add[k] = 0;
    if (l == r) {
        scanf("%lld", &sum[k]);
        return ;
    }
    // 递归建树
    int m = (l + r) >> 1;
    build(l, m, k << 1);
    build(m+1, r, k << 1 | 1);
    // 更新父结点
    PushUp(k);
}

void update(int L, int R, int c, int l, int r, int k) {
    if (L <= l && r <= R) {
        // 如果搜索区间在目标区间之内就直接修改
        add[k] += c;
        sum[k] += (LL)c * (r - l + 1);
        return ;
    }
    // 更新子结点
    PushDown(k , r - l + 1);
    // 递归更新
    int m = (l + r) >> 1;
    if (L <= m)
        update(L, R, c, l, m, k << 1);
    if (m < R)
        update(L, R, c, m+1, r, k << 1 | 1);
    // 更新父结点
    PushUp(k);
}

LL query(int L,int R,int l,int r,int k) {
    // 查询区间总和
    if (L <= l && r <= R)
        // 如果搜索区间在目标区间之内就直接修改
        return sum[k];
    // 更新子结点
    PushDown(k , r - l + 1);
    // 递归找总和
    int m = (l + r) >> 1;
    LL ans = 0;
    if (L <= m) ans += query(L , R , l, m, k << 1);
    if (m < R) ans += query(L , R , m+1, r, k << 1 | 1);
    return ans;
}

int main() {
    int n, Q;
    scanf("%d%d", &n, &Q);
    build(1, n, 1);
    while (Q--) {
        char op[2];
        int a , b , c;
        scanf("%s",op);
        if (op[0] == 'Q') {
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a , b , 1, n, 1));
        } else {
            scanf("%d%d%d",&a,&b,&c);
            update(a , b , c , 1, n, 1);
        }
    }
    return 0;
}

D - Mayor's posters

HDU - 1698

题意

线段树重复染色。
只需要一个区间染色操作和一个查询操作即可。
唯一的问题是需要简单Hash一下。
如果完全简单哈希的话会有问题,所以用数组缓存一下,然后判断两个数是否相邻,如果不相邻需要在他们之间插入一个任意数来分隔。

代码

// 94ms 1112KB C++
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 11111;

bool hashset[maxn];
int col[maxn<<4], x[maxn<<2];
int ans, n, cnt, cur;

struct {
    int l, r;
}q[maxn];

void pushdown(int rt){
    if (col[rt] != -1){
        col[rt<<1] = col[rt<<1|1] = col[rt];
        col[rt] = -1;
    }
}

void update(int L, int R, int c, int l, int r, int rt){
    // 区间染色
    if (L <= l && r <= R){
        col[rt] = c;
        return;
    }
    pushdown(rt);
    int m = (l+r)>>1;
    if (L <= m) update(L, R, c, l, m, rt<<1);
    if (R > m) update(L, R, c, m+1, r, rt<<1|1);
}

void query(int l, int r, int rt){
    if (col[rt] != -1){
        // 根据染色更新vis(hashset)
        if (!hashset[col[rt]]) ++ans;
        hashset[col[rt]] = true;
        return;
    }
    if (l == r) return;
    int m = (l+r) >> 1;
    query(l, m, rt<<1);
    query(m+1, r, rt<<1|1);
}

void init(){
    cnt = ans = 0;
    scanf("%d", &n);
    memset(col, -1, sizeof(col));
    memset(hashset, 0, sizeof(hashset));
}

void solve(){
    init();
    for (int i = 0; i < n; ++i){
        scanf("%d%d", &q[i].l, &q[i].r);
        x[cnt++] = q[i].l, x[cnt++] = q[i].r;
    }
    // 给所有的区间排序,取其中不重复的
    sort(x, x + cnt);
    cur = 1;
    for (int i = 1; i < cnt; ++i)
        if (x[i] != x[i-1])
            x[cur++] = x[i];

    // 如果前后两个数是不相邻的,那就在两个之间插入一个前一个数(其实可以是任意)
    for (int i = cur-1; i >= 1; --i)
        if (x[i] != x[i-1] + 1)
            x[cur++] = x[i-1] + 1;
    sort(x, x + cur);

    for (int i = 0; i < n; ++i){
        // 找每一个问题的左右边界
        int l = lower_bound(x, x + cur, q[i].l) - x;
        int r = lower_bound(x, x + cur, q[i].r) - x;
        // 更新区间
        update(l, r, i, 0, cur, 1);
    }

    // 计算答案
    query(0, cur, 1);

    // 输出
    printf("%d\n", ans);
}

int main(){
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

意外发现

在看LeaderBoard的时候意外发现一个大神的代码。线段树用DFS做,而且时间和内存都非常小,代码也很短,26行。真是厉害的操作。
另外,对于G++和C++的提交发现,这段代码在G++上可以跑出16ms的神级速度,而C++就会32ms。同时,快读对于C++编译器会起反作用,但是G++可以很快。inline对内存的优化也是这样。

// 0ms 680KB G++
#include <cstdio>
#include <cstring>
int c, n, ans, start[10005], end[10005], vis[10005];

void dfs(int l, int r, int x){
    if (!x) return;
    if (r >= start[x] && l <= end[x]){
        if (!vis[x]) { vis[x] = 1; ++ans; }
        if (l < start[x]) dfs(l, start[x] - 1, x - 1);
        if (r > end[x]) dfs(end[x] + 1, r, x - 1);
    }
    else dfs(l, r, x-1);
}

int main(){
    scanf("%d", &c);
    while (c--){
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d%d", start+i, end+i);
        memset(vis, 0, sizeof(vis));
        ans = 0;
        dfs(1, 10000000, n);
        printf("%d\n", ans);
    }
}

E - Just a Hook

HDU - 1698

题意

线段树裸题。
区间染色求和。
第一次不是看题解而是自己套板子过的题,还行还行。
出题人估计是Dota打多了

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 111111;
int add[maxn<<2];
int sum[maxn<<2];

void PushUp(int k) {
    sum[k] = sum[k<<1] + sum[k<<1|1];
}

void PushDown(int k,int m) {
    if (add[k]) {
        add[k<<1] = add[k];
        add[k<<1|1] = add[k];
        sum[k<<1] = add[k] * (m - (m >> 1));
        sum[k<<1|1] = add[k] * (m >> 1);
        add[k] = 0;
    }
}

void build(int l,int r,int k) {
    add[k] = 0;
    if (l == r) {
        sum[k] = 1;
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, k << 1);
    build(m+1, r, k << 1 | 1);
    PushUp(k);
}

void update(int L, int R, int c, int l, int r, int k) {
    if (L <= l && r <= R) {
        add[k] = c;
        sum[k] = (int)c * (r - l + 1);
        return ;
    }
    PushDown(k , r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m)
        update(L, R, c, l, m, k << 1);
    if (m < R)
        update(L, R, c, m+1, r, k << 1 | 1);
    PushUp(k);
}

int query(int L,int R,int l,int r,int k) {
    if (L <= l && r <= R)
        return sum[k];
    PushDown(k , r - l + 1);
    int m = (l + r) >> 1;
    int ans = 0;
    if (L <= m) ans += query(L , R , l, m, k << 1);
    if (m < R) ans += query(L , R , m+1, r, k << 1 | 1);
    return ans;
}

void solve(int cas) {
    int n, Q;
    scanf("%d%d", &n, &Q);
    build(1, n, 1);
    while (Q--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        update(a, b, c, 1, n, 1);
    }
    printf("Case %d: The total value of the hook is %d.\n", cas, query(1, n, 1, n, 1));
}

int main(){
    int t, cas = 0;
    scanf("%d", &t);
    while (t--)
        solve(++cas);
    return 0;
}