自学内容网 自学内容网
自学内容网 > 正文

线段树模板

🕗 发布于 2024-12-10 20:50 cocoa  macos  objective-c  

单点修改

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;

const int N = 1e6;
#define lc p << 1
#define rc p << 1 | 1
struct Tree {
    int l, r, mx;
}tr[N * 4];

void pushup(int p) {
    tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}
void build(int p, int l, int r) {
    tr[p] = {l, r, 0ll};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}

int query(int p, int ql, int qr) {
    if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx;
    if (ql > tr[p].r || qr < tr[p].l) return 0;
    return max(query(lc, ql, qr), query(rc, ql, qr)); 
}

void modify(int p, int x, int k) {
    if (tr[p].l == tr[p].r && tr[p].l == x) {
        tr[p].mx = k;
        return ;
    }
    if (x <= tr[lc].r) modify(lc, x, k);
    if (x >= tr[rc].l) modify(rc, x, k);
    pushup(p);
}

int dp[N];
void solve() {
    int n, d; cin >> n >> d;
    build(1, 0ll, 500000ll);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        int l = max(0ll, x - d), r = min(500000ll, x + d);
        int t = query(1, l, r);
        dp[x] = t + 1;
        modify(1, x, dp[x]);
    }

    int ans = 0;
    for (int i = 1; i <= 5e5; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}

signed main() {
    IOS;
    // int T; cin >> T;
    // while (T--)
        solve();
 
    return 0;
}

区间修改

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;

const int N = 4e5 + 10;
#define lc p << 1
#define rc p << 1 | 1
struct Tree {
    int l, r, sum, add, mul;
}tr[N * 4];

int n, q, mod;
int a[N];
void pushup(int p) {
    tr[p].sum = (tr[lc].sum + tr[rc].sum) % mod;
}

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0, 1};
    if (l == r) {
        tr[p].sum = a[l] % mod;
        return ;
    }

    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}

void pushdown(int p) {
    tr[lc].sum = (tr[lc].sum * tr[p].mul % mod + (tr[p].add * (tr[lc].r - tr[lc].l + 1) % mod)) % mod;
    tr[lc].mul = (tr[lc].mul * tr[p].mul) % mod;
    tr[lc].add = (tr[lc].add * tr[p].mul + tr[p].add) % mod;

    tr[rc].sum = (tr[rc].sum * tr[p].mul % mod + (tr[p].add * (tr[rc].r - tr[rc].l + 1) % mod)) % mod;
    tr[rc].mul = (tr[rc].mul * tr[p].mul) % mod;
    tr[rc].add = (tr[rc].add * tr[p].mul + tr[p].add) % mod;

    tr[p].add = 0;
    tr[p].mul = 1;
}
void update_add(int p, int ql, int qr, int k) {
    if (tr[p].l > qr || tr[p].r < ql) return ;
    if (ql <= tr[p].l && qr >= tr[p].r) {
        tr[p].add = (tr[p].add + k) % mod;
        tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1) * k) % mod;
        return ;
    }
    
    pushdown(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (ql <= mid) update_add(lc, ql, qr, k);
    if (qr > mid) update_add(rc, ql, qr, k);
    pushup(p);
}

void update_mul(int p, int ql, int qr, int k) {
    if (tr[p].l > qr || tr[p].r < ql) return ;
    if (ql <= tr[p].l && qr >= tr[p].r) {
        tr[p].mul = tr[p].mul * k % mod;
        tr[p].add = tr[p].add * k % mod;
        tr[p].sum = tr[p].sum * k % mod;
        return ;
    }

    pushdown(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (ql <= mid) update_mul(lc, ql, qr, k);
    if (qr > mid) update_mul(rc, ql, qr, k);
    pushup(p);
}

int query(int p, int ql, int qr) {
    if (tr[p].l > qr || tr[p].r < ql) return 0;
    if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].sum % mod;
    pushdown(p);

    int ans = 0;
    int mid = tr[p].l + tr[p].r >> 1;
    if (ql <= mid) ans += query(lc, ql, qr);
    if (qr > mid) ans += query(rc, ql, qr);
    ans %= mod;
    return ans;
}

