整体二分简单入门

哇马上区域赛了，感觉好多东西都没整理好。

整体二分。整体二分类似于一些决策单调性的分治，可以解决诸多区间第 k 小或区间第 k 大的问题。整体二分 solve(l,r,L,R) 表示答案在 [l,r] 中，与操作 [L,R] 有关（操作 [L,R] 不一定对应原来 [L,R] 的操作）

我们就拿静态区间第 k 小来说好了。如果原序列的数 ≤ mid ，那么就在树状数组中对应位置 +1 。如果碰到询问操作，那么查询询问区间 [ql,qr] 的值相当于查询了区间里面值在 [l,mid] 的个数，如果个数 ≤ k ，那么答案在 [mid+1,r] 中，那么把 k 减掉对应的个数，把操作分到右区间。否则答案在 [l,mid] 中，把操作分到左区间。如果 l=r ，那么直接把 ans 记录一下就好了。时间复杂度 O(n*log^2 n)

这里实现了一下基本的静态区间第k小，分别写了不离散化和离散化的版本，时间差个一半左右吧

另外有个小插曲是终于学到了负数意义下除2和右移结果不一样，除2是向0取整，右移是向负取整。

#include<bits/stdc++.h>

#define inf 1000000000
#define maxn 200010
using namespace std;
int n, m, num, a[maxn], s[maxn], ans[maxn];

struct node {
    int op, x, y, z, o;
} p[maxn * 2], q1[maxn * 2], q2[maxn * 2];

void Insert(int pos, int x) {
    while (pos <= n) {
        s[pos] += x, pos += pos & (-pos);
    }
}

int Query(int pos) {
    int res = 0;
    while (pos) {
        res += s[pos], pos -= pos & (-pos);
    }
    return res;
}

void Dfs(int l, int r, int L, int R) {
//    printf("%d %d %d %d\n", l, r, L, R);
    if (L > R)return;
    if (l == r) {
        for (int i = L; i <= R; i++)if (p[i].op == 2)ans[p[i].o] = l;
        return;
    }
    int p1 = 0, p2 = 0, mid = (l + r) >> 1;
    for (int i = L; i <= R; i++)
        if (p[i].op == 1) {
            if (p[i].x <= mid)Insert(p[i].o, 1), q1[++p1] = p[i];
            else q2[++p2] = p[i];
        } else {
            int cnt = Query(p[i].y) - Query(p[i].x - 1);
            if (cnt >= p[i].z)q1[++p1] = p[i];
            else p[i].z -= cnt, q2[++p2] = p[i];
        }
    for (int i = 1; i <= p1; i++)if (q1[i].op == 1)Insert(q1[i].o, -1);
    for (int i = 1; i <= p1; i++)p[L + i - 1] = q1[i];
    for (int i = 1; i <= p2; i++)p[L + i + p1 - 1] = q2[i];
    Dfs(l, mid, L, L + p1 - 1), Dfs(mid + 1, r, L + p1, R);
}

int main() {
    scanf("%d%d", &n, &m);
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
//        x = rand();
        p[++num] = node{1, x, 0, 0, i};
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
//        x = rand() % n + 1, y = rand() % n + 1;
//        if (x > y)swap(x, y);
//        z = rand() % (y - x + 1) + 1;
        p[++num] = node{2, x, y, z, i};
    }
    Dfs(-inf, inf, 1, num);
    for (int i = 1; i <= m; i++)printf("%d\n", ans[i]);
    return 0;
}


/*离散化版本*/
#include<bits/stdc++.h>

#define maxn 200010
using namespace std;
int n, m, num, a[maxn], b[maxn], s[maxn], ans[maxn];

struct node {
    int op, x, y, z, o;
} p[maxn * 2], q1[maxn * 2], q2[maxn * 2];

void Insert(int pos, int x) {
    while (pos <= n) {
        s[pos] += x, pos += pos & (-pos);
    }
}

int Query(int pos) {
    int res = 0;
    while (pos) {
        res += s[pos], pos -= pos & (-pos);
    }
    return res;
}

void Dfs(int l, int r, int L, int R) {
    if (L > R)return;
    if (l == r) {
        for (int i = L; i <= R; i++)if (p[i].op == 2)ans[p[i].o] = b[l];
        return;
    }
    int p1 = 0, p2 = 0, mid = (l + r) >> 1;
    for (int i = L; i <= R; i++)
        if (p[i].op == 1) {
            if (p[i].x <= mid)Insert(p[i].o, 1), q1[++p1] = p[i];
            else q2[++p2] = p[i];
        } else {
            int cnt = Query(p[i].y) - Query(p[i].x - 1);
            if (cnt >= p[i].z)q1[++p1] = p[i];
            else p[i].z -= cnt, q2[++p2] = p[i];
        }
    for (int i = 1; i <= p1; i++)if (q1[i].op == 1)Insert(q1[i].o, -1);
    for (int i = 1; i <= p1; i++)p[L + i - 1] = q1[i];
    for (int i = 1; i <= p2; i++)p[L + i + p1 - 1] = q2[i];
    Dfs(l, mid, L, L + p1 - 1), Dfs(mid + 1, r, L + p1, R);
}

int main() {
    //freopen("132.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    b[0] = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(b + 1, b + 1 + b[0], a[i]) - b;
        p[++num] = node{1, pos, 0, 0, i};
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        p[++num] = node{2, x, y, z, i};
    }
    Dfs(1, b[0], 1, num);
    for (int i = 1; i <= m; i++)printf("%d\n", ans[i]);
    return 0;
}

还有动态的区间第k小，就是把修改操作拆成两个就好了。

#include<bits/stdc++.h>

