Luogu

分析

考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的，由于这是 Ynoi 所以过不了。

由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的个数，另一个是区间中比 $x$ 大的个数。因为两种情况类似所以这里只考虑右端点。

首先是 $f(x,[1,x−1])$，直接扫一遍并用树状数组维护即可。时间复杂度 $\mathcal{O}(n\log n)$。

然后是 $f(x,[1,t])$。可以发现求这部分总共需要进行 $n$ 次单点修改和 $n\sqrt{n}$ 次查询后缀和，为了保证复杂度我们需要一个支持 $\mathcal{O}(1)$ 查询后缀和、$\mathcal{O}(\sqrt{n})$ 修改的数据结构，值域分块即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,M=317+10;

int n,m,a[N];
vector<int> S;
int B,bl[N],L[M],R[M],sb[M],s[N];
struct query { int l,r,id,w; } q[N];
bool operator <(query a,query b) {
    return bl[a.l]!=bl[b.l]?a.l<b.l:a.r<b.r;
}
vector<query> vl[N],vr[N];

ll prel[N],prer[N],ans[N];
struct BIT {
    int c[N];
    void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
    int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }
} tL,tR;

int main() {
    n=read(),m=read(); B=sqrt(n);
    for (int i=1;i<=n;++i) a[i]=read(),S.emplace_back(a[i]);
    sort(S.begin(),S.end()); S.erase(unique(S.begin(),S.end()),S.end());
    for (int i=1;i<=n;++i) a[i]=lower_bound(S.begin(),S.end(),a[i])-S.begin()+1;
    for (int i=1;i<=n;++i) bl[i]=(i-1)/B+1;
    for (int i=1;i<=bl[n];++i) L[i]=(i-1)*B+1,R[i]=min(i*B,n);
    for (int i=1;i<=m;++i) q[i]=(query){read(),read(),i,0};
    q[0]=(query){1,0,0}; sort(q+1,q+m+1);
    for (int i=1;i<=n;++i) prer[i]=prer[i-1]+i-1-tR.sum(a[i]),tR.add(a[i],1);
    for (int i=n;i>=1;--i) tL.add(a[i],1),prel[i]=prel[i+1]+tL.sum(a[i]-1);
    for (int i=1;i<=m;++i) {
        ans[q[i].id]+=prer[q[i].r]-prer[q[i-1].r];
        ans[q[i].id]+=prel[q[i].l]-prel[q[i-1].l];
        if (q[i].r<q[i-1].r)
            vr[q[i-1].l-1].emplace_back((query){q[i].r+1,q[i-1].r,q[i].id,1});
        else
            vr[q[i-1].l-1].emplace_back((query){q[i-1].r+1,q[i].r,q[i].id,-1});
        if (q[i].l<q[i-1].l)
            vl[q[i].r+1].emplace_back((query){q[i].l,q[i-1].l-1,q[i].id,-1});
        else
            vl[q[i].r+1].emplace_back((query){q[i-1].l,q[i].l-1,q[i].id,1});
    }
    for (int i=1;i<=n;++i) {
        for (int j=1;j<bl[a[i]];++j) ++sb[j];
        for (int j=L[bl[a[i]]];j<=a[i];++j) ++s[j];
        for (auto j:vr[i]) {
            ll sum=0;
            for (int p=j.l;p<=j.r;++p) sum+=sb[bl[a[p]+1]]+s[a[p]+1];
            ans[j.id]+=j.w*sum;
        }
    }
    memset(sb,0,sizeof(sb)),memset(s,0,sizeof(s));
    for (int i=n;i>=1;--i) {
        for (int j=bl[n];j>bl[a[i]];--j) ++sb[j];
        for (int j=R[bl[a[i]]];j>=a[i];--j) ++s[j];
        for (auto j:vl[i]) {
            ll sum=0;
            for (int p=j.l;p<=j.r;++p) sum+=sb[bl[a[p]-1]]+s[a[p]-1];
            ans[j.id]+=j.w*sum;
        }
    }
    for (int i=1;i<=m;++i) ans[q[i].id]+=ans[q[i-1].id];
    for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}