跳转至

250929-251006

250929 模拟赛 T4

给你一个长为 \(n\) 的排列 \(a_{1\sim n}\)，请你将它划分成两个子序列（不交且并为全集），使得第一个子序列 \(b\) 的上升链长度 \(x\)，和第二个子序列 \(c\) 的下降链长度 \(y\) 之和 \(x+y\) 最大。

一个序列的上升链长度定义为：从左边第一个元素开始，每次找到右边第一个更大的元素，然后跳过去，形成一条链；下降链同理。

\(n\le 2\times 10^5\)

考虑朴素 dp，设 \(f_{i,a,b}\) 表示考虑原排列的前 \(i\) 个数，上升链的最后一位是 \(a\)，下降链的最后一位是 \(b\)（也就是两个序列的 \(\max\) 和 \(\min\)），总长度的最大值。枚举当前数字给上升链还是下降链，容易做到 \(O(n^3)\)。

发现 \(a>b\) 时，介于 \([b,a]\) 之间的值不会有贡献；将大于 \(a\) 的数字放到下降链序列中，即可不产生贡献，小于 \(b\) 的数字放到上升链序列中也同理。因此其答案等于后缀中以 \(a,b\) 开头的 LIS 和 LDS 长度之和，而且显然是上界。

发现 \(a<b\) 时，每插入一个新元素，要么转化成 \(a>b\) 的情况，要么 \(a,b\) 不变，要么变为 \(a,x\) 或 \(x,b\)（\(a<x<b\)）。因此 \(a<b\) 时，\(a,b\) 一定是前缀值域中相邻的两项，也即本质不同的 \((a,b)\) 状态只有 \(O(n)\) 种。考虑用线段树优化，动态维护 \(a<b\) 情况中 \(f_{i,a}\) 的值，发现插入一个元素只直接改变 \(O(1)\) 个状态，因此容易维护。

考虑如何处理 \(a<b\) 变为 \(a>b\) 然后直接统计答案的贡献。我们需要动态维护从某个点开始的后缀 LIS 和 LDS。可以倒着扫一遍，考虑“二分法求 LIS 和 LDS”中记录的：长度为 \(i\) 的 LIS 和 LDS 的开头最大/最小是多少，查询以一个数开头的 LIS 或者 LDS 就是在这个数组中 lower_bound。发现插入一个数字只会对一段区间 \(+1\)，因此是好做的。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

struct Range {
    int l, r;
} olis[N], olds[N];

int n, ans;
int a[N];

int lis[N], lds[N], li, ld;
int len_i[N], len_d[N];