#define inf 1000000000
#define maxn 100010
using namespace std;
int n, m, num, a[maxn], s[maxn], ans[maxn];

struct node {
    int op, x, y, z, o;
} p[maxn * 3], q1[maxn * 3], q2[maxn * 3];

void Insert(int pos, int x) {
    while (pos <= n) {
        s[pos] += x, pos += pos & (-pos);
    }
}

int Query(int pos) {
    int res = 0;
    while (pos) {
        res += s[pos], pos -= pos & (-pos);
    }
    return res;
}

void Dfs(int l, int r, int L, int R) {
    if (L > R)return;
    if (l == r) {
        for (int i = L; i <= R; i++)if (p[i].op == 2)ans[p[i].o] = l;
        return;
    }
    int p1 = 0, p2 = 0, mid = (l + r) >> 1;
    for (int i = L; i <= R; i++)
        if (p[i].op == 1) {
            if (p[i].x <= mid)Insert(p[i].o, p[i].y), q1[++p1] = p[i];
            else q2[++p2] = p[i];
        } else {
            int cnt = Query(p[i].y) - Query(p[i].x - 1);
            if (cnt >= p[i].z)q1[++p1] = p[i];
            else p[i].z -= cnt, q2[++p2] = p[i];
        }
    for (int i = 1; i <= p1; i++)if (q1[i].op == 1)Insert(q1[i].o, -q1[i].y);
    for (int i = 1; i <= p1; i++)p[L + i - 1] = q1[i];
    for (int i = 1; i <= p2; i++)p[L + i + p1 - 1] = q2[i];
    Dfs(l, mid, L, L + p1 - 1), Dfs(mid + 1, r, L + p1, R);
}

int main() {
    scanf("%d%d", &n, &m);
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        p[++num] = node{1, a[i], 1, 0, i};
    }
    char s[5];
    for (int i = 1; i <= m; i++) {
        scanf("%s", s);
        if (s[0] == 'Q') {
            scanf("%d%d%d", &x, &y, &z);
            p[++num] = node{2, x, y, z, i};
        } else {
            scanf("%d%d", &x, &y);
            p[++num] = node{1, a[x], -1, 0, x};
            a[x] = y;
            p[++num] = node{1, a[x], 1, 0, x};
        }
    }
    memset(ans, -1, sizeof(ans));
    Dfs(-inf, inf, 1, num);
    for (int i = 1; i <= m; i++)
        if (ans[i] != -1)printf("%d\n", ans[i]);
    return 0;
}
/*离散化 快20％的样子*/
#include<bits/stdc++.h>

#define inf 1000000000
#define maxn 100010
using namespace std;
int n, m, num, a[maxn], b[maxn * 3], s[maxn], ans[maxn];

struct node {
    int op, x, y, z, o;
} p[maxn * 3], q1[maxn * 3], q2[maxn * 3];
struct quer {
    char c;
    int x, y, z;
} q[maxn];

void Insert(int pos, int x) {
    while (pos <= n) {
        s[pos] += x, pos += pos & (-pos);
    }
}

int Query(int pos) {
    int res = 0;
    while (pos) {
        res += s[pos], pos -= pos & (-pos);
    }
    return res;
}

void Dfs(int l, int r, int L, int R) {
    if (L > R)return;
    if (l == r) {
        for (int i = L; i <= R; i++)if (p[i].op == 2)ans[p[i].o] = b[l];
        return;
    }
    int p1 = 0, p2 = 0, mid = (l + r) >> 1;
    for (int i = L; i <= R; i++)
        if (p[i].op == 1) {
            if (p[i].x <= mid)Insert(p[i].o, p[i].y), q1[++p1] = p[i];
            else q2[++p2] = p[i];
        } else {
            int cnt = Query(p[i].y) - Query(p[i].x - 1);
            if (cnt >= p[i].z)q1[++p1] = p[i];
            else p[i].z -= cnt, q2[++p2] = p[i];
        }
    for (int i = 1; i <= p1; i++)if (q1[i].op == 1)Insert(q1[i].o, -q1[i].y);
    for (int i = 1; i <= p1; i++)p[L + i - 1] = q1[i];
    for (int i = 1; i <= p2; i++)p[L + i + p1 - 1] = q2[i];
    Dfs(l, mid, L, L + p1 - 1), Dfs(mid + 1, r, L + p1, R);
}


int main() {
    //freopen("132.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[++b[0]] = a[i];
    }
    char s[5];
    for (int i = 1; i <= m; i++) {
        scanf("%s", s);
        if (s[0] == 'Q') {
            scanf("%d%d%d", &x, &y, &z);
            q[i] = quer{s[0], x, y, z};
        } else {
            scanf("%d%d", &x, &y);
            q[i] = quer{s[0], x, y, 0};
            b[++b[0]] = y;
        }
    }
    sort(b + 1, b + 1 + b[0]);
    b[0] = unique(b + 1, b + 1 + b[0]) - b - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + 1 + b[0], a[i]) - b;
        p[++num] = node{1, a[i], 1, 0, i};
    }
    for (int i = 1; i <= m; i++) {
        if (q[i].c == 'Q') {
            p[++num] = node{2, q[i].x, q[i].y, q[i].z, i};
        } else {
            x = q[i].x;
            y = lower_bound(b + 1, b + 1 + b[0], q[i].y) - b;
            p[++num] = node{1, a[x], -1, 0, x};
            a[x] = y;
            p[++num] = node{1, a[x], 1, 0, x};
        }
    }
    memset(ans, -1, sizeof(ans));
    Dfs(1, b[0], 1, num);
    for (int i = 1; i <= m; i++)
        if (ans[i] != -1)printf("%d\n", ans[i]);
    return 0;
}