251005 模拟赛

T1

给定一个长为 \(n\) 的序列，每次操作你可以选择一个长为 \(k\) 的区间，将区间内数字都删掉，并在原来的位置插入一个数字，其值等于区间异或和。你需要不断操作直到区间长度等于 \(1\)。保证 \((k-1)\mid (n-1)\)。定义一个操作序列的代价为：插入的所有数字的和。最小化操作代价。

\(n\le 500,~k\le 50\)

考虑区间 dp，设 \(f_{i,j}\) 表示把区间内的数字能删就删，最终剩下 \(<k\) 个数字，最小代价和。若 \((k-1)\mid(len-1)\)，那么最后一次操作一定是把 \(k\) 个数字合成 \(1\) 个，这时考虑最后一次操作之前。此时区间内还剩 \(2\sim k\) 个元素，枚举第一个元素在原序列中对应的区间，容易做到 \(O(\frac{n^3}{k})\)。

T2

给定一个长为 \(n\) 的二元组序列。有一个排列初始为 \(p_i=i\)。一个二元组表示一个操作：交换排列中位于 \(a_i,b_i\) 的两项。有 \(q\) 次询问，每次询问给定区间 \([l,r]\) 和常数 \(k\)，询问从左到右只执行区间内的操作，最终排列的第 \(k\) 项是多少。（询问之间相互独立）。

\(n,q\le 10^6\)

首先容易通过倍增做到 \(O\big((n+q)\log n\big)\)。可以通过本题。

考虑时光倒流，从右到左依次执行每一个操作，那么依次询问等价于询问在执行到 \(r\) 时位于第 \(k\) 项的值在执行到 \(l\) 时位于什么位置。容易做到线性。

T3

发现每个点的答案显然有下界：所有出边 \(r\) 的最小值。发现答案最大的点显然可以取到下界。删掉这个点之后的问题也是容易维护的。

通过维护删边和桶排可以做到线性，但是我不太会。

T4

初始给定一个长为 \(n\) 的序列 \(a\)。一次冒泡排序定义为执行一次以下代码：

for(int i = 1; i < n; i++)
    if(a[i] > a[i + 1]) swap(a[i], a[i + 1]);

有 \(q\) 组询问，每次询问：进行 \(c\) 次冒泡排序之后，区间 \([l,r]\) 的前 \(k\) 小值之和是多少。

\(n,q\le 5\times 10^5\)

官方题解实际上很清楚了，还是建议自己看官方题解思考，实在不知道怎么实现的可以看下面。

先考虑如何求出区间内的第 \(k\) 小值。考虑二分答案，将序列转化为 01 序列。那么一次冒泡排序会将所有 \(0\) 向左移动一位（一段前缀的 \(0\) 不动）。那么最终停留在区间 \([l,r]\) 的 \(0\) 只可能在 \([1,r+c]\) 之间。同时考虑到左边的一些 \(0\) 会溜到 \(l\) 左边，因此分讨 \(c\) 次冒泡之后 \([1,l-1]\) 是否被 \(0\) 填满。发现这时容易判断的，只需查询 \([1,l+c-1]\) 内 \(0\) 的数量。

考虑如何对两种情况分别处理。若 \([1,l+c-1]\) 内 \(0\) 的数量没有填满 \([1,l-1]\)，那么 \(0\) 的数量就等于 \([1,r+c]-[1,l+c-1]\)。否则，多出的 \(0\) 都会追加到后面，可以用 \([1,r+c]-(l-1)\) 计算（这里直接用区间表示区间内 \(0\) 的数量了），即使多统计几个 \(0\) 二分答案也不会有什么问题。

二分答案可以直接在主席树上线段树二分，从而做到单 \(\log\)。

考虑如何求前 \(k\) 项和。这里先把第 \(k\) 小的值求出来，记为 \(v\)。注意到若 \([1,l+c-1]\) 内的 \(0\) 填满了 \([1,l-1]\)，那么不易计算溢出到 \(l-1\) 后面那些 \(0\) 的 \(sum\)。尝试观察性质，发现 \(c\) 次操作之后 \([1,l+c-1]\) 前缀中的前 \(c\) 大都会移动到 \([l,l+c-1]\) 及 \(l+c-1\) 以后，其中后者不会有什么影响，因为交换过来的数字一定更大。也就是说，\(c\) 次冒泡排序把 \([1,l+c-1]\) 的前 \(l-1\) 小都扔到了 \([1,l-1]\)。这可以再通过一次主席树查询得到。