void solve() {
    cin >> n >> q >> mod;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    while (q--) {
        int op; cin >> op;
        int l, r; cin >> l >> r;
        if (op == 1) {
            int k; cin >> k;
            update_mul(1, l, r, k);
        }
        else if (op == 2) {
            int k; cin >> k;
            update_add(1, l, r, k);
        }
        else {
            cout << query(1, l, r) << '\n';
        }
    }
}

signed main() {
    IOS;
    // int T; cin >> T;
    // while (T--)
        solve();
 
    return 0;
}

势能线段树

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
//#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;

const int N = 4e5 + 10;
#define lc p << 1
#define rc p << 1 | 1

struct Tree {
    int l, r, sum, mx;
}tr[N * 4];
int a[N];

void pushup(int p) {
    tr[p].sum = tr[lc].sum | tr[rc].sum;
    tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}

void build(int p, int l, int r) {
    tr[p] = {l, r, a[l], a[l]};
    if (l == r) return ;
    
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}


void modify(int p, int x, int v) {
    if (x < tr[p].l || x > tr[p].r) return ;
    if (tr[p].l == tr[p].r && tr[p].l == x) {
        tr[p].sum = v;
        tr[p].mx = v;
        return ;
    }

    int mid = tr[p].l + tr[p].r >> 1;
    if (x <= mid) modify(lc, x, v);
    if (x > mid) modify(rc, x, v);
    pushup(p);
}

void update(int p, int ql, int qr, int v) {
    if (tr[p].l > qr || tr[p].r < ql) return ;
    if (tr[p].l == tr[p].r) {
        tr[p].sum &= v;
        tr[p].mx &= v;
        return ;
    }

    if ((tr[p].sum & v) == tr[p].sum) return ;
    update(lc, ql, qr, v);
    update(rc, ql, qr, v);
    pushup(p);
}

int query(int p, int ql, int qr) {
    if (tr[p].l > qr || tr[p].r < ql) return 0;
    if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx;
    int ans = 0;
    int mid = tr[p].l + tr[p].r >> 1;
    if (ql <= mid) ans = max(ans, query(lc, ql, qr));
    if (qr > mid) ans = max(ans, query(rc, ql, qr));
    return ans;
}

int read() {
    int x; scanf("%lld", &x);
    return x;
}

char op[4];
void solve() {
    int n, m; n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);

    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            int l, r, v; l = read(), r = read(), v = read();
            update(1, l, r, v);
        }
        else if (op[0] == 'U') {
            int x, v; x = read(), v = read();
            modify(1, x, v);
        }
        else {
            int l, r; l = read(), r = read();
            cout << query(1, l, r) << '\n';
        }
    }
}

signed main() {
    //IOS;
    // int T; cin >> T;
    // while (T--)
        solve();
 
    return 0;
}

主席树

区间第k大

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;

const int N = 2e5 + 10;
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
struct Tree {
    int ch[2];
    int s;
}tr[N * 22];
int root[N];
int a[N];
int idx;

void build(int &p, int l, int r) {
    p = ++idx;
    if (l == r) return ;
    int mid = l + r >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
}

void insert(int x, int &y, int l, int r, int v) {
    y = ++idx;
    tr[y] = tr[x];
    tr[y].s++;
    if (l == r) return ;
    int mid = l + r >> 1;
    if (v <= mid) insert(lc(x), lc(y), l, mid, v);
    else insert(rc(x), rc(y), mid + 1, r, v);
}

int query(int x, int y, int l, int r, int k) {
    if (l == r) return l;
    int mid = l + r >> 1;
    int sum = tr[lc(y)].s - tr[lc(x)].s;
    if (sum >= k) return query(lc(x), lc(y), l, mid, k);
    else return query(rc(x), rc(y), mid + 1, r, k - sum);
}

int arr[N];
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        arr[i] = a[i];
    }  
    build(root[0], 1, n);

    sort(arr + 1, arr + 1 + n);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(arr + 1, arr + 1 + n, a[i]) - arr;
    }

    for (int i = 1; i <= n; i++) {
        insert(root[i - 1], root[i], 1, n, a[i]);
    }

    while (m--) {
        int l, r, k; cin >> l >> r >> k;
        int t = query(root[l - 1], root[r], 1, n, k);
        cout << arr[t] << '\n';
    }
}

