自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:06:32，当前版本为作者最后更新于2019-04-24 17:59:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一种非常腻害的高科技。二次离线莫队，$stOlxlOrz$

首先我们康康这道题的暴力莫队怎么做。

其实就是搞个权值树状数组，每次右指针右移的时候查询一下当前区间 $[l,r]$ 有多少个数比它大即可。

其他类似。

复杂度$O(n\sqrt m\log n)$

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 100000 + 5 ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define lowbit(x) ( x & ( - x ) )
int n, m, tot, ans[N] ;
int tree[N], c[N] ; 
struct Q {
    int l, r, id ;  
} q[N], p[N];
bool cmp( Q a, Q b ) {
    return ( a.l / tot == b.l / tot ) ? a.r < b.r : a.l < b.l ;  
}
bool cmp2( Q a, Q b ) {
    return a.l < b.l ;
}
void tr_add( int x, int k ) {
    for( int i = x; i <= n; i += lowbit(i) ) tree[i] += k ; 
}
int tr_sum( int x ) {
    int ans = 0 ;
    for( int i = x; i; i -= lowbit(i) ) ans += tree[i] ; 
    return ans ; 
}
void init() {
    sort( q + 1, q + m + 1, cmp ) ;
    int l = 1, r = 0; int Ans = 0 ;
    rep( i, 1, m ) {
        while( r < q[i].r ) Ans += 1ll * ( r - l + 1 - tr_sum(c[++ r]) ), tr_add( c[r], 1 ) ;
        while( r > q[i].r ) Ans -= 1ll * ( r - l + 1 - tr_sum(c[r --]) ), tr_add( c[r + 1], -1 ) ;
        while( l < q[i].l ) Ans -= 1ll * tr_sum( c[l ++] - 1 ), tr_add( c[l - 1], -1 ) ;
        while( l > q[i].l ) Ans += 1ll * tr_sum( c[-- l] - 1 ), tr_add( c[l], 1 ) ; 
        ans[q[i].id] = Ans ; 
    }
    rep( i, 1, m ) printf("%lld\n", ans[i] ) ;
}
signed main()
{
    n = read(), m = read() ; tot = n / sqrt( m * 1.5 ) ;
    rep( i, 1, n ) p[i].l = c[i] = read(), p[i].id = i ; 
    sort( p + 1, p + n + 1, cmp2 ) ; 
    int idnum = 0 ; p[0].l = -1 ; 
    rep( i, 1, n ) c[p[i].id] = ( idnum += ( p[i].l != p[i - 1].l ) ) ;
    rep( i, 1, m ) q[i].l = read(), q[i].r = read(), q[i].id = i ; 
    init() ; 
    return 0;
}

