跳转至

区间逆序对

例题

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II - 洛谷

根据区间逆序对的性质, 将莫队再次离线即二次离线莫队.

代码
C++
  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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[100005];
int tr[100005];
i64 pre[100005], suf[100005];
int lowbit(int x) {
    return x & -x;
}
int len;
void add(int x) {
    while (x <= len) {
        tr[x]++;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int belong[100005], st[100005], ed[100005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        return x.R < y.R;
    }
};
int B;
i64 cnt[100005], info[320];
void addL(int k) {
    int x = belong[k];
    for (int i = st[x] ; i < k ; i++) {
        cnt[i]++;
    }
    for (int i = 1 ; i <= x - 1 ; i++) {
        info[i]++;
    }
}
void addR(int k) {
    int x = belong[k];
    for (int i = k + 1 ; i <= ed[x] ; i++) {
        cnt[i]++;
    }
    for (int i = x + 1 ; i <= B ; i++) {
        info[i]++;
    }
}
vector<array<int, 4>> quL[100005], quR[100005];
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> idx(1, -1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    len = idx.size() - 1;
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    for (int i = 1 ; i <= n ; i++) {
        pre[i] = pre[i - 1] + query(len) - query(a[i]);
        add(a[i]);
    }
    fill(tr, tr + len + 1, 0);
    for (int i = n ; i >= 1 ; i--) {
        suf[i] = suf[i + 1] + query(a[i] - 1);
        add(a[i]);
    }
    {
        B = sqrt(len);
        int cnt = len / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = len;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    vector<MO> mo;
    for (int i = 1 ; i <= m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<i64> ans(m + 1);
    int L = 1, R = 0;
    for (auto &[QL, QR, idx] : mo) {
        if (L > QL) {
            quR[QR + 1].push_back({QL, L - 1, idx, -1});
            ans[idx] += suf[QL] - suf[L];
        }
        if (R < QR) {
            quL[L - 1].push_back({R + 1, QR, idx, -1});
            ans[idx] += pre[QR] - pre[R];
        }
        if (L < QL) {
            quR[QR + 1].push_back({L, QL - 1, idx, 1});
            ans[idx] -= suf[L] - suf[QL];
        }
        if (R > QR) {
            quL[L - 1].push_back({QR + 1, R, idx, 1});
            ans[idx] -= pre[R] - pre[QR];
        }
        L = QL;
        R = QR;
    }
    for (int i = 1 ; i <= n ; i++) {
        addL(a[i]);
        for (auto &[L, R, idx, r] : quL[i]) {
            i64 res = 0;
            for (int j = L ; j <= R ; j++) {
                res += cnt[a[j]] + info[belong[a[j]]];
            }
            ans[idx] += r * res;
        }
    }
    fill(cnt, cnt + len + 1, 0);
    fill(info, info + B + 1, 0);
    for (int i = n ; i >= 1 ; i--) {
        addR(a[i]);
        for (auto &[L, R, idx, r] : quR[i]) {
            i64 res = 0;
            for (int j = L ; j <= R ; j++) {
                res += cnt[a[j]] + info[belong[a[j]]];
            }
            ans[idx] += r * res;
        }
    }
    for (int i = 1 ; i < m ; i++) {
        ans[mo[i].idx] += ans[mo[i - 1].idx];
    }
    for (int i = 1 ; i <= m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I - 洛谷

分块

如果 \(L\) 和 \(R\) 在同一个块内, 可以对每一块单独排序, 按值从大到小遍历, 将下标在区间 \(L,R\) 和 \(<L\) 拿出来分别讨论即可计算出区间 \([L,R]\) 的逆序对数量.

如果 \(L\) 和 \(R\) 不在同一个块内, 那么我们可以拆成整块与整块之间的逆序对, 左散块与整块之间的逆序对, 右散块与整块之间的逆序对, 左散块与右散块之间的逆序对.

对于整块与整块之间的逆序对, 我们可以先预处理出第 \(1\) 块到第 \(i\) 块 \(<j\) 的数的数量, 即 \(f_{i,j}\).

令 \(s_{i,j}\) 为第 \(i\) 块到第 \(j\) 块之间的逆序对数量, 则 \(s_{i,j}=s_{i,j-1}+\sum_{k=st_j}^{ed_j}((f_{j-1,n}-f_{i-1,n})-(f_{j-1,a_k}-f_{i-1,a_k}))\)

对于 \(f_{i,j}\), 我们刚开始先枚举 \(a_k\), 使 \(f_{belong_k,a_k}\) 自增 \(1\).

然后我们前缀 \(i\), 即对任意的 \(j\) 都 \(f_{i,j}+=f_{i-1,j}\)

然后我们再前缀 \(j\), 即对任意的 \(i\) 都 \(f_{i,j}+=f_{i,j-1}\)

对于左散块与右散块之间的逆序对, 我们可以把左侧和右侧的数分别升序存入两个队列, 然后使用归并的思想线性求逆序对.

对于左散块与整块之间的逆序对, 我们可以枚举左散块的 \(a_k\), 通过 \(\sum(f_{belong_k,a_k-1}-f_{i,a_k-1})\) 求出.

对于右散块与整块之间的逆序对, 我们可以枚举右散块的 \(a_k\), 通过 \(\sum((f_{belong_k,n}-f_{i,n})-(f_{belong_k,a_k}-f_{i,a_k}))\) 求出.

代码
C++
  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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[100005], st[320], ed[320];
int B, len;
int a[100005];
array<int, 2> b[100005];
int tr[100005];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    while (x <= len) {
        tr[x] += k;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int pre[100005], suf[100005];
int f[320][100005]; // f[i][j] 表示第 i 块中小于 j 的数量
i64 s[320][320]; // s[i][j] 表示第 i 块到第 j 块的逆序对
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> idx(1, -1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    len = idx.size();
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
        b[i] = {a[i], i};
    }
    {
        B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            sort(b + st[i], b + ed[i] + 1);
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
            int x = 0;
            for (int j = st[i] ; j <= ed[i] ; j++) {
                x += query(len) - query(a[j]);
                pre[j] = x;
                add(a[j], 1);
            }
            for (int j = st[i] ; j <= ed[i] ; j++) {
                suf[j] = x;
                add(a[j], -1);
                x -= query(a[j] - 1);

            }
            for (int j = st[i] ; j <= ed[i] ; j++) {
                f[i][a[j]]++;
            }
        }
        for (int i = 1 ; i <= B ; i++) {
            for (int j = 1 ; j <= len ; j++) {
                f[i][j] += f[i - 1][j];
            }
        }
        for (int i = 1 ; i <= B ; i++) {
            for (int j = 1 ; j <= len ; j++) {
                f[i][j] += f[i][j - 1];
            }
        }
        for (int i = 1 ; i <= B ; i++) {
            s[i][i] = pre[ed[i]];
            for (int j = i + 1 ; j <= B ; j++) {
                i64 res = s[i][j - 1] + pre[ed[j]];
                for (int k = st[j] ; k <= ed[j] ; k++) {
                    res += (f[j - 1][len] - f[i - 1][len]) - (f[j - 1][a[k]] - f[i - 1][a[k]]);
                }
                s[i][j] = res;
            }
        }
    }
    i64 ans = 0;
    for (int i = 1 ; i <= m ; i++) {
        i64 tL, tR;
        cin >> tL >> tR;
        tL ^= ans;
        tR ^= ans;
        int L = tL, R = tR;
        int x = belong[L], y = belong[R];
        if (x == y) {
            ans = pre[R] - (L == st[x] ? 0 : pre[L - 1]);
            int c = 0;
            for (int i = ed[x] ; i >= st[x] ; i--) {
                auto [v, idx] = b[i];
                if (L <= idx && idx <= R) {
                    ans -= c;
                } else if (idx < L) {
                    c++;
                }
            }
        } else {
            ans = s[x + 1][y - 1] + suf[L] + pre[R];
            for (int i = L ; i <= ed[x] ; i++) { // 左散块对中间整块的逆序对
                ans += f[y - 1][a[i] - 1] - f[x][a[i] - 1];
            }
            for (int i = st[y] ; i <= R ; i++) { // 右散块对中间整块的逆序对
                ans += (f[y - 1][len] - f[y - 1][a[i]]) - (f[x][len] - f[x][a[i]]);
            }
            queue<int> ax, ay;
            for (int i = st[x] ; i <= ed[x] ; i++) {
                auto [v, idx] = b[i];
                if (idx >= L) {
                    ax.push(v);
                }
            }
            for (int i = st[y] ; i <= ed[y] ; i++) {
                auto [v, idx] = b[i];
                if (idx <= R) {
                    ay.push(v);
                }
            }
            while (!ax.empty() && !ay.empty()) {
                if (ax.front() <= ay.front()) {
                    ax.pop();
                } else {
                    ans += ax.size();
                    ay.pop();
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}