若 \([1,l+c-1]\) 内的 \(0\) 没有填满 \([1,l-1]\)，那么只需要直接减去 \([1,l+c-1]\) 中小于等于 \(v\)（也就是数字 \(0\)）的数字之和就行了。实现中可以分两个函数，一个用来找 \(k\) 小值，另一个用来求 \(k\) 小和，后者传入两个参数 \(v\) 和 \(k\)，表示取 \(\le v\) 所有数字中的前 \(k\) 小，若不足 \(k\) 个则只取 \(\le v\) 的数字，同时返回一个 \(cnt\) 表示到底统计了多少数字。先查 \([1,l+c-1]\) 的贡献，得到 \(cnt\) 后查 \([1,r+c]\) 中 \(\le v\) 的前 \(k+cnt\) 小。

代码

#include<ctype.h>
#include<bits/stl_algobase.h>
#include<cstdio>
#include<cassert>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int LOGN = 21;

struct istream {
    inline istream &operator>>(int &x) {
        char ch;
        while(!isdigit(ch = getchar()));
        x = ch - '0';
        while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
        return *this;
    }
} cin;

struct ostream {
    char buf[60], top = 0;
    inline ostream &operator<<(int x) {
        do buf[++top] = x % 10, x /= 10; while(x);
        while(top) putchar_unlocked(buf[top--] + '0');
        return *this;
    }
    inline ostream &operator<<(char c) {
        putchar_unlocked(c);
        return *this;
    }
    inline ostream &operator<<(const char str[]) {
        for(const char *i = str; *i; i++) putchar(*i);
        return *this;
    }
} cout;

char endl = '\n';

int n, q;
int a[N];

namespace SegT {
    int sz[N * LOGN], sum[N * LOGN], chd[N * LOGN][2];
    int rt[N], nn;
    inline int addNode() {
        sz[++nn] = 0;
        sum[nn] = chd[nn][0] = chd[nn][1] = 0;
        return nn;
    }
    inline void copy(int a, int b) {
        sz[a] = sz[b], sum[a] = sum[b], chd[a][0] = chd[b][0], chd[a][1] = chd[b][1];
    }
    inline void push_up(int p) {
        sz[p] = sz[chd[p][0]] + sz[chd[p][1]];
        sum[p] = sum[chd[p][0]] + sum[chd[p][1]];
    }
    int insert(int p, int l, int r, int q) {
        int cur = addNode();
        if(p) copy(cur, p);
        if(l == r) {
            sz[cur]++; sum[cur] += l;
            return cur;
        }
        int mid = (l + r) >> 1;
        if(q <= mid) chd[cur][0] = insert(chd[cur][0], l, mid, q);
        else chd[cur][1] = insert(chd[cur][1], mid + 1, r, q);
        push_up(cur);
        return cur;
    }
    int query_Kth(int p1, int p2, int l, int r, int k, int ql, int ps1, int ps2) {
        if(l == r) return l;
        int mid = (l + r) >> 1;
        int tmp = sz[chd[p1][0]] + ps1;
        int res = (tmp >= ql - 1) ? (sz[chd[p2][0]] + ps2 - (ql - 1)) : (sz[chd[p2][0]] + ps2 - sz[chd[p1][0]] - ps1);
        if(k <= res) return query_Kth(chd[p1][0], chd[p2][0], l, mid, k, ql, ps1, ps2);
        else return query_Kth(chd[p1][1], chd[p2][1], mid + 1, r, k, ql, ps1 + sz[chd[p1][0]], ps2 + sz[chd[p2][0]]);
    }
    int cnt = 0;
    int query_sumKth(int p, int l, int r, int v, int k) {
        if(l == r) return cnt += min(sz[p], k), min(sz[p], k) * l;
        int mid = (l + r) >> 1;
        if(k <= sz[chd[p][0]] || v <= mid) return query_sumKth(chd[p][0], l, mid, v, k);
        else return cnt += sz[chd[p][0]], query_sumKth(chd[p][1], mid + 1, r, v, k - sz[chd[p][0]]) + sum[chd[p][0]];
    }
    int query(int l, int r, int c, int k) {
        cnt = 0;
        int v = query_Kth(rt[min(n, l + c - 1)], rt[min(n, r + c)], 1, n, k, l, 0, 0);
        int tmp2 = query_sumKth(rt[min(n, l + c - 1)], 1, n, v, l - 1);
        int tmp1 = query_sumKth(rt[min(n, r + c)], 1, n, v, k + cnt);
        return tmp1 - tmp2;
    }
}

using SegT::rt;

signed main() {

    freopen("florist.in", "r", stdin);
    freopen("florist.out", "w", stdout);

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

    for(int i = 1; i <= n; i++) rt[i] = SegT::insert(rt[i - 1], 1, n, a[i]);

    while(q--) {
        int c, l, r, k;
        cin >> c >> l >> r >> k;
        cout << SegT::query(l, r, c, k) << '\n';
    }

    return 0;
}