Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

Posted on In
Symbols count in article: 5.3k Reading time ≈ 5 mins.

比较板子，值域分块有点难想

Yuno loves sqrt technology II

思路

虽然有重复元素了，但没强制在线，考虑莫队，发现每次移动指针时改变的是点对区间的贡献，不好 $O(1)$ 移动指针，考虑二次离线，记 $f(i, [l, r])$ 表示“点 $i$ 对 $[l, r]$ 的贡献”，分类讨论：

  1. 指针从 $[il, ir]$ 变为 $[il, r](r > ir)$ ，则 $\Delta ans = \sum_{i = ir + 1}^r f(i, [il, i - 1])$
  2. 指针从 $[il, ir]$ 变为 $[il, r](r < ir)$ ，则 $\Delta ans = -\sum_{i = r + 1}^{ir} f(i, [il, i - 1])$
  3. 指针从 $[il, ir]$ 变为 $[l, ir](l < il)$ ，则 $\Delta ans = \sum_{i = l}^{il - 1} f(i, [i + 1, ir])$
  4. 指针从 $[il, ir]$ 变为 $[l, ir](l > il)$ ，则 $\Delta ans = -\sum_{i = il}^{l - 1} f(i, [i + 1, ir])$

然后很套路的拆成前/后缀和，记 $f(i, j) = f(i, [1, j]), g(i, j) = f(i, [j, n])$ （前/后缀分开是因为逆序对点在前时贡献是“区间小于点的数”，在后是“区间大于点的数”，要分开），如第一类，就是 $\Delta ans = \sum_{i = ir + 1}^r f(i, [il, i - 1]) = \sum_{i = ir + 1}^r f(i, i - 1) - f(i, il)$ ，而第三类就是 $\Delta ans = \sum_{i = l}^{il - 1} f(i, [i + 1, ir]) = \sum_{i = l}^{il - 1} g(i, i + 1) - g(i, ir)$

对于 $f(i, i - 1)$ 和 $g(i, i + 1)$ ，直接暴力求，用 BIT 就是 $O(n \log n)$ ，记得把它们前缀和了卡常；而 $f(i, il)$ 和 $g(i, ir)$ 根据套路直接打标记，然后……这里用 BIT 求就是 $O(n \sqrt{n} \log n)$ （ wfy 大佬说好像可以用条块分摊 $\log n$ 的方法卡，但在下是大常数选手），爆炸，仔细分析，对于 $f(i, il)$ 和 $g(i, ir)$ ，有 $O(n)$ 次修改和 $O(n \sqrt{n})$ 次查询，但 BIT 修改和查询都是 $O(\log n)$ 这显然不平均，为了平衡复杂度，考虑值域分块

我们用 BIT 想要维护的信息是“当前区间小于等于 $x$ 的数有多少个”，直接值域分块，记 $as[i]$ 表示“值小于第 $i$ 块最小值的数的个数”，再记 $ct[i]$ 表示“数 $i$ 所在块中值小于等于 $i$ 的数的个数”，这样，修改是 $O(\sqrt{n})$ 的，但询问变成了 $O(1)$ ；另外 BIT 也就不需要了， $f(i, i - 1)$ 和 $g(i, i + 1)$ 也用这个分块求

时间 $O(n \sqrt{n})$ ，注意常数

代码