namespace SegT1 {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void spread(int p, int tg) { tag[p] += tg; mx[p] += tg; }
    inline void push_down(int p) { if(tag[p]) spread(lc(p), tag[p]), spread(rc(p), tag[p]), tag[p] = 0; }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { spread(p, v); return; }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql > qr) return -INF;
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1, res = 0; push_down(p);
        if(ql <= mid) res = query(lc(p), l, mid, ql, qr);
        if(mid < qr) res = max(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

namespace SegT2 {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void spread(int p, int tg) { tag[p] += tg; mx[p] += tg; }
    inline void push_down(int p) { if(tag[p]) spread(lc(p), tag[p]), spread(rc(p), tag[p]), tag[p] = 0; }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { spread(p, v); return; }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql > qr) return -INF;
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1, res = 0; push_down(p);
        if(ql <= mid) res = query(lc(p), l, mid, ql, qr);
        if(mid < qr) res = max(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

set<int> st;

int main() {

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

    for(int i = 1; i <= n + 1; i++) lds[i] = n + 1;
    for(int i = n; i >= 1; i--) {
        int p = lower_bound(lds + 1, lds + 1 + ld, a[i]) - lds;
        olds[i] = (Range){a[i], lds[p] - 1};
        lds[p] = a[i]; ld = max(ld, p);
        len_d[i] = p;
    }
    for(int i = n; i >= 1; i--) {
        int p = upper_bound(lis + 1, lis + 1 + li, a[i], [](int a, int b) { return a > b; } ) - lis;
        olis[i] = (Range){lis[p] + 1, a[i]};
        lis[p] = a[i]; li = max(li, p);
        len_i[i] = p;
    }

    for(int i = 1; i <= n; i++) SegT1::add(1, 0, n, olds[i].l, olds[i].r, 1);
    for(int i = 1; i <= n; i++) SegT2::add(1, 0, n, olis[i].l, olis[i].r, 1);

    st.insert(0);
    st.insert(n + 1);
    for(int i = 1; i <= n; i++) {
        int pre = *--st.lower_bound(a[i]);
        int nxt = *st.upper_bound(a[i]);
        st.insert(a[i]);
        SegT1::add(1, 0, n, pre, nxt - 1, 1);
        SegT2::add(1, 0, n, pre, nxt - 1, 1);
        SegT1::add(1, 0, n, olds[i].l, olds[i].r, -1);
        SegT2::add(1, 0, n, olis[i].l, olis[i].r, -1);
        ans = max(ans, SegT1::query(1, 0, n, 0, pre - 1) + len_i[i]);
        ans = max(ans, SegT2::query(1, 0, n, nxt, n) + len_d[i]);
    }

    cout << ans << endl;

    return 0;
}

251004 模拟赛

T1

只需注意到 \(7\times 11\times 13=1001\)，然后简单分讨或者暴力枚举 27 种解（为什么全场只有我一个人没用分讨的）即可。

不开 long long 挂成 \(50\)。

T2

给定两个整数三元组 \(a,b\)，一次操作你可以选择三个数中的某几个数，将他们乘以一个整数或者加上一个整数，问你最少操作多少次可以把 \(a\) 变成 \(b\)。

\(|v|\le 10^9\)

暴力分讨即可。注意到答案不超过 \(3\)，其中 \(0,1\) 都是好判的。对于 \(2\)，先把一个数字相等的情况判掉；分讨两次操作操作的数字是否具有包含关系：若不交，那么枚举操作一个数字，然后对剩下的部分 check1（判断一次能否成功）。若交叉，发现只有很少的情况（一个数字被操作两遍，两个数字被操作一遍），在外面枚举全排列，里面枚举两次操作即可。若包含，先判掉重合的情况；若乘法包含加法，那么加法一定可以放在后面执行，乘法操作三个数，因此可以知道乘数；若加法包含乘法，由于乘法至少也至多对两个数字操作，因此乘数容易得到。

Code

T3

初始给你 \(n\) 个区间 \([l_i,r_i]\)，有 \(q\) 次询问，每次询问给你 \(m\) 个点 \(p_{1\sim m}\)，问你有多少个区间满足其内部恰好包含奇数个点。

\(n,q,l_i,r_i\le 5\times 10^5,~\sum m\le n\)

对 \(m\) 根号分治，设阈值为 \(B\)，对于 \(m\le B\)，发现合法区间形如 \(m^2\) 组限制，由于 \(\sum m^2\) 是 \(nB\) 级别的，因此直接暴力二维数点，用分块平衡即可。对于 \(m>B\)，这样的询问不超过 \(\frac nB\) 个，每次询问直接暴力 \(O(n)\) 扫一遍。时间复杂度 \(O(n\sqrt n)\)。

也可以用别的方法。考虑一个区间对哪些询问有贡献。虽然看着没什么前途，但是如果变化量较小的话还是有办法维护的。用莫队维护，那么上面的东西是容易求得的，但考虑如何合并各区间的贡献。发现莫队扩展的过程形如单点 flip，在 \(0\to 1\) 时贡献提前计算，减掉区间左端点；在 \(1\to 0\) 时再加上区间右端点即可。时间复杂度 \(O(n\sqrt n)\)。虽然跑得没有他们快，但是空间小的离谱（\(13.2\)M）。

Code

T4

给定 \(n\times m\) 的网格图（坐标从 \((1,1)\) 到 \((n,m)\)），问所有顶点在整点上的三角形，轮廓上整点数量之和是多少。

\(n,m\le 10^6,~T\le 5\)

不妨设 \(m\le n\)。

从点或者三角形统计贡献不好做，考虑统计一条边的贡献。对于一条横纵坐标差分别为 \((\Delta x,\Delta y)\) 的边，其上有 \(\gcd(\Delta x,\Delta y)\) 个整点（两个端点只计算一个），而第三个点可以取平面内任意不共线的点，可以取 \(nm\) 个点之后减去共线的情况。共线的情况也是简单的，一个退化成线段的三角形上有 \(2\gcd(\Delta x,\Delta y)\) 个整点，第三个点又可以取所有整点，而取在两个端点上的情况只会把三角形上的其他整点统计一遍，因此加起来也是两遍，正好又是 \(\gcd(x,y)\) 遍。可以列出答案的式子：

\[ \begin{align*} ans1&=\sum_{i=1}^{n}i(n-i)nm(m-1)+\sum_{i=1}^{m}i(m-i)nm(n-1)\\ ans2&=2nm\sum_{x=1}^{n-1}\sum_{y=1}^{m-1}\gcd(x,y)(n-x)(m-y)\\ ans3&=4\sum_{x=1}^{n-1}\sum_{y=1}^{m-1}\gcd(x,y)^2(n-x)(m-y)\\ \end{align*} \]

答案就是 \(ans1+ans2-ans3\)。其中 \(ans2,ans3\) 乘以 \(2\) 是因为线段有两种倾斜方向。

把 \((n-x)(m-y)\) 拆成 \(4\) 项，就变成 P3768 简单的数学题 了，但是由于 \(n,m\) 不等，因此要用莫反。枚举 \(\gcd\)，然后莫反：

\[ \begin{align*} \sum_{d_1=1}^{m}d_1\sum_{x=1}^{\lfloor\frac{n}{d_1}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1}\rfloor}(d_1x)(d_1y) [\gcd(x,y)=1]&=\sum_{d_1=1}^{m}(d_1)^3\sum_{x=1}^{\lfloor\frac{n}{d_1}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1}\rfloor}xy[\gcd(x,y)=1]\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}(d_2x)(d_2y)\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^2\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}xy\\ &=\sum_{d_1=1}^{m}(d_1)^3\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^2\frac{\lfloor\frac{n}{d_1d_2}\rfloor(\lfloor\frac{n}{d_1d_2}\rfloor+1)}{2} \frac{\lfloor\frac{m}{d_1d_2}\rfloor(\lfloor\frac{m}{d_1d_2}\rfloor+1)}{2}\\ \end{align*} \]

