莫队二次离线板子。

题意

给定一个序列 $a$，每次询问给出一个区间 $[l,r]$，求满足条件 $i<j\land a_i>a_j$ 且 $i,j\in [l,r]$ 的数对 $(i,j)$ 的数量。

Solution

看到上面这个东西，我们肯定能想到莫队二次离线，现在来思考实现上的细节。

设 $F(x,k)$ 为满足 $i\in[1,k]$ 且 $a_i>a_x$ 的 $i$ 的数量，$G(x,k)$ 为满足 $i\in[1,k]$ 且 $a_i<a_x$ 的 $i$ 的数量

在左指针挪到 $x$ 时答案的变化量为 $G(x,r)-G(x,x)$，右指针挪到 $x$ 时答案的变化量为 $F(x,x-1)-F(x,l-1)$。

显然，$F(x,x-1)$ 和 $G(x,x)$ 都可以直接 $O(n\log n)$ 树状数组预处理，而 $G(x.r)$ 和$F(x,l-1)$ 可以扫描线处理。

在实现扫描线的时候，我们会发现我们需要一种支持 $O(\sqrt n)$ 插入，$O(1)$ 查询在一个值域范围内的数的数量的数据结构，分块完全可以支持，只要维护块内前缀和和块间前缀和即可。

具体的实现可以看代码：

#include<cstdio>
#include<algorithm>
#include<vector>
#include<tuple>
#include<cmath>
#include<cstring>
namespace IO{
	#define BUFSIZE 10000000
	struct read{
		char buf[BUFSIZE],*p1,*p2,c,f;
		read():p1(buf),p2(buf){}
		char gc(void){
			if(p1==p2)p2=buf+fread(p1=buf,1,BUFSIZE,stdin);
			if(p1==p2)return EOF;
			else return *p1++;
		}
		read& operator >>(int& x){
			c=gc(),f=1,x=0;
			for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
			for(;c>='0'&&c<='9';c=gc())x=x*10+c-'0';
			x*=f;
			return *this;
		}
	};
	struct write{
		char buf[BUFSIZE],*p1,*p2,s[50];
		int tp;
		write():p1(buf),p2(buf+BUFSIZE){}
		~write(){flush();}
		void flush(void){
			fwrite(buf,1,p1-buf,stdout);
			p1=buf;
		}
		void pc(char c){
			if(p1==p2)flush();
			*p1++=c;
		}
		write& operator <<(long long x){
			if(x<0)x=-x,pc('-');
			do{s[tp++]=x%10+'0',x/=10;}while(x);
			while(tp)pc(s[--tp]);
			return *this;
		}
		write& operator <<(char x){
			pc(x);
			return *this;
		}
	};
	read in;
	write out;
}
using IO::in;
using IO::out;
std::vector<std::tuple<int,int,int,int,int> > v[100010];
int c[100010];
int n,m,a[100010],b[100010],bel[100010],le[100010],gr[100010],lv[320],rv[320],s[320],sv[320][320],sz,belv[100010];
long long ans[100010];
inline void updated(int i,int const &x){for(;i<=n;i+=i&-i)c[i]+=x;}//树状数组
inline int queryd(int i){int ans=0;for(;i;i-=i&-i)ans+=c[i];return ans;}
inline void update(int const &x){//分块
	for(int i=x-lv[belv[x]],*k=sv[belv[x]];i<sz;i++)++k[i];
	for(int i=belv[x],k=belv[n];i<=k;i++)++s[i];
}
inline int query(int const &x){
	return s[belv[x]-1]+sv[belv[x]][x-lv[belv[x]]];
}
struct node{
	int l,r,id;
	long long ans;
	bool operator <(node const &x)const{
		return bel[l]==bel[x.l]?r<x.r:l<x.l;
	}
}q[100010];
int main(){
	in>>n>>m;
	for(int i=1;i<=n;i++)in>>a[i],b[i]=a[i];
	std::sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1;i<=n;i++){//预处理
		le[i]=queryd(a[i]-1);
		gr[i]=queryd(n)-queryd(a[i]);
		updated(a[i],1);
	}
	::sz=sqrt(n);
	for(int i=1;i<=n;i++)belv[i]=(i-1)/::sz+1;
	for(int i=0,j=1;i<n;i+=::sz,j++)lv[j]=i+1,rv[j-1]=i;
	rv[belv[n]]=n;
	int sz=n/sqrt(m);
	for(int i=1;i<=n;i++)bel[i]=(i-1)/sz+1;
	for(int i=1;i<=m;i++)in>>q[i].l>>q[i].r,q[i].id=i;
	std::sort(q+1,q+m+1);
	for(int i=1,l=1,r=0;i<=m;i++){//莫队
		if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,1,1,i);
		while(l>q[i].l) --l,q[i].ans-=le[l];
		if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,0,-1,i);
		while(r<q[i].r) ++r,q[i].ans+=gr[r];
		if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,1,-1,i);
		while(l<q[i].l) q[i].ans+=le[l],++l;
		if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,0,1,i);
		while(r>q[i].r) q[i].ans-=gr[r],--r;
	}
	for(int p=1;p<=n;p++){//扫描线
		int l,r,cmp,kp,id;
		update(a[p]);
		for(auto&& x:v[p]){
			std::tie(l,r,cmp,kp,id)=x;
			for(int i=l;i<=r;i++)
				if(cmp==1) q[id].ans+=kp*query(a[i]-1);
				else q[id].ans+=kp*(query(n)-query(a[i]));
		}
	}
	for(int i=2;i<=m;i++)q[i].ans+=q[i-1].ans;
	for(int i=1;i<=m;i++)ans[q[i].id]=q[i].ans;
	for(int i=1;i<=m;i++)out<<ans[i]<<'\n';
	return 0;
}