代码中的 $f[0/1]$ 代表 $f(i, i - 1)$ 和 $g(i, i + 1)$ 

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
#include <bits/stdc++.h>
#define STC static
#define IL inline
namespace FIO
{
    const int L = (1 << 20) + 5;
    int l = 0;
    char *S, *E, buf[L], out[L];
    #define gh() (S == E ? E = (S = buf) + fread(buf, 1, L, stdin), (S == E ? EOF : *S++) : *S++)
    IL void flus(){ fwrite(out, 1, l, stdout), l = 0; }
    IL void chk(){ if (l >= L - 5) flus(); }
    template<class T>
    IL void read(T &x)
    {
        char ch = gh(), t = 0;
        for (; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
        for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
        if (t) x = -x;
    }
    IL void putc(char x){ out[l++] = x, chk(); }
    template<class T>
    IL void write(T x)
    {
        if (x < 0) putc('-'), x = -x;
        if (x > 9) write(x / 10);
        out[l++] = x % 10 + 48, chk();
    }
}
using FIO::flus;
using FIO::read;
using FIO::putc;
using FIO::write;
using LL = long long;
const int N = 1e5 + 100;
int n, m, a[N], nn;
LL ans[N];
struct Q{ int l, r, id; LL ans; } q[N];
std::vector<int> xx;
namespace VBlock  //值域分块
{
    const int V = 320, NV = 320;
    struct Node{ int l, r, as; } b[NV];
    int bid[N], num, ct[N];
    IL void prev()
    {
        for (int i = 1; i <= nn; i += V) b[++num].l = i, b[num].r = i + V - 1;
        b[num].r = nn;
        for (int i = 1; i <= num; ++i)
            for (int j = b[i].l; j <= b[i].r; ++j) bid[j] = i;
    }
    IL void ins(int x, int d)
    {
        Node *t = &b[bid[x]];
        for (int i = x; i <= t->r; ++i) ct[i] += d;
        for (int i = bid[x] + 1; i <= num; ++i) b[i].as += d;
    }
    IL int ask(int x){ return b[bid[x]].as + ct[x]; }
}
namespace TOF //Twice Offline
{
    const int B = 320;
    struct Tag{ int l, r, id, pos; } tg1[N], tg2[N];
    int tp1 = 0, tp2 = 0;
    LL f[2][N];
    IL void prev()
    {
        STC int bid[N];
        for (int i = 1; i <= n; ++i) bid[i] = (i - 1) / B + 1;
        std::sort(q + 1, q + m + 1, [&](Q x, Q y){ return bid[x.l] == bid[y.l] ? x.r < y.r : x.l < y.l; });
    }
    IL void add_tag()
    {
        for (int i = 1, il = q[1].r + 1, ir = q[1].r; i <= m; ++i)
        {
            if (il > q[i].l) tg1[++tp1] = {q[i].l, il - 1, -i, ir};
            else  if (il < q[i].l) tg1[++tp1] = {il, q[i].l - 1, i, ir}; 
            il = q[i].l;
            if (ir < q[i].r) tg2[++tp2] = {ir + 1, q[i].r, -i, il - 1};
            else if (ir > q[i].r) tg2[++tp2] = {q[i].r + 1, ir, i, il - 1};
            ir = q[i].r;
        }
        std::sort(tg1 + 1, tg1 + tp1 + 1, [&](Tag x, Tag y){ return x.pos < y.pos; });
        std::sort(tg2 + 1, tg2 + tp2 + 1, [&](Tag x, Tag y){ return x.pos < y.pos; });
    }
    IL void offline()
    {
        int p = 0;
        for (int i = 1; i <= tp2; ++i)
        {
            while (p < tg2[i].pos && ++p)
            {
                f[0][p] = f[0][p - 1] + p - VBlock::ask(a[p]) - 1;
                VBlock::ins(a[p], 1);
            }
            for (int l = tg2[i].l, r = tg2[i].r, k = (tg2[i].id < 0 ? -1 : 1), id = tg2[i].id * k; l <= r; ++l) q[id].ans += LL(p - VBlock::ask(a[l])) * k;
        }
        while (p < n && ++p)
        {
            f[0][p] = f[0][p - 1] + p - VBlock::ask(a[p]) - 1;
            VBlock::ins(a[p], 1);
        }
        p = 0;
        for (int i = 1; i <= tp1; ++i)
        {
            while (p < tg1[i].pos && ++p)
            {
                VBlock::ins(a[p], -1);
                f[1][p] = f[1][p - 1] + VBlock::ask(a[p] - 1);
            }
            for (int l = tg1[i].l, r = tg1[i].r, k = (tg1[i].id < 0 ? -1 : 1), id = tg1[i].id * k; l <= r; ++l) q[id].ans += LL(VBlock::ask(a[l] - 1)) * k;
        }
        while (p < n && ++p)
        {
            VBlock::ins(a[p], -1);
            f[1][p] = f[1][p - 1] + VBlock::ask(a[p] - 1);
        }
    }
    IL void modui()
    {
        for (int i = 1, il = q[1].r + 1, ir = q[1].r; i <= m; ++i)
        {
            if (il != q[i].l) q[i].ans += f[1][il - 1] - f[1][q[i].l - 1];
            il = q[i].l;
            if (ir != q[i].r) q[i].ans += f[0][q[i].r] - f[0][ir];
            ir = q[i].r;
        }
        for (int i = 2; i <= n; ++i) q[i].ans += q[i - 1].ans;
        for (int i = 1; i <= m; ++i) ans[q[i].id] = q[i].ans;
    }
    IL void work(){ prev(), add_tag(), offline(), modui(); }
}
IL void lsh()
{
    xx.push_back(-1);
    for (int i = 1; i <= n; ++i) xx.push_back(a[i]);
    std::sort(xx.begin(), xx.end());
    xx.erase(std::unique(xx.begin(), xx.end()), xx.end());
    for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(xx.begin(), xx.end(), a[i]) - xx.begin();
    nn = xx.size() - 1;
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= m; ++i) read(q[i].l), read(q[i].r), q[i].id = i;
    lsh(), VBlock::prev(), TOF::work();
    for (int i = 1; i <= m; ++i) write(ans[i]), putc('\n');
    return flus(), 0;
}