251120 模拟赛

T1

都说了签到题

T2

给定一个无向图，点有点权和颜色，颜色只有黑白两种。你可以进行任意次操作，每次操作可以选择一条边 \((u,v)\)，然后依次执行一下两个操作：

• 交换 \(a_u,a_v\)；
• 若 \(u,v\) 颜色相同，则同时反转，否则不变；

给定两个局面，问能否从一个局面变为另一个局面。

\(\sum n,m\le 10^5,~a_i\le 10^6\)，不包含自环，可能有重边，不一定连通。

操作的形式非常不好看，对它进行转化。发现操作等价于先交换两点的点权和颜色，再反转颜色。点权构成的可重集相等显然是一个必要条件。

对于二分图，一个点被交换到左侧时的颜色是恒定的。也就是说只要 点权，在左侧时的颜色 组成的二元组构成的可重集是相等的，那么两个局面就可以相互到达（假定图连通）。

对于非二分图，先考虑奇环怎么做。手模一些 \(n\) 很小的情况，发现在奇环上我们可以在不改变点权排布的情况下反转相邻两个点的颜色。考虑原图的一个二分连通子图，我们可以用它把需要的点交换到奇环上，然后反转颜色。此时只需要两种颜色分别在两个局面对应节点数量的差都是偶数即可。

需要对每个连通块分别统计。

T3

给定 \(n,x,y\)，定义

\[ f(a,b)=\sum_{i=a}^{n-b}\binom{i}{a}x^{i-a}\binom{n-i}{b}y^{n-i-b} \]

对所有 \(2\le a+b\le n\) 且 \(1\le a,b\le 5000\) 求出 \(f(a,b)\bmod 998244353\) 的值。

\(x^{-a}y^{n-b}\) 直接扔出来，设 \(z=\frac{x}{y}\)，式子变成：

\[ \sum_{i=a}^{n-b}\binom{i}{a}\binom{n-i}{b}z^{i} \]

仿照梦现时刻的做法，拆开组合数：

\[ \begin{align*} \sum_{i=a}^{n-b}\binom{i}{a}\binom{n-i}{b}z^{i}&=\sum_{i=a}^{n-b}\Bigg(\binom{i+1}{a+1}-\binom{i}{a+1}\Bigg)\binom{n-i}{b}z^i\\ &=\sum_{i=a}^{n-b}\binom{i+1}{a+1}\Bigg(\binom{n-i-1}{b}+\binom{n-i-1}{b-1}\Bigg)z^{i}-\binom{i}{a+1}\binom{n-i}{b}z^i \end{align*} \]

于是可以得到 \(f(a,b)\) 从 \(f(a-1,b),f(a,b-1)\) 的递推式。边界条件单独讨论一下即可。另外，递推式在 \(z=1\) 时会有问题，此时直接用一个形似范德蒙德卷积的式子算一下就行。

代码

#include<iostream>
#define int long long
using namespace std;
const int N = 5010;
const int MOD = 998244353;

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int n, x, y, z, q;

int inv[2 * N];
int f[N][N], g[2 * N];
int pwx[N], pwy[N];

