跳转至

NOIP2025

T2 sale

注意到不合法当且仅当最后只剩一个位置却尝试插入一个大小为 \(2\) 的块，并且它的价值大于左边第一个和右边第一个大小为 \(1\) 的块的价值之和。

考虑对这个东西计数，枚举这个大小为 \(2\) 的块和左边第一个大小为 \(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
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int MOD = 998244353;

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

struct myPair {
    int id, val;
    inline bool operator<(const myPair &b) const {
        if(val != b.val) return val < b.val;
        return id < b.id;
    }
} a[N];

int T, n, m, ans;
int inv[N], fac[N], ifac[N], pw2[N];

inline int C(int a, int b) { return (ll)fac[a] * ifac[b] % MOD * ifac[a - b] % MOD; }

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

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

    cin >> T >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 1; i <= n; i++) cin >> a[i].val, a[i].id = i;
        if(m == 1) { cout << qpow(2, n) << '\n'; continue; } m -= 2; ans = 0;
        sort(a + 1, a + 1 + n, [](myPair i, myPair j){ return j < i; });
        for(int i = 1, t = 1; i <= n; i++) {
            while(t < n && 2 * a[t + 1].val > a[i].val) ++t;
            for(int j = i + 1, k = n + 1; j <= t; j++) {
                if(a[j].val == a[i].val) continue;
                while(a[j].val + a[k - 1].val < a[i].val) --k;
                int pre = i - 1, cnt = j - 2;
                if(m < pre || m > pre + cnt) continue;
                add(ans, (ll)C(cnt, m - pre) * pw2[n - k + 1] % MOD);
            }
        }
        cout << (qpow(2, n) - ans + MOD) % MOD << '\n';
    }

    return 0;
}

T4 query

区间的左端点记为 \(i\)，被贡献到的查询点记为 \(p\)。

对于一个左端点 \([i,i+L-1]\sim [i,i+R-1]\)，对完全包含于 \([i,i+L-1]\) 的点，直接产生贡献，可以 st 表先求出每个区间的最大贡献然后单调队列扫一遍。

对于包含于 \([i+L-1,i+R-1]\) 的点 \(p\)，注意到我们只关心 \([p,i+R-1]\) 之间前缀和数组 \(s\) 的最大值。因此从右往左扫描点 \(p\)，用第一个单调队列维护 \([p,p+(R-L)]\) 中 \(s\) 的前缀最大值。

随后，我们只关心相邻两个前缀最大值 \(s_{x},s_{y}\) 之间的满足 \(x\le i+R-1<y\) 的 \(i\)，并且只关心这些 \(i\) 中 \(s_{i-1}\) 的最小值。这个最小值可以用 st 表，也可以在单调队列合并时顺带维护。

记两个前缀最大值之间 \(s_{i-R+1}\) 的最小值为 \(mn\)，跟随第一个单调队列一起维护。现在的问题是，如何 \(O(1)\) 查询出 \(s[que_x]-mn_x\) 的最大值。再用第二个单调队列维护即可。发现第一个 que 的 pop 不会破坏第二个 que 的单调性。