算法竞赛模板

排序

m 次随意排列， 注意带最后只询问一个位置的值

可以想到一种神奇的二分法，计>=mid的值为1，其余为0
变成0-1序列后用区间重置线段树可以轻松维护
时间复杂度N^log^2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _ cout << "----------" << endl
#define int ll
int n, m, q;
const int N = 1e5 + 10;
int a[N];
array<int, 3> b[N];

struct tag {
    bool st;
    int v;
    tag(): st(0),v(0) {}
    void apply(tag& T) {
        if (T.st) {
            st = 1;
            v = T.v;
        }
    }
};

struct node {
    int sum, len;
    node(): sum(0), len(1) {}
    void apply(tag& T) {
        if (T.st) {
            sum = len * T.v;
        }
    }
    node operator+ (const node& b) const {
        node tmp;
        tmp.len = len + b.len;
        tmp.sum = sum + b.sum;
        return tmp;
    }
};

struct lazy {
    int n;
    vector<node> tree;
    vector<tag> tg;
    lazy(int _n, vector<node>& b) {
        n = _n;
        tree.assign(4*n,node());
        tg.assign(4*n,tag());
        build(1,n,1,b);
    }

    void up(int p) {
        tree[p] = tree[p<<1] + tree[p<<1|1];
    }
    void build(int l, int r, int p, vector<node>& b) {
        if (l == r) {
            tree[p] = b[l];
            return;
        }
        int mid = l + r >> 1;
        build(l,mid,p<<1,b);
        build(mid+1,r,p<<1|1,b);
        up(p);
    }

    void apply(int p, tag& T) {
        tree[p].apply(T);
        tg[p].apply(T);
    }

    void down(int p) {
        apply(p<<1,tg[p]);
        apply(p<<1|1,tg[p]);
        tg[p] = tag();
    }

    void modify(int ml, int mr, int l, int r, int p, tag& T) {
        if (r < ml || l > mr) return;
        if (l >= ml && r <= mr) {
            apply(p,T);
            return;
        }
        down(p);
        int mid = l + r >> 1;
        modify(ml,mr,l,mid,p<<1,T);
        modify(ml,mr,mid+1,r,p<<1|1,T);
        up(p);
    }

    void modify(int l, int r, tag& T) {
        modify(l,r,1,n,1,T);
    }

    int query(int ql, int qr, int l, int r, int p) {
        if (r < ql || l > qr) return 0;
        if (l >= ql && r <= qr) {   
            return tree[p].sum;
        }
        down(p);
        int mid = l + r >> 1;
        return query(ql,qr,l,mid,p<<1) + query(ql,qr,mid+1,r,p<<1|1);
    }

    int query(int l, int r) {
        return query(l,r,1,n,1);
    }
};

bool check(int mid) {
    vector<node> c(n+1);
    for (int i = 1; i <= n; i++) {
        c[i].sum = (a[i] >= mid);
    }
    lazy tree(n,c);
    for (int i = 1; i <= m; i++) {
        int op = b[i][0], l = b[i][1], r = b[i][2];
        int tot = tree.query(l,r);
        tag T1, T2;
        T1.st = 1, T2.st = 1;
        T1.v = 1, T2.v = 0;
        if (op == 0) {
            tree.modify(r-tot+1,r,T1);
            tree.modify(l,r-tot,T2);
        } else {
            tree.modify(l,l+tot-1,T1);
            tree.modify(l+tot,r,T2);
        }
    } 
    return tree.query(q,q);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i][0] >> b[i][1] >> b[i][2];
    }
    cin >> q;
    int ans = 1;
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            ans = max(ans,mid);
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}