跳转至

250712 模拟赛

T2 dist

给定长度为 \(n\) 的序列 \(x,y\)，求 \(\sum_{i=1}^n\sum_{j=1}^n{\min(|x_i-x_j|,|y_i-y_j|)}\)。

\(n\le 5\times 10^5\)

注意到

\[ \min(|x_i-x_j|,|y_i-y_j|)=|x_i-x_j|+|y_i-y_j|-\max(|x_i-x_j|,|y_i-y_j|) \]

而前两项（曼哈顿距离）是容易求得的，考虑最后一项，注意到

\[ \max(|x|,|y|)=\left|\frac{x+y}{2}\right|+\left|\frac{x-y}{2}\right| \]

因此最后一项（切比雪夫距离）等于

\[ \left|\frac{x_i+y_i-x_j-y_j}{2}\right|+\left|\frac{x_i-y_i-x_j+y_j}{2}\right|=\left|\frac{(x_i+y_i)-(x_j+y_j)}{2}\right|+\left|\frac{(x_i-y_i)-(x_j-y_j)}{2}\right| \]

正是 \((x_i+y_i,x_i-y_i)\) 曼哈顿距离的一半。由于曼哈顿距离的两个维度是相互独立的，因此是容易的。

最终，问题转化为求 \((x_i,y_i)\) 两两之间曼哈顿距离之和，加上 \(1/2\) 倍的 \((x_i+y_i,x_i-y_i)\) 两两之间曼哈顿距离之和。

由于题目需要我们把一个无序点对 \((i,j)\) 的贡献计算两次，因此给 \((x_i,y_i)\) 的贡献算两遍，\((x_i+y_i,x_i-y_i)\) 的贡献算一次即可。

切比雪夫距离和曼哈顿距离

切比雪夫距离和曼哈顿距离可以互相转化，即两个点 \(A,B\) 的切比雪夫（曼哈顿）距离等于另外两个点 \(A',B'\) 的曼哈顿（切比雪夫）距离，并且这种映射是一一映射，如下：

\[ \begin{align} \max(|x|,|y|)=\left|\frac{x+y}{2}\right|+\left|\frac{x-y}{2}\right|\\ |x|+|y|=\max(|x+y|,|x-y|) \end{align} \]

这都基于

\[ \max(a,b)=\frac{a+b}{2}+\left|\frac{a-b}{2}\right| \]

成立。

代码 
 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
#include<iostream>
#define ll long long
using namespace std;
const int N = 5e5 + 10;
const int V = 1e6;

int n;
int x[N], y[N];
int a[N];

int s[2 * V + 10];
ll calc() {
    ll res = 0;
    for(int i = 0; i < 2 * V; i++) s[i] = 0;
    for(int i = 1; i <= n; i++) s[a[i]]++;
    ll sum = 0;
    int cnt = 0;
    for(int i = 0; i < 2 * V; i++) {
        res += ((ll)cnt * i - sum) * s[i];
        sum += (ll)i * s[i];
        cnt += s[i];
    }
    return res;
}

ll ans;

#define FIO

signed main() {

    #ifdef FIO
    freopen("dist.in", "r", stdin);
    freopen("dist.out", "w", stdout);
    #endif

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

    for(int i = 1; i <= n; i++) a[i] = x[i];
    ans += 2 * calc();
    for(int i = 1; i <= n; i++) a[i] = y[i];
    ans += 2 * calc();
    for(int i = 1; i <= n; i++) a[i] = x[i] + y[i];
    ans -= calc();
    for(int i = 1; i <= n; i++) a[i] = x[i] - y[i] + V;
    ans -= calc();

    cout << ans << '\n';

    return 0;
}

T3 neq

给定一个长度为 \(n\) 的序列 \(a\)（\(1\le a_i\le n\)），有 \(q\) 次询问，每次询问给定区间 \([l,r]\)，表示询问所有 \([1,n]\) 的排列 \(p\) 中有多少个满足 \(\forall i\in [l,r],\ a_i\ne p_i\)。

\(n\le 3000\)

错排考虑容斥，问题转化为求：钦定区间中有 \(k\) 个数字匹配的方案数 \((m-k)!f_k\)。先考虑静态问题，不难注意到区间内 \(a_i\) 的顺序不影响结果，因此容易想到将各个颜色分开处理。具体的，当我们加入一种占领 \(c_i\) 个位置的颜色 \(i\)：

\[ f'_j\gets f_j\\ f'_j\gets f_{j-1}c_i \]

容易做到 \(O(n)\) 转移。

现在考虑动态问题。由于是区间查询，发现不易对两个相邻区间进行合并，因此考虑莫队。发现 \(n^2\sqrt q\) 足以通过本题。这里可以使用回滚莫队，或者普通莫队+背包撤销（显然背包不要求各个物品之间的顺序，并且转移是线性且满秩的，因此可以 \(O(n)\) 实现逆变换）。

代码 
 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N = 3010;
const int MOD = 1e9 + 7;

int blo[N], blen;
struct Qr {
    int l, r, id;
    inline bool operator<(const Qr &b) const {
        if(blo[l] != blo[b.l]) return blo[l] < blo[b.l];
        return (blo[l] & 1) ? (r < b.r) : (r > b.r);
    }
} q[N];

int n, nq;
int a[N], ans[N];

int fact[N];

int cnt[N];
int c_l, c_r, c_ans;

int f[N], m;

inline void add(int c) {
    ++m;
    for(int i = m; i >= 1; i--) f[i] = (f[i] + (ll)f[i - 1] * c % MOD) % MOD;
}

inline void del(int c) {
    for(int i = 1; i <= m; i++) f[i] = (MOD + f[i] - (ll)f[i - 1] * c % MOD) % MOD;
    --m;
}

inline void add_p(int p) {
    del(cnt[a[p]]);
    ++cnt[a[p]];
    add(cnt[a[p]]);
}

inline void del_p(int p) {
    del(cnt[a[p]]);
    --cnt[a[p]];
    add(cnt[a[p]]);
}

inline int query() {
    int res = 0;
    for(int i = 0; i <= m; i += 2) res = (res + (ll)f[i] * fact[n - i] % MOD) % MOD;
    for(int i = 1; i <= m; i += 2) res = (res + MOD - (ll)f[i] * fact[n - i] % MOD) % MOD;
    return res;
}

#define FIO

int main() {

    #ifdef FIO
    freopen("neq.in", "r", stdin);
    freopen("neq.out", "w", stdout);
    #endif

    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = (ll)fact[i - 1] * i % MOD;

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

    blen = max(1, (int)(n / sqrt(nq)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    sort(q + 1, q + 1 + nq);

    f[0] = 1;
    for(int i = 1; i <= n; i++) add(0);
    c_l = 1;

    for(int i = 1; i <= nq; i++) {
        int l = q[i].l, r = q[i].r;
        while(c_l > l) add_p(--c_l);
        while(c_r < r) add_p(++c_r);
        while(c_l < l) del_p(c_l++);
        while(c_r > r) del_p(c_r--);
        ans[q[i].id] = query();
    }

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

    return 0;
}

T4 choose

err-tag