I 小鸡的排列构造的 checker

看题第一反应是主席树。

定义 lst[x]lst[x] 表示值 xx 出现的下标（因为是排列只会出现一次），则每次询问中要求的区间排名即为 lstlst 上 p[c]p[c] 左侧在 [l,r][l,r] 之间的数的个数，加上 ll 就是答案。使用扫描线——离线树状数组解决即可。（如果你没有学过二位数点，类比树状数组求逆序对即可）。

赛时代码：

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
int n, m;
cin >> n >> m;

vector<int> p(n + 1);
for (int &num : p | views::drop(1)) {
    cin >> num;
}

struct Query {
    int l, r, c, id;
};

vector<vector<Query>> queryByCVal(n + 1);
for (int i = 0; i < m; i++) {
    Query query;
    auto &[l, r, c, id] = query;
    cin >> l >> r >> c;
    id = i;
    queryByCVal[p[c]].push_back(query);
}

vector<int> lst(n + 1);
for (int i = 1; i <= n; i++) {
    lst[p[i]] = i;
}

Fenwick<int> tree(n);
vector<int> ans(m);

for (int val = 1; val <= n; val++) {
    for (auto q : queryByCVal[val]) {
        ans[q.id] = tree.GetSum(q.r) - tree.GetSum(q.l - 1) + q.l;
    }

    tree.Add(lst[val], +1);
}

for (int num : ans) {
    cout << num << '\n';
}

H 小鸡的排列构造

我讨厌构造题…

猜测无论输入如何都存在满足条件的排列（即任意奇数或者偶数长度区间都是全错排），试着构造：

当 r−l+1r - l + 1 为奇数时：n=3n=3 的情况平凡，2 3 1 或者 3 1 2。以前者为例，考虑以此构造 n=4n=4 的情况，设第 4 位为 x，由于后三位 3 1 x 必须满足全错排，因此只能是 2 3 1 1.5 的大小关系，即 3 4 1 2。同理构造 n=5n=5 的情况：3 4 1 2 0.5 即 4 5 2 3 1，以此类推，不难看出规律 n-1,n,n-3,n-2,...。（如果从 3 1 2 出发能得到另一组构造）。

不太清楚“对于一个任意长度为 3 的区间都是全错排的排列，任意长度为 5, 7, 9… 的区间也是全错排”怎么形式化的理解或证明，但是观察我们构造出的序列显然是满足的。

r−l+1r - l + 1 为偶数时同理，可以得到构造 n, n-1, n-2, n-3, ...。

赛时代码：

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
int n, m;
cin >> n >> m;

int parity = 0;
for (int i = 1; i <= m; i++) {
    int l, r, c;
    cin >> l >> r >> c;
    parity = (r - l + 1) & 1;
}

if (parity == 1) {
    for (int i = n - 1; i >= 1; i -= 2) {
        cout << i << ' ' << i + 1 << ' ';
    }
    if (n % 2 == 1) {
        cout << 1;
    }
    cout << '\n';
}
else {
    for (int i = n; i >= 1; i--) {
        cout << i << ' ';
    }
    cout << '\n';
}

D Viva La Vida(Fried-Chicken’s Version)

虽然题目是无向边，但是我们先将其看作有向边。画个简单的图，结论其实就一目了然：

problem D

（剩下的边用更大的数补全即可）

边权就类似势能一样，从高走向低，因此不能成环（重边除外）。由于出度为 1，所以每个联通分量一定有且仅有一个重边，所以数重边个数即可。

由于边权是排列，没有相等的数，也就是说对于一条重边，它的边权就是和这两个点相连的 2n−32n-3 条边里最小的一条，概率 12n−3\cfrac{1}{2n-3}。由期望的线性性，总期望就是每一条边的期望之和， 即 Cn22n−3\cfrac{C_n^2}{2n-3}。

代码略。

E 任造化落骰

参考官方题解的做法，先用单调栈预处理出 nxtMax[i]nxtMax[i]，即 ii 之后下一个改变 max⁡\max 的位置，然后枚举左端点 ll，用双指针处理 max⁡×min⁡\max \times \min 为 valval 的二元对的个数，做个后缀和，每次询问二分找要的值就行。

代码：

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
int n, m, q;
cin >> n >> m >> q;

vector<int> a(n);
for (int &num : a) {
    cin >> num;
}

auto calc = [&](const function<bool(int, int)> &cmp) {
    stack<int> St;
    vector<int> nxt(n);

    for (int i = n - 1; i >= 0; i--) {
        while (St.empty() == false && cmp(a[St.top()], a[i]) == false) {
            St.pop();
        }

        if (St.empty()) {
            nxt[i] = n;
        }
        else {
            nxt[i] = St.top();
        }

        St.push(i);
    }
    return nxt;
};

auto nxtMin = calc(less());
auto nxtMax = calc(greater());

map<ll, ll> bkt;
for (int l = 0; l < n; l++) {
    for (int i = l, j = l; i < n && j < n;) {
        if (nxtMin[i] < nxtMax[j]) {
            bkt[1ll * a[i] * a[j]] += nxtMin[i] - max(i, j);
            i = nxtMin[i];
        }
        else {
            bkt[1ll * a[i] * a[j]] += nxtMax[j] - max(i, j);
            j = nxtMax[j];
        }
    }
}

vector<ll> vals;
vector<ll> sufSum;
for (auto [val, cnt] : bkt) {
    vals.push_back(val);
    sufSum.push_back(cnt);
}

for (int i = sufSum.size() - 2; i >= 0; i--) {
    sufSum[i] += sufSum[i + 1];
}

while (q--) {
    ll k;
    cin >> k;

    int ind = ranges::lower_bound(vals, k) - vals.begin();
    cout << sufSum[ind] << '\n';
}