考虑到拆 \((n-x)(m-y)\) 出来的四项不尽相同，外面的系数和内部 \(x,y\) 的次数也不一样，但推出来的式子都是如下的形式：

\[ \sum_{d_1=1}^{m}(d_1)^a\sum_{d_2=1}^{\lfloor\frac{m}{d_1}\rfloor}\mu(d_2)(d_2)^b\sum_{x=1}^{\lfloor\frac{n}{d_1d_2}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d_1d_2}\rfloor}x^cy^d \]

反正都能做就是了。

直接整除分块套整除分块，外层 \(d_1\) 内层 \(d_2\)，同时对 \(n,m\) 两个数整除分块即可，时间复杂度 \(O(n+Tn^{3/4})\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#define int __int128
using namespace std;
const int N = 1e6 + 10;

void read(int &x) {
    char ch;
    while(!isdigit(ch = getchar()));
    x = ch - '0';
    while(isdigit(ch = getchar())) x = x * 10 + ch - '0';
}

void write(int x) {
    if(x == 0) putchar('0');
    char buf[60], top = 0;
    while(x) buf[++top] = x % 10, x /= 10;
    while(top) putchar(buf[top--] + '0');
}

int T, n, m;
int ans1, ans2, ans3;

int s[2][N];

int sum(int n, int a) {
    if(a == 0) return n;
    if(a == 1) return n * (n + 1) / 2;
    if(a == 2) return n * (n + 1) * (2 * n + 1) / 6;
    if(a == 3) return s[0][n];
    return s[1][n];
}

int npri[N], pri[N], pcnt;
int mu[N][3];

int calc(int a, int b, int c, int d) {
    int ans = 0;
    for(int l1 = 1, r1; l1 <= m; l1 = r1 + 1) {
        r1 = min(n / (n / l1), m / (m / l1));
        int n1 = n / l1, m1 = m / l1, res = 0;
        for(int l2 = 1, r2; l2 <= m1; l2 = r2 + 1) {
            r2 = min(n1 / (n1 / l2), m1 / (m1 / l2));
            res += (mu[r2][b] - mu[l2 - 1][b]) * sum(n1 / l2, c) * sum(m1 / l2, d);
        }
        ans += res * (sum(r1, a) - sum(l1 - 1, a));
    }
    return ans;
}

void solve() {
    ans1 = ans2 = ans3 = 0;
    if(n < m) swap(n, m);
    for(int i = 1; i <= n; i++) ans1 += i * (n - i) * m * (m - 1) * n;
    for(int i = 1; i <= m; i++) ans1 += i * (m - i) * n * (n - 1) * m;
    ans2 = n * m * calc(1, 0, 0, 0) - n * calc(2, 1, 0, 1) - m * calc(2, 1, 1, 0) + calc(3, 2, 1, 1);
    ans2 = 2 * n * m * ans2;
    ans3 = n * m * calc(2, 0, 0, 0) - n * calc(3, 1, 0, 1) - m * calc(3, 1, 1, 0) + calc(4, 2, 1, 1);
    ans3 = 4 * ans3;
    write(ans1 + ans2 - ans3);
    putchar('\n');
}

signed main() {

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

    mu[1][0] = 1;
    for(int i = 2; i < N; i++) {
        if(!npri[i]) { mu[i][0] = -1; pri[++pcnt] = i; }
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] >= N) break;
            npri[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                mu[i * pri[j]][0] = 0;
                break;
            } else {
                mu[i * pri[j]][0] = -mu[i][0];
            }
        }
    }

    for(int i = 1; i < N; i++) mu[i][1] = mu[i - 1][1] + mu[i][0] * i;
    for(int i = 1; i < N; i++) mu[i][2] = mu[i - 1][2] + mu[i][0] * i * i;
    for(int i = 1; i < N; i++) mu[i][0] = mu[i - 1][0] + mu[i][0];

    for(int i = 1; i < N; i++) s[0][i] = s[0][i - 1] + i * i * i;
    for(int i = 1; i < N; i++) s[1][i] = s[1][i - 1] + i * i * i * i;

    read(T);
    while(T--) {
        read(n), read(m);
        solve();
    }

    return 0;
}

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\) 小。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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;
}