signed main() {
    IOS;
    // int T; cin >> T;
    // while (T--)
        solve();
 
    return 0;
}

主席树二分

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define PII pair<int, int>
#define x first
#define y second
#define endl '\n'

inline int read() {int c; cin >> c; return c;}
inline void readn(int a[], int n) {
    for_each(a + 1, a + n + 1, [](int &x) {cin >> x;});
}
inline void writen(int a[], int n) {
    for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; });
    cout << endl;
}
template<typename T, typename... Args>
void write(const T &first, const Args &...args) {
    cout << first;
    ((cout << ' ' << args), ...);
    cout << endl;
}
template<typename T, typename... Args>
void ewrite(const T& first, const Args&... args) {
    cerr << '*';
    cerr << first;
    ((cerr << ' ' << args), ...);
    cerr << endl;
}
char out[2][10] = {"No", "Yes"};
const double eps = 1e-6;
const int N = 1e6 + 10;
const int M = N << 1;
const int mod = 998244353;

/* next is main_solve */
int n;
int a[N];


struct node {
    int l, r, sum;
} o[N * 30];
int rt[N];
int tot;
int add(int x, int l, int r, int v) {
    int t = ++tot;
    o[t] = o[x];
    o[t].sum++;
    if (l == r)
        return t;
    int mid = (l + r) / 2;
    if (v <= mid)
        o[t].l = add(o[t].l, l, mid, v);
    else
        o[t].r = add(o[t].r, mid + 1, r, v);
    return t;
}

int asksum(int x, int l, int r, int ql, int qr)
{
    if (x == 0)
        return 0;
    if (ql <= l && r <= qr)
        return o[x].sum;
    int mid = l + r >> 1;
    if (ql <= mid && qr > mid)
        return asksum(o[x].l, l, mid, ql, qr) + asksum(o[x].r, mid + 1, r, ql, qr);
    else if (ql <= mid)
        return asksum(o[x].l, l, mid, ql, qr);
    else
        return asksum(o[x].r, mid + 1, r, ql, qr);
}
int ask(int x, int l, int r, int cnt)
{
    if (l == r)
        return l;
    int mid = l + r >> 1;
    if (o[o[x].l].sum >= cnt)
        return ask(o[x].l, l, mid, cnt);
    else
        return ask(o[x].r, mid + 1, r, cnt - o[o[x].l].sum);

}
int ask(int beg, int i, int k)
{

    int sum = o[rt[i]].sum; //总的大于等于i的位置的数量
    int suml;
    if (beg == 1)
        suml = 0;
    else
        suml = asksum(rt[i], 1, n, 1, beg - 1);//beg前面有几个大于等于i

    if (sum - suml < k) //如果剩下的数量不足k个则无法升级，返回n+1
        return n + 1;

    return ask(rt[i], 1, n, suml + k); //区间里第一个等于suml+k的位置
}

vector<int> sb[N];
vector<int> pos[N];

