【题解】Ynoi2019模拟赛 Yuno loves sqrt technology II

考虑莫队。

如果是单纯的莫队的话，还需要一个树状数组来维护逆序对数，这样子的话复杂度是 \(O(n^{1.5}\log n)\)，难以接受。

怎么将这个树状数组消除？

考虑当前区间为 \([l,r-1]\) ，需要将右端点向右移动，即加入 \(a_r\) ，并且将答案加上 \(a_{l,l+1,\cdots,r-1}\) 中大于 \(a_r\) 的数的个数。其实这也就等于 \(a_{1\cdots r-1}\) 中大于 \(a_r\) 的个数减去 \(a_{1\cdots l-1}\) 中大于 \(a_r\) 的个数。

第一个贡献可以直接将整个数组扫一遍处理，时间复杂度 \(O(n\log n)\) 。

第二个询问的话，考虑将 \(l-1\) 处开个桶，然后将 \(r\) 丢入。因为莫队的移动次数是 \(O(n\sqrt{m})\) 的，因此空间的需求量也是 \(O(n\sqrt{m})\) 的。

最后只需要枚举左端点，然后获取其桶中的数的答案即可。

但是这题卡空间，不能直接存储贡献。同时可以发现一个 \(l\) 对应的一段 \(r\) 其实是连续的，因此直接将区间做右端点存下即可。

注意 ans 记录的是答案变化量，因此最终还需要做一遍前缀和。

（其实就是相当于将莫队的转移再次离线

// {{{ Template

/*CYJian yyds!*/
/*ldx gg txdy!*/
/*sto karry,tiger,lsqs orz*/

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef double db;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef vector <int> poly;
typedef pair <int,int> pii;

#define fi first
#define se second
#define rez resize
#define pp pop_back
#define pb push_back
#define mkp make_pair

#define lep(i,l,r) for(int i=l;i<=r;++i)
#define rep(i,r,l) for(int i=r;i>=l;--i)

#define CLEAR(x) memset((x),0,sizeof((x)))
#define COPY(x,y) memcpy((x),(y),sizeof((x)))

const int inf=1e9+7;
const int mod=1e9+7;

template <class T> inline T read() {
    char ch; bool flag=0; T x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch==‘-‘) flag=1;
    while(isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return flag?-x:x;
}
struct {
    inline operator ll() {return read<ll>();}
    inline operator int() {return read<int>();}
    inline operator bool() {return read<bool>();}
    inline operator double() {double _tmp; return scanf("%lf",&_tmp),_tmp;}
    template <class T> inline void operator () (T &x) {x=*this;}
    template <class T,class ...A> inline void operator () (T &x,A &...a)
    {x=*this,this->operator()(a...);}
} IN;

template <class T> inline void chkmax(T &x,T y) {if(x<y) x=y;}
template <class T> inline void chkmin(T &x,T y) {if(x>y) x=y;}