signed main() {

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

    inv[1] = 1;
    for(int i = 2; i < 2 * N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;

    cin >> n >> x >> y;
    z = x * qpow(y, MOD - 2) % MOD;

    pwx[0] = pwy[0] = 1;
    pwx[1] = qpow(x, MOD - 2); pwy[1] = qpow(y, MOD - 2);
    for(int i = 2; i < N; i++) pwx[i] = pwx[i - 1] * pwx[1] % MOD;
    for(int i = 2; i < N; i++) pwy[i] = pwy[i - 1] * pwy[1] % MOD;

    int c1 = z * qpow(MOD + 1 - z, MOD - 2) % MOD;
    int c3 = qpow(y, n);
    if(z == 1) {
        g[0] = 1;
        for(int i = 1; i < 2 * N; i++) g[i] = g[i - 1] * (n - i + 2) % MOD * inv[i] % MOD;
        cin >> q;
        while(q--) {
            int a, b; cin >> a >> b;
            cout << g[a + b + 1] * pwx[a] % MOD * c3 % MOD * pwy[b] % MOD << '\n';
        }
        return 0;
    } else {
        f[0][0] = (qpow(z, n + 1) - 1) * qpow(z - 1, MOD - 2) % MOD;
        for(int i = 1, j = 1, c2 = qpow(z, n); i < N; i++) {
            f[i][0] = (f[i - 1][0] - (j + j * (n - i + 1) % MOD * inv[i] % MOD) * c2 % MOD + MOD) * c1 % MOD;
            j = j * (n - i + 1) % MOD * inv[i] % MOD;
        }
        for(int i = 1, j = 1, c2 = qpow(z - 1, MOD - 2); i < N; i++) {
            f[0][i] = (f[0][i - 1] - (j + j * (n - i + 1) % MOD * inv[i] % MOD) % MOD + MOD) * c2 % MOD;
            j = j * (n - i + 1) % MOD * inv[i] % MOD;
        }
    }
    int ix = qpow(z, MOD - 2);
    for(int i = 1; i < N; i++) {
        for(int j = 1; j < N; j++) {
            f[i][j] = c1 * (f[i - 1][j] - ix * f[i][j - 1] % MOD + MOD) % MOD;
        }
    }

    cin >> q;
    while(q--) {
        int a, b; cin >> a >> b;
        cout << f[a][b] * pwx[a] % MOD * c3 % MOD * pwy[b] % MOD << '\n';
    }

    return 0;
}

T4

有 \(10^9\) 个花盆排成一列，初始都未种花。给定 \(n\) 个区间 \((l_i,r_i]\)，每次找到区间内未种花数量最少且未被选择过的区间（相同时选择编号更小的一个），将它内部全都种满花，直到所有区间都被选择。输出每次选择的区间。

保证短区间一定比长区间编号小。

\(n\le 10^5\)

如果一个区间被另一个区间包含了，那么前者一定比后者先选到，相等时由区间编号判断。因此动态维护当前所有不被包含的区间，不难发现它们的左右端点都是严格上升的。

用线段树对有效区间进行维护，每次取权值最小的一个，用并查集找到其内部所有没有种花的区间，依次将它们种满。一个小区间会贡献到一段连续的有效区间，用线段树上二分找到两个端点即可。

删掉一个区间后可能会有一些区间成为新的有效区间。先在一开始将所有区间按照 \(r_i\) 为第一关键字，\(-l_i\) 为第二关键字，\(i\) 为第三关键字进行排序，然后取出所有 \(l_i\) 的严格前缀最大值作为初始的关键区间。再用一个线段树维护所有非有效区间，把所有新成为前缀最大值的区间拿出来扔到第一棵线段树里，其权值需要再用一个树状数组维护。

代码

#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int N = 2.5e5 + 10;
const int INF = 0x7fffffff;

struct Range {
    int l, r, w, id;
    inline bool operator<(const Range &b) const {
        if(r != b.r) return r < b.r;
        if(l != b.l) return l > b.l;
        return id < b.id;
    }
    inline bool operator>(const Range &b) const {
        return b < *this;
    }
    inline bool operator==(const Range &b) const {
        return id == b.id;
    }
} a[N];

int n;
int swp[N];
int num[2 * N], nn;
void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i].l, num[++nn] = a[i].r;
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) {
        a[i].l = lower_bound(num + 1, num + 1 + nn, a[i].l) - num;
        a[i].r = lower_bound(num + 1, num + 1 + nn, a[i].r) - num;
    }
}

