DDOSvoid's Blog

bzoj 3744 Gty的妹子序列

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

题目描述

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次询问，每次询问区间 $[l,r]$ 的逆序对个数

$n,m \le 5\times 10^5$

Solution

我们考虑预处理块 $i$ 到块 $j$ 之间的答案，边角拿主席树暴力处理

时间复杂度 $O(n\sqrt n\log n)$​，可以通过增加码量来优化掉 $\log$​

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 50010
#define maxs 250
#define ll long long 
using namespace std;

int n, m, a[maxn];

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

#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 * 20]; 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 blo, num, l[maxs], r[maxs], bl[maxn], d[maxs][maxs]; 
void init_blo() {
    blo = sqrt(n); num = n / blo; if (n % blo) ++num; 
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n; 
    for (int i = 1; i <= num; ++i) {
        ll s = 0; 
        for (int j = i; j <= num; ++j) {
            for (int k = l[j]; k <= r[j]; ++k) s += query(rt[l[i] - 1], rt[k], 1, cnt, a[k] + 1, cnt);
            d[i][j] = s;
        }
    } 
}

ll query(int L, int R) {
    ll ans = 0; int Bl = bl[L], Br = bl[R]; 
    if (bl[L] == bl[R]) { 
        for (int i = L; i <= R; ++i)
            ans += query(rt[L - 1], rt[i], 1, cnt, a[i] + 1, cnt);
        return ans;
    } ans += d[Bl + 1][Br - 1]; 
    for (int i = L; i <= r[Bl]; ++i)
        ans += query(rt[i - 1], rt[r[Br - 1]], 1, cnt, 1, a[i] - 1);
    for (int i = l[Br]; i <= R; ++i)
        ans += query(rt[l[Bl + 1] - 1], rt[i], 1, cnt, a[i] + 1, cnt);
    for (int i = L; i <= r[Bl]; ++i)
        ans += query(rt[l[Br] - 1], rt[R], 1, cnt, 1, a[i] - 1); 
    return ans;
} 

ll lans; 
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init_hash();
    for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, cnt, a[i], 1);
    init_blo(); cin >> m; 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        x ^= lans; y ^= lans;
        printf("%lld\n", lans = query(x, y)); 
    }
    return 0;
}