inline int mul(int x,int y) {return 1ll*x*y%mod;}
inline int dec(int x,int y) {x-=y; if(x<0) x+=mod; return x;}
inline int add(int x,int y) {x+=y; if(x>=mod) x-=mod; return x;}
inline void sub(int &x,int y) {x-=y; if(x<0) x+=mod;}
inline void pls(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
inline int modpow(int x,int y,int res=1) {
    if(y==-1) y=mod-2;
    for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
    return res;
}

// }}}
// #define debug

const int N=1e5+5;

int n,m,_,a[N];
ll ans[N];
struct Query {int l,r,id;} q[N];

// {{{ unique_a
inline void unique_a() {
    static int h[N];
    lep(i,1,n) h[i]=a[i];
    std::sort(h+1,h+1+n),_=1;
    lep(i,2,n) if(h[_]!=h[i]) h[++_]=h[i];
    lep(i,1,n) a[i]=std::lower_bound(h+1,h+1+_,a[i])-h;
}
// }}}

namespace Get_Pre { // {{{
ll pre[N],suf[N];

// {{{ BIT
int res,c[N];
inline int lowbit(int x) {return x&(-x);}
inline void modify(int x) {for(;x<=_;x+=lowbit(x)) ++c[x];}
inline int query(int x) {res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res;}
inline void clear() {CLEAR(c);}
// }}}

inline void solve() {
    clear(); lep(i,1,n) pre[i]=pre[i-1]+query(_-a[i]),modify(_-a[i]+1);
    clear(); rep(i,n,1) suf[i]=suf[i+1]+query(a[i]-1),modify(a[i]);
}
} using Get_Pre::pre,Get_Pre::suf; // }}}

// {{{ Solve
struct Node {int l,r,id,typ;};
std::vector <Node> sta1[N],sta2[N];

// {{{ Block
const int SqrtN=4e2+5;
int id[N],val[N],L[SqrtN],R[SqrtN],sum[SqrtN];

inline int query(int x) {return val[x]+sum[id[x]];}
inline void update1(int x) {
    lep(i,L[id[x]],x-1) ++val[i];
    lep(i,1,id[x]-1) ++sum[i];
}
inline void update2(int x) {
    lep(i,x+1,R[id[x]]) ++val[i];
    lep(i,id[x]+1,id[_]) ++sum[i];
}
inline void clear() {CLEAR(val),CLEAR(sum);}
// }}}

inline void solve() {
    int B=sqrt(_);
    for(int l=1,r=0,c=1;l<=_;l=r+1,++c) {
        r=min(l+B-1,_),L[c]=l,R[c]=r;
        lep(i,l,r) id[i]=c;
    }

    clear(); lep(i,1,n) {
        update1(a[i]);
        for(Node now:sta1[i]) lep(j,now.l,now.r) ans[now.id]+=1ll*query(a[j])*now.typ;
    }
    clear(); rep(i,n,1) {
        update2(a[i]);
        for(Node now:sta2[i]) lep(j,now.l,now.r) ans[now.id]+=1ll*query(a[j])*now.typ;
    }
}
// }}}

int pos[N];
int main() {
    IN(n,m);
    lep(i,1,n) IN(a[i]);
    lep(i,1,m) IN(q[i].l,q[i].r),q[i].id=i;

    unique_a();
    Get_Pre::solve();

    #ifdef debug
    printf("a : "); lep(i,1,n) printf("%d ",a[i]); puts("");
    printf("pre : "); lep(i,1,n) printf("%lld ",pre[i]); puts("");
    printf("suf : "); lep(i,1,n) printf("%lld ",suf[i]); puts("");
    #endif

    int B=n/sqrt(m*2/3+1);
    std::sort(q+1,q+1+m,[&](Query x,Query y){return (x.l/B)^(y.l/B)?x.l<y.l:x.r<y.r;});
    lep(i,1,m) pos[q[i].id]=i;

    int l=1,r=0;
    lep(i,1,m) {
        if(r<q[i].r) ans[i]+=(pre[q[i].r]-pre[r]),sta1[l-1].pb((Node){r+1,q[i].r,i,-1}),r=q[i].r;
        if(r>q[i].r) ans[i]-=(pre[r]-pre[q[i].r]),sta1[l-1].pb((Node){q[i].r+1,r,i,1}),r=q[i].r;
        if(l<q[i].l) ans[i]-=(suf[l]-suf[q[i].l]),sta2[r+1].pb((Node){l,q[i].l-1,i,1}),l=q[i].l;
        if(l>q[i].l) ans[i]+=(suf[q[i].l]-suf[l]),sta2[r+1].pb((Node){q[i].l,l-1,i,-1}),l=q[i].l;
    }

    solve();
    lep(i,1,m) ans[i]+=ans[i-1];
    lep(i,1,m) printf("%lld\n",ans[pos[i]]);
    return 0;
}

【题解】Ynoi2019模拟赛 Yuno loves sqrt technology II

原文：https://www.cnblogs.com/losermoonlights/p/14165847.html