发现忘了写题解……
来补一份。
二次离线莫队就不讲了。
应用二次离线莫队的时候，会发现我们需要寻找一种数据结构能承受 \(O(n)\) 次修改，\(O(n \sqrt n)\) 次询问。
显然地值域分块，这玩意也可以把修改和询问的复杂度交换，达到一种根号平衡。
就是有点复杂（
听说还有 \(n^{1.41}\) 的做法，瑟瑟发抖。
代码： 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
using namespace std;
const int N = 1e5;
const int BLK = 320;
const int CNT = 320;
int n,m,block,a[N + 5],pos[N + 5];
int ind[N + 5],len;
struct s_query
{
int l,r,id;
long long ans;
inline bool operator<(const s_query &o) const
{
return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
}
} qry[N + 5];
struct s_contrib
{
int l,r,id,w;
};
int c[N + 5];
inline void update(int x,int k)
{
for(;x <= len;x += lowbit(x))
c[x] += k;
}
inline int query(int x)
{
int ret = 0;
for(;x;x -= lowbit(x))
ret += c[x];
return ret;
}
int cnt[CNT + 5],pre[N + 5];
inline void add(int x,int k)
{
for(register int i = pos[x] + 1;i <= pos[n];++i)
cnt[i] += k;
for(register int i = x;i <= min(pos[x] * block,n);++i)
pre[i] += k;
}
inline int ask(int x)
{
return cnt[pos[x]] + pre[x];
}
vector<s_contrib> vec[2][N + 5];
long long sum[2][N + 5],ans[N + 5];
int main()
{
scanf("%d%d",&n,&m),block = sqrt(n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),ind[i] = a[i],pos[i] = (i - 1) / block + 1;
sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
for(register int i = 1;i <= n;++i)
sum[0][i] = i - query(a[i]) - 1,update(a[i],1);
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
sum[1][i] = query(a[i] - 1),update(a[i],1);
for(register int i = 1;i <= m;++i)
scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
l < qry[i].l && (vec[1][r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
for(;l < qry[i].l;qry[i].ans += sum[1][l++]);
l > qry[i].l && (vec[1][r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
for(;l > qry[i].l;qry[i].ans -= sum[1][--l]);
r < qry[i].r && (vec[0][l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
for(;r < qry[i].r;qry[i].ans += sum[0][++r]);
r > qry[i].r && (vec[0][l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
for(;r > qry[i].r;qry[i].ans -= sum[0][r--]);
}
for(register int i = 1;i <= n;++i)
{
add(a[i],1);
for(register vector<s_contrib>::iterator it = vec[0][i].begin();it != vec[0][i].end();++it)
for(register int j = it->l;j <= it->r;++j)
qry[it->id].ans += it->w * (i - ask(a[j]));
}
memset(cnt,0,sizeof cnt),memset(pre,0,sizeof pre);
for(register int i = 1;i <= n;++i)
{
add(a[i],1);
for(register vector<s_contrib>::iterator it = vec[1][i].begin();it != vec[1][i].end();++it)
for(register int j = it->l;j <= it->r;++j)
qry[it->id].ans += it->w * ask(a[j] - 1);
}
for(register int i = 1;i <= m;++i)
ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans);
for(register int i = 1;i <= m;++i)
printf("%lld\n",ans[i]);
}