DDOSvoid's Blog

第十八届浙大城市学院程序设计竞赛（同步赛）H Infinite Array

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/12986/H

Solution

我们考虑对于 $a_i$，它所能对应的 $b$ 为 $b_i,b_{i+n},b_{i+2n},\cdots$

注意到因为 $(n,m)=1$，所以 $\lbrace kn\rbrace,k\in[0,m)$ 为模 $m$ 的完全剩余系

那么我们注意到 $a_i$ 对应的 $b$ 为 $\lbrace kn\rbrace,k\in[0,m)$ 的一段连续区间，下标加 $i$ 只是相当于右移，并不影响相对顺序

所以相当于查询区间内比 $a_i$ 小的数的个数，显然可以用主席树实现

时间复杂度 $O(n\log 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
#include <iostream>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n, m, a[maxn], b[maxn];
ll k;

int c[maxn * 2], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) c[i] = a[i];
    for (int i = 1; i <= m; ++i) c[i + n] = b[i];
    sort(c + 1, c + n + m + 1); cnt = unique(c + 1, c + n + m + 1) - c - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(c + 1, c + cnt + 1, a[i]) - c;
    for (int i = 1; i <= m; ++i) b[i] = lower_bound(c + 1, c + cnt + 1, b[i]) - c;
} 

int d[maxn], rd[maxn];
ll w[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
    int v, ch[2];
} T[maxn * 40]; int rt[maxn], top;
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v += v; 
    if (l == r) return ; int m = l + r >> 1;
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v);
}

int query(int i, int j, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[j].v - T[i].v;
    int m = l + r >> 1;
    return query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];
    init_hash();
    for (int i = 1; i <= n; ++i) w[i] = k / n + (k % n >= i);  
    for (int i = 1; i <= m; ++i) {
        d[i] = 1ll * (i - 1) * n % m + 1;
        rd[d[i]] = i; 
    }
    for (int i = 1; i <= m; ++i)
        update(rt[i], rt[i - 1], 1, cnt, b[d[i]], 1);
    ll ans = 0; 
    for (int i = 1; i <= n; ++i) {
        ans += w[i] / m * query(rt[0], rt[m], 1, cnt, 1, a[i] - 1);
        int res = w[i] % m;
        if (!res) continue;
        int l = rd[(i - 1) % m + 1], r = (l + res - 1 - 1) % m + 1;
        if (l <= r) ans += query(rt[l - 1], rt[r], 1, cnt, 1, a[i] - 1);
        else ans += query(rt[0], rt[r], 1, cnt, 1, a[i] - 1) + query(rt[l - 1], rt[m], 1, cnt, 1, a[i] - 1); 
    } cout << ans << "\n"; 
    return 0;
}