专栏文章

题解：P11505 [NordicOI 2018] Mysterious Array

NNazq
P11505题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1i17k
此快照首次捕获于
2025/12/02 11:50
3 个月前
此快照最后确认于
2025/12/02 11:50
3 个月前
查看原文
一个限制 l,r,xl, r, x 等价于 x∈a[l,r]x\in a[l, r] 且 1∼x−11\sim x - 1 都在 [1,l−1]∪[r+1,n][1, l - 1]\cup [r + 1, n]。考虑处理出每个 xx 能在哪些区间。
注意到，每个 xx 所在区间要么包含要么相离，所以考虑树上考虑这个问题。
一个限制只会影响 ≤x\le x 的元素，而我们已填的数不能影响后面的填数，所以按 xx 从大到小考虑。
若干相同的限制，只能在这些限制 [l,r][l, r] 的交集，[1,x−1][1, x - 1] 只能在这些限制 [1,l−1]∪[r+1,n][1, l - 1]\cup [r + 1, n] 的交集。
然后统计方案数。
当前子树 TT 会分出两个儿子。一个是 xx 的，一个是 [1,x−1][1, x - 1] 的。
设 xx 子树内元素个数为 ll； 划分完后，可能存在一些区间，既不能有 xx 也不能有 [1,x−1][1, x - 1]。设这样位置有 tt 个； 当前子树还有 tottot 个数 >x\gt x。
贡献组成：
  • xx 在子树内选一个位置，贡献为 ll。
  • 一个是这个子树内 >x\gt x 的数的贡献，从这些数中选出 l−1l - 1 个数并排列放在 xx 所在子树，选出 tt 个数并排列放在只能放 >x\gt x 的位置，剩下的递归去算，Atotl+t−1A_{tot}^{l + t - 1}。
  • 一个是 [1,x−1][1, x - 1] 所在子树，递归下去算。
递归到底层后，贡献就是剩下数个数的阶乘。
实现时，用 set 维护当前子树的可选位置的集合，即前面限制的 [1,l−1]∪[r+1,n][1, l - 1]\cup [r + 1, n] 的交集。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, l, r) for(int i = (l); i <= (r); ++i)
#define per(i, r, l) for(int i = (r); i >= (l); --i)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define ZERO { cout << "0"; exit(0); }
const int N = 2e5 + 5, mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    a %= mod;
    ll ans = 1;
    while(b) {
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int n, q, fac[N], ifac[N];
ll C(int n, int m) {
    if(n < m || m < 0)return 0LL;
    return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
struct Limit {
    int l, r, x;
} p[N];
bool cmpX(Limit &a, Limit &b) {
    return a.x > b.x;
}
set<int> pos;
ll ans = 1;
void solve(int ql, int qr) {
    if(ql > qr) return;
    int lmi = n, lmx = 0, rmi = n, rmx = 0, x = p[ql].x;
    rep(i, ql, qr) {
        lmi = min(lmi, p[i].l);
        lmx = max(lmx, p[i].l);
        rmi = min(rmi, p[i].r);
        rmx = max(rmx, p[i].r);
    }
    // x \in [lmx, rmi]
    if(lmx > rmi) ZERO;
    // [1, x-1] in [1, lmi-1] U [rmx+1, n]
    if(lmi - 1 < 1 && rmx + 1 > n && x > 1) ZERO;
    if(pos.size() - x < 0) ZERO;
    int tot = pos.size();
    auto itl = pos.lower_bound(lmx);
    auto itr = itl;
    if(itl == pos.end() || *itl > rmi) ZERO;
    int l = 0, t = 0;
    while(itr != pos.end() && *itr <= rmi)itr++, l++;
    pos.erase(itl, itr);
    if(x > 1 && pos.empty()) ZERO;

    itl = pos.lower_bound(lmi);
    itr = itl;
    while(itr != pos.end() && *itr <= rmx)itr++, t++;
    pos.erase(itl, itr);

    if(x - 1 > pos.size()) ZERO;

    ans = 1LL * ans * l % mod * C(tot - x, l + t - 1) % mod* fac[l + t - 1] % mod;
}
int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    cin >> n >> q;
    fac[0] = 1;
    rep(i, 1, n) fac[i] = 1LL * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    per(i, n - 1, 0) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
    assert(ifac[0] == 1);
    rep(i, 1, q)cin >> p[i].l >> p[i].r >> p[i].x;
    sort(p + 1, p + q + 1, cmpX);

    rep(i, 1, n) pos.insert(i);
    for(int i = 1, las = 1; i <= q + 1; ++i) {
        if(i == q + 1 || p[i].x != p[i - 1].x) {
            solve(las, i - 1);
            las = i;
        }
    }
    ans = 1LL * ans * fac[pos.size()] % mod;
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...