前言

此处只记录线段树应用上的"奇技淫巧"，不会提及线段树的基本知识。

动态开点线段树

适用于区间修改且维护区间大的题目

空间一般开$K*\text{修改次数},K\in[20,80]$

遇到RE就调大，遇到MLE就调小

例题: Codeforces 915 E (1s, 256MB)

题意，对于区间$[1,n]$，有两个操作：

1. 将$[l,r]$全部置$1$
2. 将$[l,r]$全部置$0$

每次操作后，求$[1,n]$中$1$的个数

PS. 本体开40倍空间会RE，60倍空间MLE

AC代码 (702ms, 235MB)

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 3e5 + 2000;

struct nd{
    int val, lazy, lson, rson;
}nodes[50 * maxn];
int root, node_cnt;

void pushdown(int rt, int l, int r){
    if(nodes[rt].lazy){
        int & lson = nodes[rt].lson;
        int & rson = nodes[rt].rson;
        if(lson == 0) lson = ++node_cnt;
        if(rson == 0) rson = ++node_cnt;
        nodes[lson].lazy = nodes[rson].lazy = nodes[rt].lazy;
        int mid = (l + r) >> 1;
        nodes[lson].val = (mid - l + 1) * (nodes[lson].lazy==1);
        nodes[rson].val = (r - mid) * (nodes[rson].lazy==1);
        nodes[rt].lazy = 0;
    }
}

void modify(int & rt, int l, int r, int ql, int qr, int val){
    if(rt == 0) rt = ++node_cnt;
    if(ql <= l && r <= qr){
        nodes[rt].lazy = val;
        nodes[rt].val = (r - l + 1) * (val==1);
        return;
    }
    pushdown(rt, l, r);
    int mid = (l + r) >> 1;
    if(ql <= mid) modify(nodes[rt].lson, l, mid, ql, qr, val);
    if(qr > mid) modify(nodes[rt].rson, mid + 1, r, ql, qr, val);
    nodes[rt].val = nodes[nodes[rt].lson].val + nodes[nodes[rt].rson].val; // 要保证nodes[0].val=0
}

int query(int & rt, int l, int r, int ql, int qr){
    if(rt == 0) return 0;
    if(ql <= l && r <= qr) return nodes[rt].val;
    pushdown(rt, l, r);
    int sum = 0, mid = (l + r) >> 1;
    if(ql <= mid) sum = query(nodes[rt].lson, l, mid, ql, qr);
    if(qr > mid) sum += query(nodes[rt].rson, mid + 1, r, ql, qr);
    return sum;
}

int n, q;
void solve(){
    cin >> n >> q;
    for(int i=0, l, r, v; i<q; i++){
        cin >> l >> r >> v;
        modify(root, 1, n, l, r, v);
        cout << n - query(root, 1, n, 1, n) << '\n';
    }
}
  
signed main(){
    Android;
    solve();
}