ACM - 每日一题 - 4.9 线段树lazy

题目链接

主要是学习的前几个dalao的代码，整理了一遍自己的格式。
注意好 lazy 标记。细节都在代码里。

#include <bits/stdc++.h>
using namespace std;

#define Lrt (rt << 1)
#define Rrt (rt << 1 | 1)
#define mid ((l + r) >> 1)

const int N = 1e5 + 10;

struct Tree{
    bool lazy[26];
    int w[26];
}tree[N<<2];

struct node{
    int w[26];
}zero;

char x[N];
int a[N];

void pushup(int rt){
    for(int i = 0; i <= 25; i++)
        tree[rt].w[i] = tree[Lrt].w[i] + tree[Rrt].w[i];
}

void pushdown(int rt, int l, int r){
    if (l == r){
        return;
    }
    for(int i = 0; i <= 25; i++)
        if (tree[rt].lazy[i]){
            for(int j = 0; j <= 25; j++)
                tree[Lrt].lazy[j] = tree[Rrt].lazy[j] = tree[Lrt].w[j] = tree[Rrt].w[j] = 0;
            tree[Lrt].lazy[i] = tree[Rrt].lazy[i] = 1;
            tree[Lrt].w[i] = mid - l + 1;
            tree[Rrt].w[i] = r - mid;
            tree[rt].lazy[i] = 0;
        }
}

void build(int rt, int l, int r){
    if (l == r){
        tree[rt].w[a[l]] = 1;
        return;
    }
    build(Lrt, l, mid);
    build(Rrt, mid+1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int L, int R, int v){
    if (l > R || r < L) return;
    if (L <= l && R >= r){
        for(int i = 0; i <= 25; i++)
            tree[rt].lazy[i] = tree[rt].w[i] = 0;
        tree[rt].lazy[v] = 1;
        tree[rt].w[v] = r - l + 1;
        return;
    }
    pushdown(rt, l, r);
    if (L <= mid) update(Lrt, l, mid, L, R, v);
    if (R > mid) update(Rrt, mid + 1, r, L, R, v);
    pushup(rt);
}

node query(int rt, int l, int r, int L, int R){
    if (L <= l && R >= r){
        node t;
        for(int i = 0; i <= 25; i++)
            t.w[i] = tree[rt].w[i];
        return t;
    }
    pushdown(rt, l, r);
    node t = zero;
    if (L <= mid){
        node tt = query(Lrt, l, mid, L, R);
        for(int i = 0; i <= 25; i++)
            t.w[i] += tt.w[i];
    }
    if (R > mid){
        node tt = query(Rrt, mid + 1, r, L, R);
        for(int i = 0; i <= 25; i++)
            t.w[i] += tt.w[i];
    }
    return t;
}

void print(int rt, int l, int r){
    pushdown(rt, l, r);
    if (l == r){
        for(int i = 0; i <= 25; i++)
            if (tree[rt].w[i]){
                printf("%c", 'a' + i);
                return;
            }
    }
    print(Lrt, l, mid);
    print(Rrt, mid + 1, r);
}

int main(){
    //freopen("input.txt", "r", stdin);
    int n, m, L, R, op;
    char x[N];
    scanf("%d%d", &n, &m);
    scanf("%s", x + 1);
    for(int i = 1; i <= n; i++){
        a[i] = x[i] - 'a';
    }
    build(1, 1, n);
    while(m--){
        scanf("%d%d%d", &L, &R, &op);
        node t = query(1, 1, n, L, R);
        if (op){
            for(int i = 0; i <= 25; i++){
                update(1, 1, n, L, L + t.w[i] - 1, i);
                L += t.w[i];
            }
        }
        else{
            for(int i = 25; i >= 0; i--){
                update(1, 1, n, L, L + t.w[i] - 1, i);
                L += t.w[i];
            }
        }
    }
    print(1, 1, n);
    return 0;
}