貌似在$O(2)$加持下可以获得 $20$ 的高分$(-///-)$

考虑优化，我们发现我们的某一次询问其实是可以差分的。

即每次右指针右移的时候，都有这样的一组询问：$l-r$中有多少数比$a[r]$大

然而这个东西可以差分：$[1,r]$中比$a[r]$大的数的数量$-[1,l]$中比$a[r]$大的数的数量。

我们发现对于前面那一坨貌似就是直接的逆序对，可以用树状数组做。 复杂度$O(nlogn)$

然后对于后面那一坨，我们可以将莫队指针的移动再次离线，将所有指针$r$的移动，存到其移动前对应的$l$处$($开个$vector)$

然后我们想要处理出后面那一坨怎么办，将右指针的移动再次离线后，我们可以考虑以类似于扫描线的方式让左指针从$1-n$ 扫 过去

这样我们只需要在扫到的位置$x$时去解决以$x$为左端点的右端点的移动即可。（即$1-x$内有多少个数比存下来的右端点大）

这个时候我们一共存了$n\sqrt m$ 组移动，（莫队复杂度，总移动次数）也就是要处理$n\sqrt m$组询问。

然而我们可以平衡它的复杂度，因为我们要处理$n\sqrt m$询问，却只需要插入$O(n)$组数（即左端点扫过去的过程只移动 $n$ 次）

可以使用一个插入$O(\sqrt n),$查询$O(1)$的数组结构$->$值域分块。

对于莫队中的四种移动分$4$类讨论，最后需要从$1-n$用左端点扫一遍还需要再用右端点从$n-1$扫一遍。

这样复杂度就被平衡到了$O(n\sqrt m+n\sqrt n)$辣。

但是这样做要把$n\sqrt m$移动存下来，空间吃不下。

我们发现其实莫队的移动和有规律，当右端点移动的时候，其左端点并没有发生任何移动，换而言只，我们刚刚的做法其实将所有右端点的移动都存在了同一个左端点$l$的$vector$内。

而且这些右端点的编号其实都是连续的，所以其实我们根本就没必要所有的移动都存下来，可以将左端点不动的若干次右端点的移动当作一个区间存起来就行了。

当然你对于区间内的元素的询问还是要逐一处理的。

这样空间复杂度就变成了 $O(M)$

注意，如果这样处理最后对于每个ans数组其实存下来的是其于上一次的左右端点之间的变化量，所以还要再做一遍前缀和。

下面是喜闻乐见的代码$QwQ$

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 100000 + 5 ;
const int M = 355 ; 
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define drep( i, t, s ) for( register int i = t; i >= s; -- i )
#define lowbit(x) ( x & ( - x ) )
int n, m, tot, idnum, tree[N], c[N], num1[N], num2[N], cnt, w[N], bel[N], sz, L[M], R[M], ad[M] ; 
LL ans[N], sum1[N], sum2[N];
struct Q { int l, r, id ; } q[N], p[N];
struct node { int p, l, r, id ; };
vector< node> vec1[N], vec2[N] ; 
bool cmp( Q a, Q b ) { return ( a.l / tot == b.l / tot ) ? a.r < b.r : a.l < b.l ; }
bool cmp2( Q a, Q b ) { return a.l < b.l ; }
void tr_add( int x, int k ) { for( int i = x; i <= n; i += lowbit(i) ) tree[i] += k ; }
int tr_sum( int x ) {
    int ans = 0 ;
    for( int i = x; i; i -= lowbit(i) ) ans += tree[i] ; 
    return ans ; 
}
void add1( int x, int p, int k1, int k2, int id ) { //存查询 
    vec1[x].push_back((node){ p, k1, k2, id } ) ;
}
void add2( int x, int p, int k1, int k2, int id ) {//存查询 
    vec2[x].push_back((node){ p, k1, k2, id } ) ;
}
void pushup1( int x ) { //左边做的值域分块 
    if( ad[bel[x]] ) rep( i, L[bel[x]], R[bel[x]] ) w[i] += ad[bel[x]] ; ad[bel[x]] = 0 ;
    rep( i, L[bel[x]], x ) ++ w[i];
    int siz = bel[x] - 1 ; rep( i, 1, siz ) ++ ad[i] ;
}
void pushup2( int x ) { //右边做的值域分块 
    if( ad[bel[x]] ) rep( i, L[bel[x]], R[bel[x]] ) w[i] += ad[bel[x]] ; ad[bel[x]] = 0 ;
    rep( i, x, R[bel[x]] ) ++ w[i] ; rep( i, bel[x] + 1, sz ) ++ ad[i] ; 
}
void solve() {
    cnt = sqrt( idnum ); sz = 1; L[sz] = 1;  
    if( cnt * cnt < idnum ) ++ cnt ; 
    rep( i, 1, idnum ) { bel[i] = sz ; if( i % cnt == 0 ) R[sz] = i, L[++ sz] = i + 1 ; } //分块初始化 
	R[sz] = idnum ;
	rep( i, 1, n ) {
        int siz = vec1[i].size() - 1, fr, ed, id; LL p ; 
        rep( j, 0, siz ) { 
		id = vec1[i][j].id, p = 1ll * vec1[i][j].p, fr = vec1[i][j].l, ed = vec1[i][j].r; 
			rep( k, fr, ed ) ans[id] += 1ll * p * ( ad[bel[c[k] + 1]] + w[c[k] + 1] );
		} pushup1( c[i] ); //给[1,c[i]]+1 
    }
    memset( ad, 0, sizeof(ad) ), memset( w, 0, sizeof(w) ) ;
    drep( i, n, 1 ) {
        int siz = vec2[i].size() - 1, fr, ed, id; LL p ;
        rep( j, 0, siz ) { 
		id = vec2[i][j].id, p = 1ll * vec2[i][j].p, fr = vec2[i][j].l, ed = vec2[i][j].r; 
            rep( k, fr, ed ) ans[id] += 1ll * p * ( ad[bel[c[k] - 1]] + w[c[k] - 1] );
		} pushup2( c[i] ) ;//给 [c[i],n]+1 
    }
}
signed main()
{
    n = read(), m = read() ; tot = 355 ;
    rep( i, 1, n ) p[i].l = c[i] = read(), p[i].id = i ; 
    sort( p + 1, p + n + 1, cmp2 ), p[0].l = -1 ; 
    rep( i, 1, n ) c[p[i].id] = ( idnum += ( p[i].l != p[i - 1].l ) ) ; //离散化 
    rep( i, 1, m ) q[i].l = read(), q[i].r = read(), q[i].id = i ;  //存查询 
    rep( i, 1, n ) num1[i] += ( i - 1 - tr_sum(c[i]) ), tr_add( c[i], 1 ), sum1[i] = sum1[i - 1] + num1[i] ; //从左往右做 
    memset( tree, 0, sizeof(tree) ) ; 
    drep( i, n, 1 ) num2[i] += tr_sum(c[i] - 1), tr_add( c[i], 1 ), sum2[i] = sum2[i + 1] + num2[i] ;//从右往左做 
    sort( q + 1, q + m + 1, cmp ) ;
    int l = 1, r = 0;
    rep( i, 1, m ) {
        if( r < q[i].r ) ans[q[i].id] += ( sum1[q[i].r] - sum1[r] ), 
			add1( l, -1, r + 1, q[i].r, q[i].id ), r = q[i].r ;
        if( r > q[i].r ) ans[q[i].id] -= ( sum1[r] - sum1[q[i].r] ), 
			add1( l, 1, q[i].r + 1, r, q[i].id ), r = q[i].r ;
        if( l < q[i].l ) ans[q[i].id] -= ( sum2[l] - sum2[q[i].l]), 
			add2( r, 1, l, q[i].l - 1, q[i].id ), l = q[i].l ;
        if( l > q[i].l ) ans[q[i].id] += ( sum2[q[i].l] - sum2[l] ), 
			add2( r, -1, q[i].l, l - 1, q[i].id ), l = q[i].l ;
    }
    solve() ; 
    rep( i, 1, m ) ans[q[i].id] += ans[q[i - 1].id] ; rep( i, 1, m ) printf("%lld\n", ans[i] ) ;
    return 0;
}