线段树基本操作

struct SegmentTree {
    int l, r;
    int dat;
}t[maxn * 4];

//1. 线段树的建树
void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){ t[p].dat = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].dat = max(d[p * 2].dat, d[p * 2 + 1].dat);
}

build(1, 1, n);

//2. 线段树的单点修改
void change(int p, int x, int v){
    if(t[p].l == t[p].r){ t[p].dat = v; return;}
    int mid = (t[p].l + r[p].r) / 2;
    if(x <= mid) change(p * 2, x, v);
    else change(p * 2 + 1, x, v);
    t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);
}

change(1, x, n);

//3. 线段树的区间查询
int ask(int p, int l, int r){
    if(l <= t[p].l && t[p].r <= r) return t[p].dat;
    int mid = t[p].l + t[p].r >> 1;
    int res = -(1 << 30);
    if(l <= mid) res = max(res, ask(2 * p, l, r));
    if(r > mid) res = max(res, ask(2 * p + 1, l, r));
    return res;
}
cout << ask(1, l, r) << endl;

延迟标记 lazy标记 Acwing.243

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
    int l, r;
    ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){t[p].sum = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

void spread(int p){
    if(t[p].lazy){
        t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
        t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
        t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
        t[2 * p + 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void change(int p, int l, int r, ll d){
    if(t[p].l >= l && t[p].r <= r) {
        t[p].sum += d * (t[p].r - t[p].l + 1);
        t[p].lazy += d;  //注意是 "+=" 不是 "="
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(2 * p, l, r, d);
    if(r > mid) change(2 * p + 1, l, r, d);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
   if(t[p].l >= l && t[p].r <= r) return t[p].sum;
   int mid = t[p].l + t[p].r >> 1;
   spread(p);
   ll res = 0;
   if(l <= mid) res += ask(2 * p, l, r);
   if(r > mid) res += ask(2 * p + 1, l, r);
   return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    build(1, 1, n);

    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << ask(1, l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(1, l, r, val);
        }
    }
    return 0;
}

扫描线例题 Acwing 247

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn = 100005;

struct Edge{
    double x1, x2, y;
    int op;
    bool operator < (const Edge &tmp) const{
        return y < tmp.y;
    }
}e[maxn * 2];

struct SegmentTree{
    int l, r, cnt;
    double len;
}t[maxn * 4];

int n, m, T;
double xList[maxn * 2];

int query(double x){
    return lower_bound(xList, xList + m, x) - xList;
}

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r, t[p].cnt = t[p].len = 0;
    if(l == r) return;
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
}

void get_len(int p){
    if(t[p].cnt >= 1) t[p].len = xList[t[p].r + 1] - xList[t[p].l];
    else t[p].len = t[p << 1].len + t[(p << 1) | 1].len;
}

void update(int p, int l, int r, int val){
    if(l <= t[p].l && t[p].r <= r){
        t[p].cnt += val;
        get_len(p);
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) update(2 * p, l, r, val);
    if(r > mid) update(2 * p + 1, l, r, val);
    get_len(p);
}

int main(){
    T = 1;
    while(scanf("%d",&n), n){
        double x1, y1, x2, y2;
        int cnt = 0;
        for(int i = 0; i < n; ++ i){
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            e[cnt] = {x1, x2, y1, 1};
            xList[cnt ++] = x1;
            e[cnt] = {x1, x2, y2, -1};
            xList[cnt ++] = x2;
        }

        sort(xList, xList + cnt);
        sort(e, e + cnt);
        m = unique(xList, xList + cnt) - xList;

        build(1, 0, m - 1);

        double ans = 0;
        for(int i = 0; i < cnt - 1; ++ i){
            int el = query(e[i].x1);
            int er = query(e[i].x2) - 1;
            update(1, el, er, e[i].op);
            ans += (e[i + 1].y - e[i].y) * t[1].len;
        }

        printf("Test case #%d\n", T ++);
        printf("Total explored area: %.02f\n\n", ans);
    }
    return 0;
}