例题：洛谷 P5047
题面图上的妹子好可爱啊(ˉ﹃ˉ)
多组询问，求一个区间内的逆序对数，离线，
n
≤
1
0
5
n \leq 10^5
n≤105，时限0.3s，空间限制32MB （好，不愧是lxl）
二次离线莫队
如果直接用莫队做这道题的话，每次移动都要来一遍树状数组，复杂度就是
O
(
n
n
log
n
)
O(n \sqrt{n} \log n)
O(nn
logn)的了。
记
(
[
l
1
,
r
1
]
,
[
l
2
,
r
2
]
)
([l_1,r_1],[l_2,r_2])
([l1,r1],[l2,r2])表示这两个区间之间的逆序对数。
现在考虑做莫队的过程中，假如我要将区间
[
l
,
r
]
[l,r]
[l,r]，通过右端点右移，变成区间
[
l
,
r
′
]
[l,r']
[l,r′]。那么一次从
[
l
,
r
+
i
]
[l,r+i]
[l,r+i]变到
[
l
,
r
+
i
+
1
]
[l,r+i+1]
[l,r+i+1]的移动，当前答案就要加上
(
[
l
,
r
+
i
]
,
[
r
+
i
+
1
,
r
+
i
+
1
]
)
([l,r+i],[r+i+1,r+i+1])
([l,r+i],[r+i+1,r+i+1])。差分一下，得到：
(
[
1
,
r
+
i
]
,
[
r
+
i
+
1
,
r
+
i
+
1
]
)
−
(
[
1
,
l
−
1
]
,
[
r
+
i
+
1
,
r
+
i
+
1
]
)
([1,r+i],[r+i+1,r+i+1])-([1,l-1],[r+i+1,r+i+1])
([1,r+i],[r+i+1,r+i+1])−([1,l−1],[r+i+1,r+i+1])。
因此这一次移动，当前答案应该加上：
(
∑
i
=
r
+
1
r
′
(
[
1
,
i
−
1
]
,
[
i
,
i
]
)
)
−
(
[
1
,
l
−
1
]
,
[
r
+
1
,
r
′
]
)
(\sum_{i=r+1}^{r'} ([1,i-1],[i,i]))-([1,l-1],[r+1,r'])
(i=r+1∑r′([1,i−1],[i,i]))−([1,l−1],[r+1,r′])
前者只有
n
n
n种情况，用树状数组
O
(
n
log
n
)
O(n \log n)
O(nlogn)预处理，然后利用前缀和计算。
后者是一个前缀和一个区间的逆序对数的形式，将其离线存在每个前缀处。所有
[
r
+
1
,
r
′
]
[r+1,r']
[r+1,r′]的总长，由于莫队的性质，是
O
(
n
n
)
O(n \sqrt{n})
O(nn
)级别的。那么可以从左到右处理每一个前缀以及挂在这个前缀上的
[
r
+
1
,
r
′
]
[r+1,r']
[r+1,r′]，利用分块，每次前缀加入一个新数，修改每个元素的值和前缀的逆序对数是
O
(
n
n
)
O(n \sqrt{n})
O(nn
)的，查询一个位置的元素与前缀的逆序对数是
O
(
1
)
O(1)
O(1)的。
总复杂度是
O
(
n
log
n
+
n
n
)
O(n \log n+n \sqrt{n})
O(nlogn+nn
)的。
其他的左端点左移，左端点右移，右端点左移也类似，左端点移动就用后缀即可。
注意一点，莫队在处理完右端点的移动后，当前区间的右端点就变成了当前处理的询问的右端点，而不是上一个询问的右端点。
代码
#include<bits/stdc++.h>
using namespace std
;
#define RI register int
int read() {
int q
=0;char ch
=' ';
while(ch
<'0'||ch
>'9') ch
=getchar();
while(ch
>='0'&&ch
<='9') q
=q
*10+ch
-'0',ch
=getchar();
return q
;
}
typedef long long LL
;
const int N
=100005,sqn
=320;
int n
,m
,js
;
int a
[N
],b
[N
],tr
[N
],pos
[N
],lz
[sqn
+5];
LL suml
[N
],sumr
[N
],ans
[N
],kansl
[N
],kansr
[N
];
struct node
{int l
,r
,id
;}q
[N
];
bool cmp(node A
,node B
) {return pos
[A
.l
]==pos
[B
.l
]?A
.r
<B
.r
:pos
[A
.l
]<pos
[B
.l
];}
int lowbit(int x
) {return x
&(-x
);}
void add(int x
) {while(x
<=js
) ++tr
[x
],x
+=lowbit(x
);}
int query(int x
) {int re
=0;while(x
) re
+=tr
[x
],x
-=lowbit(x
); return re
;}
void prework() {
for(RI i
=1;i
<=n
;++i
)
suml
[i
]=suml
[i
-1]+query(js
-a
[i
]),add(js
-a
[i
]+1);
for(RI i
=1;i
<=js
;++i
) tr
[i
]=0;
for(RI i
=n
;i
>=1;--i
)
sumr
[i
]=sumr
[i
+1]+query(a
[i
]-1),add(a
[i
]);
}
vector
<node
> lmove
[N
],rmove
[N
];
void work1() {
sort(q
+1,q
+1+m
,cmp
);
q
[0].l
=1,q
[0].r
=0;
for(RI i
=1;i
<=m
;++i
) {
if(q
[i
].r
>q
[i
-1].r
)
lmove
[q
[i
-1].l
-1].push_back((node
){q
[i
-1].r
+1,q
[i
].r
,i
});
if(q
[i
].r
<q
[i
-1].r
)
lmove
[q
[i
-1].l
-1].push_back((node
){q
[i
].r
+1,q
[i
-1].r
,i
});
if(q
[i
].l
>q
[i
-1].l
)
rmove
[q
[i
].r
+1].push_back((node
){q
[i
-1].l
,q
[i
].l
-1,i
});
if(q
[i
].l
<q
[i
-1].l
)
rmove
[q
[i
].r
+1].push_back((node
){q
[i
].l
,q
[i
-1].l
-1,i
});
}
}
void work2() {
for(RI i
=1;i
<=js
;++i
) tr
[i
]=0;
for(RI i
=1;i
<=pos
[js
];++i
) lz
[i
]=0;
for(RI i
=0;i
<n
;++i
) {
int sz
=lmove
[i
].size();
for(RI j
=0;j
<sz
;++j
)
for(RI k
=lmove
[i
][j
].l
;k
<=lmove
[i
][j
].r
;++k
)
kansl
[lmove
[i
][j
].id
]+=tr
[a
[k
]]+lz
[pos
[a
[k
]]];
for(RI j
=a
[i
+1]-1;j
>=sqn
*(pos
[a
[i
+1]]-1)+1;--j
) ++tr
[j
];
for(RI j
=pos
[a
[i
+1]]-1;j
>=1;--j
) ++lz
[j
];
}
for(RI i
=1;i
<=js
;++i
) tr
[i
]=0;
for(RI i
=1;i
<=pos
[js
];++i
) lz
[i
]=0;
for(RI i
=n
+1;i
>=2;--i
) {
int sz
=rmove
[i
].size();
for(RI j
=0;j
<sz
;++j
)
for(RI k
=rmove
[i
][j
].l
;k
<=rmove
[i
][j
].r
;++k
)
kansr
[rmove
[i
][j
].id
]+=tr
[a
[k
]]+lz
[pos
[a
[k
]]];
for(RI j
=a
[i
-1]+1;j
<=sqn
*pos
[a
[i
-1]];++j
) ++tr
[j
];
for(RI j
=pos
[a
[i
-1]]+1;j
<=pos
[js
];++j
) ++lz
[j
];
}
}
void work3() {
LL nowans
=0;
for(RI i
=1;i
<=m
;++i
) {
if(q
[i
].r
>q
[i
-1].r
)
nowans
+=suml
[q
[i
].r
]-suml
[q
[i
-1].r
]-kansl
[i
];
if(q
[i
].r
<q
[i
-1].r
)
nowans
-=suml
[q
[i
-1].r
]-suml
[q
[i
].r
]-kansl
[i
];
if(q
[i
].l
>q
[i
-1].l
)
nowans
-=sumr
[q
[i
-1].l
]-sumr
[q
[i
].l
]-kansr
[i
];
if(q
[i
].l
<q
[i
-1].l
)
nowans
+=sumr
[q
[i
].l
]-sumr
[q
[i
-1].l
]-kansr
[i
];
ans
[q
[i
].id
]=nowans
;
}
}
int main()
{
n
=read(),m
=read();
for(RI i
=1;i
<=n
;++i
) a
[i
]=b
[i
]=read();
sort(b
+1,b
+1+n
);
js
=1;for(RI i
=2;i
<=n
;++i
) if(b
[i
]!=b
[js
]) b
[++js
]=b
[i
];
for(RI i
=1;i
<=n
;++i
) a
[i
]=lower_bound(b
+1,b
+1+js
,a
[i
])-b
;
for(RI i
=1;i
<=m
;++i
) q
[i
].l
=read(),q
[i
].r
=read(),q
[i
].id
=i
;
for(RI i
=1;i
<=n
;++i
) pos
[i
]=(i
-1)/sqn
+1;
prework(),work1(),work2(),work3();
for(RI i
=1;i
<=m
;++i
) printf("%lld\n",ans
[i
]);
return 0;
}
