251119 模拟赛

T1

签

T2

拆贡献后反射容斥即可。

T3

给你一个长为 \(n\) 的正整数序列 \(a_{1\sim n}\)。称一个有序三元组 \((x,y,z)\) 是合法的，当且仅当 \(1\le x<y<z\le n\) 且 \(y-x\le z-y\)。有 \(q\) 次询问，每次询问给定区间 \([l,r]\)，询问满足 \(l\le x\wedge z\le r\) 的三元组中，\(a_x+a_y+a_z\) 的最大值是多少。

\(n,q\le 5\times 10^5,~1\le a_i\le 10^8\)

考虑什么样的三元组一定不会成为答案。发现如果开区间 \((x,y)\) 存在一个比 \(a_x\) 或 \(a_y\) 更大的数字，那么将 \(a_x\) 或 \(a_y\) 替换为那个更大的数字一定不劣。因此 \((x,y)\) 支配对只有 \(O(n)\) 种。

从右向左对 \(l\) 和支配对的 \(x\) 进行扫描线，问题转化为后缀 ckmax 以及后缀加一个序列的最大值。可以直接用线段树维护。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;

struct Qr {
    int l, r, id;
    inline bool operator<(const Qr &b) const {
        return l < b.l;
    }
} q[N];

struct Op {
    int a, b;
    inline bool operator<(const Op &oth) const {
        return a < oth.a;
    }
};

int n, m;
int a[N], ans[N];
int sta[N], top;

Op op[2 * N]; int nn;