namespace SegT1 {
    struct Node {
        int mnl, mxl, mn, mnp, tag;
    } tr[8 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        int l = lc(p), r = rc(p);
        tr[p].mnl = min(tr[l].mnl, tr[r].mnl);
        tr[p].mxl = max(tr[l].mxl, tr[r].mxl);
        if(tr[l].mn < tr[r].mn || tr[l].mn == tr[r].mn && tr[l].mnp < tr[r].mnp) {
            tr[p].mn = tr[l].mn, tr[p].mnp = tr[l].mnp;
        } else tr[p].mn = tr[r].mn, tr[p].mnp = tr[r].mnp;
    }
    inline void spread(int p, int tg) { tr[p].mn += tg, 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() {
        for(int i = 0; i <= 4 * nn; i++) tr[i].mn = tr[i].mnl = INF;
    }
    void insert(int p, int l, int r, Range &v) {
        if(l == r) {
            tr[p].mn = v.w; tr[p].mnl = tr[p].mxl = v.l; tr[p].mnp = v.id;
            return;
        }
        int mid = (l + r) >> 1; push_down(p);
        if(v.r <= mid) insert(lc(p), l, mid, v);
        else insert(rc(p), mid + 1, r, v);
        push_up(p);
    }
    void erase(int p, int l, int r, int q) {
        if(l == r) {
            tr[p].mn = tr[p].mnl = INF; tr[p].mnp = tr[p].mxl = 0;
            return;
        }
        int mid = (l + r) >> 1; push_down(p);
        if(q <= mid) erase(lc(p), l, mid, q);
        else erase(rc(p), mid + 1, r, q);
        push_up(p);
    }
    void add(int p, int l, int r, int q) {
        if(tr[p].mnl > q) return;
        if(tr[p].mxl <= q && q < l) return spread(p, -(num[q + 1] - num[q]));
        int mid = (l + r) >> 1; push_down(p);
        if(mid > q) add(lc(p), l, mid, q);
        add(rc(p), mid + 1, r, q);
        push_up(p);
    }
}

namespace SegT2 {
    priority_queue<Range, vector<Range>, greater<Range>> q1[2 * N], q2[2 * N];
    int mx[8 * 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)]); }
    void build() {
        for(int i = 0; i <= 4 * nn; i++) mx[i] = -1;
        for(int i = 1; i <= nn; i++) q1[i].push({-1, INF, 0, 0});
    }
    void insert(int p, int l, int r, Range &v) {
        if(l == r) {
            q1[l].push(v);
            mx[p] = q1[l].top().l;
            return;
        }
        int mid = (l + r) >> 1;
        if(v.r <= mid) insert(lc(p), l, mid, v);
        else insert(rc(p), mid + 1, r, v);
        push_up(p);
    }
    void erase(int p, int l, int r, Range &v) {
        if(l == r) {
            q2[l].push(v);
            while(!q2[l].empty() && q1[l].top() == q2[l].top()) q1[l].pop(), q2[l].pop();
            mx[p] = q1[l].top().l;
            return;
        }
        int mid = (l + r) >> 1;
        if(v.r <= mid) erase(lc(p), l, mid, v);
        else erase(rc(p), mid + 1, r, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr, int lim) {
        if(r < ql || l > qr) return -1;
        if(mx[p] < lim) return -1;
        if(l == r) return q1[l].top().id;
        int mid = (l + r) >> 1;
        int res = query(lc(p), l, mid, ql, qr, lim);
        if(~res) return res;
        return query(rc(p), mid + 1, r, ql, qr, lim);
    }
}

namespace BIT {
    int sum[2 * N];
    inline void add(int p, int v) {
        for(int i = p + 2; i <= nn + 5; i += i & -i) sum[i] += v;
    }
    inline int query(int l, int r) {
        int res = 0;
        for(int i = l + 1; i; i -= i & -i) res -= sum[i];
        for(int i = r + 2; i; i -= i & -i) res += sum[i];
        return res;
    }
}

int fa[2 * N];
int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); }

void fill(int l, int r) {
    for(int i = find(l); i <= r; i = find(i)) {
        SegT1::add(1, 1, nn, i);
        BIT::add(i, -(num[i + 1] - num[i]));
        fa[i] = find(i + 1);
    }
}

set<Range> valid;

int main() {

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

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r, a[i].id = i;

    lisanhua();
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) swp[a[i].id] = i;
    for(int i = 1; i <= nn; i++) fa[i] = i;
    for(int i = 1; i <= nn - 1; i++) BIT::add(i, num[i + 1] - num[i]);

    SegT1::build();
    SegT2::build();
    for(int i = 1, mn = -1; i <= n; i++) {
        a[i].w = num[a[i].r] - num[a[i].l];
        if(a[i].l > mn) SegT1::insert(1, 1, nn, a[i]), valid.insert(a[i]), mn = a[i].l;
        else SegT2::insert(1, 1, nn, a[i]);
    }

    for(int cnt = 1; cnt <= n; cnt++) {
        int cur = swp[SegT1::tr[1].mnp];
        cout << a[cur].id << ' ';
        SegT1::erase(1, 1, nn, a[cur].r);
        valid.erase(a[cur]);
        fill(a[cur].l, a[cur].r - 1);
        auto it = valid.lower_bound(a[cur]);
        int preR, nxtR, preL;
        if(it != valid.end()) nxtR = it->r - 1;
        else nxtR = nn;
        if(it != valid.begin()) preR = (--it)->r + 1, preL = it->l + 1;
        else preR = 1, preL = 0;
        int tmp = SegT2::query(1, 1, nn, preR, nxtR, preL);
        while(~tmp) {
            tmp = swp[tmp];
            SegT2::erase(1, 1, nn, a[tmp]);
            a[tmp].w = BIT::query(a[tmp].l, a[tmp].r - 1);
            SegT1::insert(1, 1, nn, a[tmp]); valid.insert(a[tmp]);
            tmp = SegT2::query(1, 1, nn, a[tmp].r + 1, nxtR, a[tmp].l + 1);
        }
    }
    cout << endl;

    return 0;
}