题解 P5047 【[Ynoi2019模拟赛]Yuno loves sqrt technology II】
皎月半洒花
2020-04-12 22:13:27
### 正文
还是考虑二次离线，那么需要预处理
$$\sum_{i=1}^k (i,i)(1,i-1)\quad | \quad \sum_{i=1}^k (i,i)(1,i)$$
和
$$\sum_{i=k+1}^n (i,i)(i+1,n)\quad | \quad \sum_{i=k+1}^n (i,i)(i,n)$$
这 $4$ 个信息，因为在计算逆序对的时候是有方向性的，$l$ 向左扩展/向右收缩对应的是 $(l+1,n)$ 之间的信息，$r$ 向右扩展/左收缩对应的是 $(1,r-1)$ 之间的信息。同时注意到由于 $(i,i)(1,i)=(i,i)(1,i-1)$ ，所以本质上是两个信息。这个可以 $O(n\log n)$ 预处理。
同理，对于不能预处理的区间，也是要分左边的贡献和右边的贡献来做。根据方向，可以方便地判断每种情况贡献应该怎么加，拿两种值域分块，分别维护前缀和&后缀和就好了。
实现细节方面需要注意：
1、本题数据中存在 $a_i$ 相同的情况，这个地方会卡求逆序对时的边界，注意判一下即可。
2、值域分块需要注意，只需要修改整块的 `sum`，零散的点单独算贡献。
____
### 补充知识
#### 1、二次离线在莫队上的应用
大概是一种需要维护信息具有可减性的莫队。只要具可减性，就可以容斥，就可以二次离线。所谓『二次离线』，大概是指由于普通莫队无法快速计算贡献，所以第一次离线把询问离线下来，第二次离线把莫队的转移过程离线下来。然后由于信息具有可减性(比如常见的「点对数」)，那么可以：
记 $(a,b)(c,d)$ 表示区间 $[a,b]$ 内的点和区间 $[c,d]$ 内的点对彼此产生的贡献(区间内部不算)。
（1）如果 $[l,r]\to [l+t,r]$ ，那么可知
$$\Delta ans=\sum_{i=l}^{l+t-1} (i,i)(i+1,r)=\sum_{i=l}^{l+t-1} \left((i,i)(1,r)-(i,i)(1,i)\right)=(l,l+t-1)(1,r)-\sum_{i=l}^{l+t-1}(i,i)(1,i)$$
（2）如果 $[l,r]\to [l-t,r]$ ，那么可知
$$\Delta ans=\sum_{i=l-t}^{l-1} (i,i)(i+1,r)=\sum_{i=l-t}^{l-1} \left((i,i)(1,r)-(i,i)(1,i)\right)=(l-t,l-1)(1,r)-\sum_{i=l-t}^{l-1}(i,i)(1,i)$$
（3）如果 $[l,r]\to [l,r+t]$ ，那么可知
$$\Delta ans=\sum_{i=r+1}^{r+t}(i,i)(l,i-1)=\sum_{i=r+1}^{r+t}((1,i-1)(i,i)-(1,l-1)(i,i))=-(1,l-1)(r+1,r+t)+\sum_{i=r+1}^{r+t}(i,i)(1,i-1)$$
（4）如果 $[l,r]\to [l,r-t]$ ，那么可知
$$\Delta ans=\sum_{i=r-t+1}^{r}(i,i)(l,i-1)=\sum_{i=r-t+1}^{r}((1,i-1)(i,i)-(1,l-1)(i,i))=-(1,l-1)(r-t+1,r)+\sum_{i=r-t+1}^{r}(i,i)(1,i-1)$$
其中 $\sum$ 并不是真正的 $\sum$ ，不同情况下需要按顺序(即不再有交换律)，比如 $[l,r]\to [l,r-t]$ 时就需要从 $r-1$ 算到 $r-t$ 。
然后这样容斥之后，后面的 $\sum$ 就可以预处理了，前面的 $()()$ ，由于莫队的复杂度，可以知道至多有 $n\sqrt m$ 个不同的询问，这样就可以把每一组询问打标记，打到左端点是 $1$ 的那个询问上 (比如 $[l,r]\to [l,r-t]$ 就打到 $l-1$ 上)。最后扫一遍全部的 $i\in[1,n]\cap\mathbb{Z_+}$，这样最终复杂度 $O(n\sqrt m)$ 。可以看出比起普通的莫队，二次离线还有一个好处，就是只有 $O(n)$ 次插入，于是对于某些题就可以用值域分块的技巧做到 $O(n\sqrt m+n\sqrt n)$ 。
#### 2、值域分块
发现本质上需要支持这么一种操作：
> 维护一个值域序列，要求 $O(\sqrt n)$ 修改， $O(1)$ 求区间和。
这个比较有意思。发现要求 $O(1)$ 求区间和，那自然就是要维护前缀和。于是就分别维护块的前缀和 and 块内部的前缀和，每次修改就是要修改之后的块的前缀和 and 散点所在块内部的前缀和，查询作差即可。
最后复杂度 $O(n\sqrt m+n\sqrt n)$ 。
```cpp
using IPT::qrd;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;
vector< tuple<int, int, int> > ql[N], qr[N] ;
struct query{ int id, l, r ;} q[N] ;
il bool comp(const query &a, const query &b){
return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] :
((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
il int ask(int p){
int ret = 0 ;
for ( ; p ; p -= p & -p) ret += _bit[p] ;
return ret ;
}
il void add(int p){
for ( ; p <= V ; p += p & -p) _bit[p] ++ ;
}
il void Inssuf(const int &x){
for (int i = blv[x] + 1 ; i <= blv[V] ; ++ i) sumb[i] ++ ;
for (int i = x ; blv[x] == blv[i] && i <= V ; ++ i) sump[i] ++ ;
}
il int Asksuf(const int &x){
return sump[x] + sumb[blv[x]] ;
}
il void Inspre(const int &x){
for (int i = 1 ; i <= blv[x] - 1 ; ++ i) sumb[i] ++ ;
for (int i = x ; blv[x] == blv[i] && i >= 1 ; -- i) sump[i] ++ ;
}
il int Askpre(const int &x){
return sump[x] + sumb[blv[x]] ;
}
int main(){
qrd(n), qrd(m), B = n / sqrt(m) ;
for (int i = 1 ; i <= n ; ++ i)
qrd(base[i]), tmp[i] = base[i] ;
sort(tmp + 1, tmp + n + 1) ;
L = unique(tmp + 1, tmp + n + 1) - tmp - 1 ;
for (int i = 1 ; i <= n ; ++ i){
base[i] = lwb(tmp + 1, tmp + L + 1, base[i]) - tmp ;
V = max(base[i], V) ; bl[i] = i / B ;
}
B = sqrt(V) + 1 ;
for (int i = 0 ; i <= V ; ++ i) blv[i] = i / B + 1 ;
for (int i = n ; i >= 1 ; -- i)
s2[i] = s2[i + 1] + ask(base[i] - 1), add(base[i]) ;
fill(_bit, _bit + V + 1, 0) ;
for (int i = 1 ; i <= n ; ++ i)
s1[i] = s1[i - 1] + i - 1 - ask(base[i]), add(base[i]) ;
for (int i = 1 ; i <= m ; ++ i)
qrd(q[i].l), qrd(q[i].r), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ; q[0].l = 1, q[0].r = 0 ;
for (int i = 1 ; i <= m ; ++ i){
int newl = q[i].l ;
int newr = q[i].r ;
int l = q[i - 1].l ;
int r = q[i - 1].r ;
ans[i] -= s2[l] + s1[r] ;//l 的贡献变成了一个后缀，原来是 l'-(l-1),现在变成了 l-l'
ans[i] += s2[newl] + s1[newr] ;//l 和 r 要分开计算贡献
if (newl < l)
qr[newr + 1].emplace_back(newl, l - 1, -i) ;
else if (newl > l)
qr[newr + 1].emplace_back(l, newl - 1, i) ;
if (newr < r)
ql[l - 1].emplace_back(newr + 1, r, i) ;
else if (newr > r)
ql[l - 1].emplace_back(r + 1, newr, -i) ;
}
for (int i = 1 ; i <= n ; ++ i){
Inspre(base[i]) ;
for (const auto &j : ql[i]){
int l, r, id ;
tie(l, r, id) = j ; ll tmp = 0 ;
for (int o = l ; o <= r ; ++ o)
tmp += Askpre(base[o] + 1) ;
if (id < 0)
ans[id * (-1)] -= tmp ;
else ans[id] += tmp ;
}
}
memset(sumb, 0, sizeof(sumb)) ;
memset(sump, 0, sizeof(sump)) ;
for (int i = n ; i >= 1 ; -- i){
Inssuf(base[i]) ;
for (const auto &j : qr[i]){
int l, r, id ;
tie(l, r, id) = j ; ll tmp = 0 ;
for (int o = l ; o <= r ; ++ o)
tmp += Asksuf(base[o] - 1) ;
if (id < 0)
ans[id * (-1)] -= tmp ;
else ans[id] += tmp ;
}
}
for (int i = 1 ; i <= m ; ++ i) ans[i] += ans[i - 1] ;
for (int i = 1 ; i <= m ; ++ i) res[q[i].id] = ans[i] ;
qwa(res, n, '\n', '\n') ;return 0 ;
}
```