251006 模拟赛

T3

给你两个图 \(G_1,G_2\)，点集相同，边集不同，边有边权。你可以选择两个整数权值 \(a,b\)，然后保留 \(G_1\) 中边权不超过 \(a\) 的边，和 \(G_2\) 中边权不超过 \(b\) 的边。称两个点是连通的，要么他们在第一个图中连通，要么在第二个图中连通。请你最小化 \(a+b\) 的值，使得相互连通的点对数量不小于给定的常数 \(k\)。

\(n,m_1,m_2\le 2\times 10^5,~k\le\frac{n(n+1)}{2}\)

首先，\(a,b\) 一个上升，另一个就下降，反之亦然，具有单调性。考虑双指针，对一个图维护加边，另一个图维护删边，动态维护连通点对数。发现点对数可以拆成在 \(G_1'\) 中连通，\(G_2'\) 中连通，同时在 \(G_1',G_2'\) 中连通三部分，分别记为 \(ans1,ans2,ans3\)，那么在 \(ans1+ans2-ans3\ge k\) 时更新答案即可。其中 \(ans1,ans2\) 是好做的。对于 \(ans3\)，考虑给 \(G_1'\) 和 \(G_2'\) 中的每个连通块赋一个随机权值，并定义一个点的权值等于其在两个图中两个连通块权值的异或。用哈希表维护所有异或值，容易在哈希表内维护 \(ans3\)。删边和加边操作直接启发式合并即可。时间复杂度 \(O(n\log n)\)。

Code