void solve() {
    n = read();
    int q;
    q = read();
    readn(a, n);

    for (int i = 1; i <= n; i++) {
        sb[a[i]].pb(i);
    }

    for (int i = 200000; i >= 1; i--) {
        rt[i] = rt[i + 1];
        for (auto x : sb[i]) {
            rt[i] = add(rt[i], 1, n, x);
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int l = 1, r, i = 1; l <= n; i++) {
            r = ask(l, i, k);
            pos[k].pb(r);
            l = r + 1;
        }
    }

    while (q--) {
        int p, k;
        p = read(), k = read();
        int t = lower_bound(all(pos[k]), p) - pos[k].begin() + 1;
        if (a[p] >= t) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

void cloud_fly() {
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cloud_fly();
    return 0;
}

扫描线

扫描线求面积

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

#define int long long
const int N = 1e5 + 10;

struct line{
    int x1, x2, y, tag;
}L[N * 2];
bool cmp(line l1, line l2) {
    return l1.y < l2.y;
}
int X[N * 2];

#define lc p << 1
#define rc p << 1 | 1
struct Tree{
    int l, r;
    int cnt, len;
}tr[N * 16];

void pushup(int p) {
    int l = tr[p].l, r = tr[p].r;
    if (tr[p].cnt > 0) tr[p].len = X[r + 1] - X[l];
    else tr[p].len = tr[lc].len + tr[rc].len;
}
void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
}

void update(int p, int ql, int qr, int k) {
    if (tr[p].r < ql || tr[p].l > qr) return ;
    if (tr[p].l >= ql && tr[p].r <= qr) {
        tr[p].cnt += k;
        pushup(p);
        return ;
    }

    update(lc, ql, qr, k);
    update(rc, ql, qr, k);
    pushup(p);
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        L[i] = {x1, x2, y1, 1};
        L[n + i] = {x1, x2, y2, -1};
        X[i] = x1;
        X[n + i] = x2;
    }
    n *= 2;
    sort(L + 1, L + 1 + n, cmp);
    sort(X + 1, X + 1 + n);
    int m = unique(X + 1, X + 1 + n) - X - 1;
    build(1, 1, m - 1);

    int ans = 0;
    for (int i = 1; i < n; i++) {
        int ql = lower_bound(X + 1, X + 1 + m, L[i].x1) - X;
        int qr = lower_bound(X + 1, X + 1 + m, L[i].x2) - X;
        update(1, ql, qr - 1, L[i].tag);
        ans += 1ll * tr[1].len * (L[i + 1].y - L[i].y);
    }
    cout << ans << '\n';
}

signed main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);

    // int T; cin >> T;
    // while (T--) 
        solve();

    return 0;
}

扫描线求周长

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

#define int long long
const int N = 5e3 + 10;
int X[N * 2];
struct line{
    int x1, x2, y, tag;
    bool operator< (const line t) {
        if (y == t.y) return tag > t.tag;
        return y < t.y;
    }
}L[N * 16];

struct Tree{
    int l, r;
    int cnt, len; 
    int lcover, rcover, sum;
}tr[N * 8];
#define lc p << 1
#define rc p << 1 | 1

void build(int p, int l, int r) {
    tr[p] = {l, r, 0, 0, 0, 0, 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
}

void pushup(int p) {
    int l = tr[p].l, r = tr[p].r;
    if (tr[p].cnt) {
        tr[p].len = X[r + 1] - X[l];
        tr[p].sum = 2;
        tr[p].lcover = tr[p].rcover = 1;
    }
    else {
        tr[p].len = tr[lc].len + tr[rc].len;
        tr[p].sum = tr[lc].sum + tr[rc].sum;
        tr[p].lcover = tr[lc].lcover;
        tr[p].rcover = tr[rc].rcover;
        if (tr[lc].rcover && tr[rc].lcover) {
            tr[p].sum -= 2;
        } 
    }
}

void update(int p, int ql, int qr, int k) {
    if (tr[p].r < ql || tr[p].l > qr) return ;
    if (tr[p].l >= ql && tr[p].r <= qr) {
        tr[p].cnt += k;
        pushup(p);
        return ;
    }
    update(lc, ql, qr, k);
    update(rc, ql, qr, k);
    pushup(p);
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        X[i] = x1;
        X[n + i] = x2;
        L[i] = {x1, x2, y1, 1};
        L[n + i] = {x1, x2, y2, -1};
    }
    n *= 2;
    sort(X + 1, X + 1 + n);
    int m = unique(X + 1, X + 1 + n) - X - 1;
    sort(L + 1, L + 1 + n);

    build(1, 1, m - 1);
    int ans = 0;
    int lst = 0;
    for (int i = 1; i < n; i++) {
        int l = lower_bound(X + 1, X + 1 + m, L[i].x1) - X;
        int r = lower_bound(X + 1, X + 1 + m, L[i].x2) - X;
        update(1, l, r - 1, L[i].tag);
        ans += abs(tr[1].len - lst);
        lst = tr[1].len;
        ans += tr[1].sum * (L[i + 1].y - L[i].y);
    }
    ans += L[n].x2 - L[n].x1;
    cout << ans << '\n';
}

signed main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);

    // int T; cin >> T;
    // while (T--) 
        solve();

    return 0;
}


原文地址：https://blog.csdn.net/LFY20031120/article/details/144347877

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024