P5047 Yuno loves sqrt technology II

首先我们显然会一个非常辣鸡的 $O(n\sqrt m\log n)$ 做法而且看不出怎么优化。。

于是考虑上二次离线莫队。

设 $[a,b][c,d]$ 表示满足 $x\in [a,b],y\in [c,d],a_x>a_y$ 的数量，也就是两个区间之间的逆序对数。如果 $c<b$ 我们认为它没有定义。

我们考虑移动一个区间，比如从 $l,r$ 移动到 $l,r’$ ，增加量是：

$$\sum_{i=r+1}^{r'} [l,i-1][i,i]$$

显然后面那个符号可以拆成前缀的差：

$$\sum_{i=r+1}^{r'} [1,i-1][i,i] - [1,l-1][i,i]$$

我们考虑 $[1,i-1][i,i]$ 这个东西可以方便地预处理前缀和。于是考虑我们现在要算的是：

$$\sum_{i=r+1}^{r'} [1,l-1][i,i]$$

也就是：

$$[1,l-1][r+1,r']$$

这个东西怎么算呢？

我们把莫队需要的这种样子的询问都拿出来，把所有 $[r+1,r’]$ 挂在 $l-1$ 下面就好了。一共会有 $m$ 个长成这样的询问，所以空间复杂度为 $O(m)$。并且由于莫队我们知道总的移动次数是不超过 $O(n\sqrt m)$ 的，于是就可以从再次离线算这个东西，从左到右加入数，然后计算比 $[r+1,r’]$ 内的数大的数字个数。为了让后面的暴力计算做到 $O(1)$ 我们可以根号平衡，值域分块一下，插入 $O(\sqrt n)$ 查询 $O(1)$ ，插入的次数是不超过 $O(n)$ 的于是总复杂度就优化到了 $O(n\sqrt m+m\sqrt n)$ 。

码起来还是比较轻松的。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007
typedef long long ll;
int n , m , blo;
int A[MAXN] , a[MAXN] , bl[MAXN];

struct que {
    int l , r , id;
    inline void rd( int x ) {
        id = x; scanf("%d%d",&l,&r);
    }
} Q[MAXN] ;

long long ans[MAXN];
long long Ls[MAXN] , Rs[MAXN]; // sum of [1,i-1][i,i] or [i,i][i+1,n]

namespace fwk {
    int T[MAXN];
    void add( int x , int c ) {
        while( x <= n ) T[x] += c , x += ( x & -x );
    }
    int sum( int x ) {
        int ret = 0;
        while( x > 0 ) ret += T[x] , x -= ( x & -x );
        return ret;
    }
}

int BLO;
namespace kuai1 {
    int T[MAXN] , lz[400];
    void add( int x ) { // ( 1 ~ x - 1 ) + 1
        per( i , x , ( x - 1 ) / BLO * BLO + 1 ) ++ T[i];
        per( i , ( x - 1 ) / BLO , 1 ) ++ lz[i];
    }
    int get( int x ) {
        return T[x] + lz[( x - 1 ) / BLO + 1];
    }
}

namespace kuai2 {
    int T[MAXN] , lz[400] , tot;
    void add( int x ) { // ( 1 ~ x - 1 ) + 1
        rep( i , x , ( x - 1 ) / BLO * BLO + BLO ) ++ T[i];
        rep( i , ( x - 1 ) / BLO + 2 , tot ) ++ lz[i];
    }
    int get( int x ) {
        return T[x] + lz[( x - 1 ) / BLO + 1];
    }
}

struct dq { int l , r , id , c; };
vector<dq> Rqs[MAXN] , Lqs[MAXN]; // Rqs : [1,i][l,r] , Lqs : [l,r][i,n]

bool cmp( que a , que b ) {
    return bl[a.l] == bl[b.l] ? bl[a.l] & 1 ? a.r < b.r : a.r > b.r : a.l < b.l;
}

void solve() {
    cin >> n >> m;
    blo = n / sqrt( m * 2 / 3 ); BLO = sqrt( n );
    rep( i , 1 , n ) scanf("%d",A + i) , bl[i] = ( i - 1 ) / blo + 1 , a[i] = A[i];
    sort( a + 1 , a + 1 + n );
    int sz = unique( a + 1 , a + 1 + n ) - a - 1;
    rep( i , 1 , n ) A[i] = lower_bound( a + 1 , a + 1 + sz , A[i] ) - a;
    rep( i , 1 , m ) Q[i].rd( i );
    sort( Q + 1 , Q + 1 + m , cmp );
    rep( i , 1 , n ) Ls[i] = fwk::sum( n - A[i] ) , fwk::add( n - A[i] + 1 , 1 );
    rep( i , 1 , n ) Ls[i] += Ls[i - 1];
    mem( fwk::T );
    per( i , n , 1 ) Rs[i] = fwk::sum( A[i] - 1 ) , fwk::add( A[i] , 1 );
    per( i , n , 1 ) Rs[i] += Rs[i + 1];
    int l = 1 , r = 0 , L , R , idx;
    rep( i , 1 , m ) {
        L = Q[i].l , R = Q[i].r , idx = Q[i].id;
        if( r < R ) Lqs[l - 1].eb( (dq){ r + 1 , R , idx , -1 } ) , ans[idx] += Ls[R] - Ls[r];
        if( r > R ) Lqs[l - 1].eb( (dq){ R + 1 , r , idx , 1 } ) , ans[idx] -= Ls[r] - Ls[R];
        r = R;
        if( l > L ) Rqs[R + 1].eb( (dq){ L , l - 1 , idx , -1 } ) , ans[idx] += Rs[L] - Rs[l];
        if( l < L ) Rqs[R + 1].eb( (dq){ l , L - 1 , idx , 1 } ) , ans[idx] -= Rs[l] - Rs[L];
        l = L;
    }
    long long re;
    rep( i , 1 , n ) {
        kuai1::add( A[i] - 1 );
        for( auto& t : Lqs[i] ) {
            re = 0;
            rep( j , t.l , t.r )
                re += kuai1::get( A[j] );
            ans[t.id] += t.c * re;
        }
    }
    kuai2::tot = ( sz - 1 ) / BLO + 1;
    per( i , n , 1 ) {
        kuai2::add( A[i] + 1 );
        for( auto& t : Rqs[i] ) {
            re = 0;
            rep( j , t.l , t.r )
                re += kuai2::get( A[j] );
            ans[t.id] += t.c * re;
        }
    }
    rep( i , 1 , m ) ans[Q[i].id] += ans[Q[i - 1].id];
    rep( i , 1 , m ) printf("%lld\n",ans[i]);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}