CF1540D

zhylj · 2022-07-14 10:52:47 · 题解

假设 n,q 同阶，下面的 b_i\gets i-1-b_i 即表示前面比它小的数的个数。

考虑如何还原排列，有两种方法：

第一种方法是，令 i 从小到大遍历，每次就令 p_i=b_i+1，然后令原先大于等于 b_i+1 的数全部 +1。

于是我们得到了确定 p_x 的一个朴素方法：令 j=x+1,x+2,\cdots,n，初始 p_x=b_x+1，每次若 b_j+1\ge p_x，则令 p_x\gets p_x+1。

第二种方法是，令 i 从大到小遍历，维护一个集合 S=\{1,2,\cdots,n\} 表示剩下的数，每次取 S 中第 b_i+1 大的元素即为 p_i。

分大小为 B=\mathcal O(\sqrt n) 的块，然后逐块处理，考虑用第一种方法跳过散块，然后要处理的是如何跳过整块，我们维护从每个块的结尾开始执行第二种方法的结果（即记 S 少了一些元素变为了 S'，维护这些少了的元素以及它们是在哪里被取走了），那么这个块前面的前缀对应的排列（即只保留前缀的 b_i 还原的排列）即会保持相对顺序变为 S' 中的元素。每次累计查询，直到块被修改的时候处理这个修改前的所有询问，给询问以 B 为底做基数排序再 two-pointer 扫一下不难做到正确的复杂度。

对于修改，考虑我们可以轻易利用现有信息将这个块拆开，也可以用类似上面 two-pointer 的方法将两个块的结果归并到一起，于是可以暴力拆成三段，然后修改再归并回去，复杂度也是对的。

时间复杂度 \mathcal O(n\sqrt n)，空间复杂度 \mathcal O(n)。

const int N = 1e5 + 5, B = 320;

struct Ask {
    int opt, x, y;
} Q[N];
int n, q, b[N], _b[N];

std::vector <int> bk[B], bk_2[B];
void Sort(std::vector <int> &p) {
    for(int i : p)
        bk[Q[i].y % B].push_back(i);
    for(int i = 0; i < B; ++i) {
        for(int j : bk[i]) bk_2[Q[j].y / B].push_back(j);
        bk[i].clear();
    }
    p.clear();
    for(int i = 0; i < B; ++i) {
        for(int j : bk_2[i]) p.push_back(j);
        bk_2[i].clear();
    }
}

void Split(std::vector <pii> f, int x,
        std::vector <pii> &f_l, std::vector <pii> &f_r) {
    f_l.clear(); f_r.clear();
    int j = 0;
    for(pii i : f) {
        if(i.se <= x) f_l.push_back(mkp(i.fi - j, i.se));
        else f_r.push_back(i), ++j;
    }
}
void Merge(std::vector <pii> f_l, std::vector <pii> f_r,
        std::vector <pii> &f) {
    f.clear();
    int j = 0;
    for(int i = 0; i < f_l.size(); ++i) {
        for(; j < f_r.size() && f_r[j].fi <= f_l[i].fi + j; ++j)
            f.push_back(f_r[j]);
        f.push_back(mkp(f_l[i].fi + j, f_l[i].se));
    }
    for(; j < f_r.size(); ++j)
        f.push_back(f_r[j]);
}

std::vector <pii> f;
std::vector <int> p;
void Modify(int x, int y) {
    if(b[x] == y) return;
    std::vector <pii> f_l, f_x, f_r;
    Split(f, x - 1, f_l, f_r);
    Split(f_r, x, f_x, f_r);
    f_x[0].fi += y - b[x];
    Merge(f_x, f_r, f_r);
    Merge(f_l, f_r, f);
    b[x] = y;
}
void Jump() {
    if(p.empty()) return;
    Sort(p);
    std::vector <pii> p_f;
    for(int i : p) p_f.push_back(mkp(Q[i].y, -i));
    Merge(p_f, f, p_f);
    for(pii i : p_f)
        if(i.se < 0) Q[-i.se].y = i.fi;
    p.clear();
}

void Solve(int L, int R) {
    f.clear(); p.clear();
    for(int i = R; i >= L; --i)
        Merge((std::vector <pii>) { mkp(b[i] + 1, i) }, f, f);
    for(int i = 1; i <= q; ++i) {
        int opt = Q[i].opt, x = Q[i].x, y = Q[i].y;
        if(opt == 1) {
            if(x > R || x < L) continue;
            Jump();
            Modify(x, y);
        } else if(opt == 2) {
            if(x > R) continue;
            if(x > L) {
                for(int j = std::max(L, x); j <= R; ++j)
                    Q[i].y += (Q[i].y >= b[j] + 1);
            } else p.push_back(i);
        }
    }
    Jump();
}

int main() {
    rd(n);
    for(int i = 1; i <= n; ++i) rd(b[i]), b[i] = i - 1 - b[i];
    memcpy(_b, b, sizeof(_b));
    rd(q);
    for(int i = 1; i <= q; ++i) {
        int opt, x; rd(opt, x);
        if(opt == 1) {
            int y; rd(y); y = x - 1 - y;
            Q[i] = (Ask) { opt, x, y };
            b[x] = y;
        } else {
            Q[i] = (Ask) { opt, x + 1, b[x] + 1 };
        }
    }
    memcpy(b, _b, sizeof(b));
    for(int i = 0; i <= n / B; ++i) {
        int L = std::max(i * B, 1),
            R = std::min((i + 1) * B - 1, n);
        Solve(L, R);
    }
    for(int i = 1; i <= q; ++i)
        if(Q[i].opt == 2) printf("%d\n", Q[i].y);
    return 0;
}