namespace SegT {
    struct Node {
        int mx, ans, tag;
    } tr[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) {
        tr[p].ans = max(tr[lc(p)].ans, tr[rc(p)].ans);
    }
    inline void spread(int p, int tg) {
        tr[p].ans = max(tr[p].ans, tr[p].mx + tg);
        tr[p].tag = max(tr[p].tag, tg);
    }
    inline void push_down(int p) {
        if(tr[p].tag) {
            spread(lc(p), tr[p].tag);
            spread(rc(p), tr[p].tag);
            tr[p].tag = 0;
        }
    }
    void build(int p, int l, int r) {
        if(l == r) return tr[p].mx = a[l], void();
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        tr[p].mx = max(tr[lc(p)].mx, tr[rc(p)].mx);
    }
    void modify(int p, int l, int r, int ql, int qr, int v) {
        if(ql > qr) return;
        if(ql <= l && r <= qr) return spread(p, v);
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(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 <= l && r <= qr) return tr[p].ans;
        int mid = (l + r) >> 1, res = 0; push_down(p);
        if(ql <= mid) res = max(res, query(lc(p), l, mid, ql, qr));
        if(mid < qr) res = max(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

int main() {

    freopen("prophecy.in", "r", stdin);
    freopen("prophecy.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    for(int i = n; i >= 1; i--) {
        while(top && a[i] > a[sta[top]]) --top;
        if(top) op[++nn] = {i, sta[top]};
        sta[++top] = i;
    }
    top = 0;
    for(int i = 1; i <= n; i++) {
        while(top && a[i] > a[sta[top]]) --top;
        if(top) op[++nn] = {sta[top], i};
        sta[++top] = i;
    }
    sort(op + 1, op + 1 + nn);

    cin >> m;
    for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    sort(q + 1, q + 1 + m);

    SegT::build(1, 1, n);

    for(int i = n, j = nn, k = m; i >= 1; i--) {
        while(j && op[j].a == i) SegT::modify(1, 1, n, 2 * op[j].b - op[j].a, n, a[op[j].a] + a[op[j].b]), j--;
        while(k && q[k].l == i) ans[q[k].id] = SegT::query(1, 1, n, 1, q[k].r), k--;
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';

    return 0;
}

T4

给你一个长为 \(n\) 的序列 \(a_{1\sim n}\)。有 \(q\) 次询问，每次询问给定两个正整数 \(k_1,k_2\)，你需要选择 \(\le k_1\) 个第一类区间，以及 \(\le k_2\) 个第二类区间，满足所有区间两两不交，每个第一类区间的贡献为其所有 \(len\ge 2\) 的子区间的平均数的最大值，每个第二类区间的贡献为其所有 \(len\ge 2\) 的子区间的平均数的第 \(P\) 小（\(P\) 是给定的常数，若不存在第 \(P\) 小则取最大值），最大化贡献和。

\(n\le 10^5,~q\le 5\times 10^5,~3\le P\le n^2,~a_i\le 10^9\)

对于一个区间，如果其存在一个子区间的平均数不小于整个区间的平均数，那么将原区间调整为平均数更大的子区间显然不劣；对于一个第二类区间，如果平均数第 \(P\) 小的区间不是其本身，那么可以调整为第 \(P\) 小的那个区间。因此每一个第二类区间都满足 \(\frac{1}{2}len(len-1)\le P\)，每一个选出的区间都满足其平均数比所有子区间的平均数严格大。

由第二个性质可以得到：区间的长度只能为 \(2\) 或 \(3\)，否则将它拆成两个区间，一定有一个区间的平均数不小于本身。又由于 \(P\ge 3\)，因此答案只和 \(k_1+k_2\) 有关。至此我们去掉了所有诈骗的部分。

记 \(k=k_1+k_2\)，转化后的问题显然可以 \(O(n\max k)\) 做。考虑优化，合理猜测答案关于 \(k\) 具有凸性，然后 wqs 二分可以做到 \(O(n\log n)\) 回答单次询问，用闵可夫斯基和优化可以做到 \(O(n\log n)\)。具体的，对序列进行分治，两部分的 dp 数组都具有凸性，合并的过程形如一个 \((\max,+)\) 卷积。跨过分治中心的 \(O(1)\) 个区间分讨一下，只需要记一下区间左右端点各扣掉 \(0/1/2\) 点个即可。

卡常：由于传参部分是瓶颈，因此改成数组显然比 vector 快，这样可以快过 std。

代码

#include<iostream>
#include<iomanip>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

int n, q; ll p;
ll a[N];

ll res[3][3][N], tmp[3][3][N];

void conv(ll c[], ll a[], ll b[], int n, int m, ll offset) {
    if(n < 0 || m < 0) return;
    n = (n >> 1); m = (m >> 1);
    static ll tmp[N];
    int i = 0, j = 0; tmp[0] = 0;
    while(i < n && j < m) {
        if(a[i + 1] - a[i] > b[j + 1] - b[j]) i++, tmp[i + j] = a[i] - a[i - 1];
        else j++, tmp[i + j] = b[j] - b[j - 1];
    }
    while(i < n) i++, tmp[i + j] = a[i] - a[i - 1];
    while(j < m) j++, tmp[i + j] = b[j] - b[j - 1];
    c[0] = max(c[0], offset);
    for(int i = 1; i <= n + m; i++) c[i] = max(c[i], (tmp[i] += tmp[i - 1]) + offset);
}

void solve(int l, int r, ll *res[3][3]) {
    for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
    for(int k = 0; k <= r - l; k++) {
        tmp[i][j][k] = 0;
    }
    if(r - l == 1) {
        res[0][0][1] = (a[l] + a[r]) * 3;
        return;
    } else if(l == r) return;
    int mid = (l + r) >> 1, lel = (mid - l + 1), ler = r - mid;
    ll *lres[3][3], *rres[3][3];
    for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++) {
        lres[i][j] = res[i][j], rres[i][j] = res[i][j] + lel;
    }
    solve(l, mid, lres);
    solve(mid + 1, r, rres);
    for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++) {
        int tl = lel - i, tr = ler - j;
        conv(tmp[i][j], lres[i][0], rres[0][j], tl, tr, 0);
        conv(tmp[i][j] + 1, lres[i][1], rres[1][j], tl - 1, tr - 1, (a[mid] + a[mid + 1]) * 3);
        conv(tmp[i][j] + 1, lres[i][2], rres[1][j], tl - 2, tr - 1, (a[mid - 1] + a[mid] + a[mid + 1]) * 2);
        conv(tmp[i][j] + 1, lres[i][1], rres[2][j], tl - 1, tr - 2, (a[mid] + a[mid + 1] + a[mid + 2]) * 2);
    }
    for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
    for(int k = 0; k <= r - l; k++) {
        res[i][j][k] = tmp[i][j][k];
    }
}

ll ans[N];

int main() {

    freopen("sanwu.in", "r", stdin);
    freopen("sanwu.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    ll *p[3][3];
    for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++) {
        p[i][j] = res[i][j];
    }

    solve(1, n, p);

    for(int i = 1; i <= n; i++) ans[i] = max(ans[i - 1], res[0][0][i]);

    cout << fixed << setprecision(3);
    while(q--) {
        int k1, k2; cin >> k1 >> k2;
        cout << ans[k1 + k2] / 6.0 << '\n';
    }

    return 0;
}