首页
关于
笔记
文章
友链

Solution -「NOI 2020」时代的眼泪

cirnovsky /

§ Description

Link。

给出一个二维平面以及一些点，保证点不在同行 / 同列。每次询问求出一个子矩阵里面的顺序对。

§ Solution

卡常，卡你吗。

膜拜 dX。

基本是把 dX 的题解贺了过来所以没啥参考的价值。

不过有很多细节的处理不一样，大概能算个 150\frac{1}{50} 成新？

对序列分块，把贡献分成 整块 - 散块 / 整块 - 整块/ 散块 - 整块 / 散块 - 散块 以及 散块内部 / 整块内部 共六种贡献。

记 ans0(l,r,x,y)\textit{ans}_{0}(l,r,x,y) 为询问 l,r,x,yl,r,x,y 的答案。

同时预处理出 lb(i,j),ub(i,j)\textit{lb}(i,j),\textit{ub}(i,j) 分别表示在块 ii 中数 jj 的 std::lower_bound / std::upper_bound 值，下文如果写成单元函数的形式那么就是省去了第一维。

以及预先做一个块内排序，记为 ord(i,j)\textit{ord}(i,j)，表示块 ii 中排序后的第 jj 个元素。

注意本文在每个 subtask 定义的东西在其他 subtask 依然适用。

  • 散块 - 散块；

两边的都是 n\sqrt{n} 级别，拉出来分别排序后归并计算顺序对即可。

  • 散块内部

考虑如何对 ans0(l,r,x,y)\textit{ans}_{0}(l,r,x,y) 进行容斥。

主要矛盾集中在：会出现 (a∈[1,x),b∈[x,y])(a\in[1,x),b\in[x,y]) 这样的贡献。令 cnt0(i,j)\textit{cnt}_{0}(i,j) 表示 [lp,i][\textit{lp},i] 中 rank1\textit{rank}_{1} 小于 jj 的数的数量，其中 lp\textit{lp} 是当前块的左端点，下同，如果出现 rp\textit{rp} 同理，rank1\textit{rank}_{1} 的定义见下文。

则容斥可以写为 ans0(l,r,x,y)=ans0(l,r,1,y)−ans0(l,r,1,x−1)−∑i=lr[ai∈[x,y]]⋅cnt0(i,lb(x)−1)\textit{ans}_{0}(l,r,x,y)=\textit{ans}_{0}(l,r,1,y)-\textit{ans}_{0}(l,r,1,x-1)-\sum_{i=l}^{r}[a_{i}\in[x,y]]\cdot\textit{cnt}_{0}(i,\textit{lb}(x)-1)。

又有 ans0(l,r,1,x)=∑i=lr[ai⩽x]⋅cnt0(i,rank1(i))\textit{ans}_{0}(l,r,1,x)=\sum_{i=l}^{r}[a_{i}\leqslant x]\cdot\textit{cnt}_{0}(i,\textit{rank}_{1}(i))，我们就可以做到单次 O(n)\mathcal{O}(\sqrt{n})，注意的 l,rl,r 触及散块边界者不同时，对 cnt0\textit{cnt}_{0} 的容斥也有区别。

  • 整块 - 整块

令 cnt1(i,j)\textit{cnt}_{1}(i,j) 为块 [1,i][1,i] 中 ⩽j\leqslant j 的元素个数，ans1(L,R,x,y)\textit{ans}_{1}(L,R,x,y) 为块 [L,R][L,R] 的答案，以及 rank0(i,j)\textit{rank}_{0}(i,j) 是块 ii 中排名 jj 的元素在原数组中的下标。

我们掏出传统容斥：ans1(L,R,x,y)=ans1(L,R,1,y)−ans1(L,R,1,x−1)−∑i=LRPiQi\textit{ans}_{1}(L,R,x,y)=\textit{ans}_{1}(L,R,1,y)-\textit{ans}_{1}(L,R,1,x-1)-\sum_{i=L}^{R}P_{i}Q_{i}，PiP_{i} 是块 [L,i)[L,i) 中 <x<x 的元素个数，QiQ_{i} 是块 ii 种 ∈[x,y]\in[x,y] 的元素个数。

考虑算 ans1(L,R,1,x)\textit{ans}_{1}(L,R,1,x)。

定义 rank1(i,j)\textit{rank}_{1}(i,j) 为块 ii 中第 jj 个元素的排名（从小到大，下同），rank2(i,j)\textit{rank}_{2}(i,j) 为块 ii 中满足 <j<j 的最大元素的排名，preb(i,j)\textit{pre}_{b}(i,j) 为块 [i,j][i,j] 中所有 <rank1(i,j)<\textit{rank}_{1}(i,j) 的元素数量。

易知 preb(i,j)=cnt1(i,rank1(i,j)−1)\textit{pre}_{b}(i,j)=\textit{cnt}_{1}(i,\textit{rank}_{1}(i,j)-1)，再定义 cp0(i,L,r)n,n,n\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{0}(i,L,r)} 为块 [1,L][1,L] 与块 ii 前 rr 小的元素组成的顺序对数量，同样易知 cp0(i,L,r)=∑k∈T[rank1(i,k)⩽r]⋅preb(L,rank1(i,k))\textit{cp}_{0}(i,L,r)=\sum_{k\in T}[\textit{rank}_{1}(i,k)\leqslant r]\cdot\textit{pre}_{b}(L,\textit{rank}_{1}(i,k))，其中 TT 是块 ii 的元素集。但这样搞状态数 O(nn)\mathcal{O}(n\sqrt{n}) 转移还要 n\mathcal{\sqrt{n}} 而且不好前缀和。

不过可以发现使用 ord\textit{ord} 数组 cp0\textit{cp}_{0} 就可以递推了：cp0(i,L,r)=∑k=lpr+lp−1preb(L,k)=cp0(i,L,r−1)+preb(L,r+lp−1)\textit{cp}_{0}(i,L,r)=\sum_{k=lp}^{r+lp-1}\textit{pre}_{b}(L,k)=\textit{cp}_{0}(i,L,r-1)+\textit{pre}_{b}(L,r+lp-1)。

然后 ans1(L,R,1,x)=∑i=L+1Rcp0(i,i−1,rank2(i,x))−cp0(i,L−1,rank2(i,x))\textit{ans}_{1}(L,R,1,x)=\sum_{i=L+1}^{R}\textit{cp}_{0}(i,i-1,\textit{rank}_{2}(i,x))-\textit{cp}_{0}(i,L-1,\textit{rank}_{2}(i,x))。

预处理 cp0\textit{cp}_{0} 是 O(nn)\mathcal{O}(n\sqrt{n})，单次回答 O(n)\mathcal{O}(\sqrt{n})。

  • 散块 - 整块

枚举散块里面的元素，利用 cnt1(i,j)\textit{cnt}_{1}(i,j) 计算答案。

具体是令散块元素集为 TT，整块编号为 L,RL,R， ∑i∈Tcnt1(R,i)−cnt1(L−1,i)\sum_{i\in T}\textit{cnt}_{1}(R,i)-\textit{cnt}_{1}(L-1,i)。

  • 整块 - 散块

和上面有什么区别吗？

  • 整块内部

预处理数组 cp1(i,x,y)n,n,n\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{1}(i,x,y)} 表示取 ord(i,x…y)\textit{ord}(i,x\dots y) 组成的序列的顺序对数量。

用 rank0\textit{rank}_{0} 来预处理：cp1(i,x,y)=cp1(i,x,y−1)+cnt0(rank0(i,y),y−1)−cnt0(rank0(i,y),x−1)\textit{cp}_{1}(i,x,y)=\textit{cp}_{1}(i,x,y-1)+\textit{cnt}_{0}(\textit{rank}_{0}(i,y),y-1)-\textit{cnt}_{0}(\textit{rank}_{0}(i,y),x-1)。

综上，这个问题得以一个 O(nn)\mathcal{O}(n\sqrt{n}) 的在线算法解决。

代码也是抄的 dX，像个 shit 一样就折叠了。

% 死X 
//almost copied from dead_X sry
//kouhu has no qiantu
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int Read()
{
	int x=0;char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
	return x;
}
const int N=101111,A=460,BS=A+10;
ll cp0[BS][BS][BS];
int a[N],rk0[BS][BS],cnt0[BS][N],cp1[BS][BS][BS],lb[BS][N],rk1[N],cnt1[BS][N],L[BS],R[BS];
bool cmp(int x,int y) { return a[x]<a[y]; }
namespace IO{
    const int sz=1<<22;
    char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
    inline char gc(){
        return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
    }
    template<class T> void gi(T& x){
        x=0; char c=gc();
        for(;c<'0'||c>'9';c=gc());
        for(;c>='0'&&c<='9';c=gc())
            x=(x<<3)+(x<<1)+(c-'0');
    }
    inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
    inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
    template<class T> void pi(T x,char c='\n'){
        if(x<0) x=-x;
        if(x==0) pc('0'); int t=0;
        for(;x;x/=10) p[++t]=x%10+'0';
        for(;t;--t) pc(p[t]); pc(c);
    }
    struct F{~F(){flush();}}f; 
}
using IO::gi;
using IO::pi;
inline int read() { int r; gi(r); return r; }
int main(){
#ifdef ONLINE_JUDGE
	freopen("tears.in","r",stdin);
	freopen("tears.out","w",stdout);
#endif
	int n=read(),m=read(),B=n/A;
	for(int i=0;i<n;++i)a[i]=read();
	for(int i=n;i<(B+1)*A;++i)a[i]=i;
	for(int i=0;i<=B;++i){
		for(int j=i*A,k=0;k<A;++j,++k)rk0[i][k]=j;
		sort(rk0[i],rk0[i]+A,[](int x,int y){return a[x]<a[y];});
		for(int j=0;j<A;++j)rk1[rk0[i][j]]=j,cnt0[j][rk0[i][j]]=1;
		for(int j=i*A+1;j<(i+1)*A;++j)
			for(int k=0;k<A;++k)cnt0[k][j]+=cnt0[k][j-1];
		for(int j=i*A;j<(i+1)*A;++j)
			for(int k=1;k<A;++k)cnt0[k][j]+=cnt0[k-1][j];
		for(int j=i*A;j<(i+1)*A;++j)++cnt1[i][a[j]];
		if(i)for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i-1][j];
		for(int j=1,k=0;j<=101000;++j)(k<A)&&(j>=a[rk0[i][k]])&&(++k),lb[i][j]=k;
	}
	for(int i=0;i<=B;++i)
		for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i][j-1];
	for(int i=1;i<B;++i)for(int j=0;j<i;++j)for(int k=0;k<A;++k)
		cp0[i][j][k+1]=cnt1[j][a[rk0[i][k]]]+cp0[i][j][k];
	for(int i=0;i<B;++i)for(int j=0;j<A;++j)for(int k=j+1;k<A;++k)
		cp1[i][j][k]=cp1[i][j][k-1]+cnt0[k-1][rk0[i][k]]-((j==0)?0:cnt0[j-1][rk0[i][k]]);
	for(;m;--m){
		int l=read()-1,r=read()-1,x=read(),y=read(),bl=l/A,br=r/A;
		if(bl==br){
			int ans=0;
			for(int i=l;i<=r;++i){
				if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
				if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
			}
			pi(ans);
		}
		else{
			ll ans=0;
			for(int i=l;i<(bl+1)*A;++i){
				if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i]-((l%A)?cnt0[rk1[i]-1][l-1]:0);
				if(lb[bl][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[bl][x-1]-1][i]-((l%A&&lb[bl][x-1])?cnt0[lb[bl][x-1]-1][l-1]:0);
				if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][y]-cnt1[bl][y]-cnt1[br-1][a[i]]+cnt1[bl][a[i]];
			}
			for(int i=br*A;i<=r;++i){
				if(x<=a[i]&&a[i]<=y&&rk1[i])ans+=cnt0[rk1[i]-1][i];
				if(lb[br][x-1]&&x<=a[i]&&a[i]<=y)ans-=cnt0[lb[br][x-1]-1][i];
				if(x<=a[i]&&a[i]<=y)ans+=cnt1[br-1][a[i]]-cnt1[bl][a[i]]-cnt1[br-1][x-1]+cnt1[bl][x-1];
			}
			int lt=0,rt=0;
			for(int i=0;i<A;++i){
				if(rk0[bl][i]>=l&&x<=a[rk0[bl][i]]&&a[rk0[bl][i]]<=y)L[++lt]=rk0[bl][i];
				if(rk0[br][i]<=r&&x<=a[rk0[br][i]]&&a[rk0[br][i]]<=y)R[++rt]=rk0[br][i];
			}
			for(int i=1,t=1;i<=rt;++i){
				while(t<=lt&&a[L[t]]<a[R[i]])++t;
				ans+=t-1;
			}
			for(int i=bl+1;i<br;++i)if(lb[i][y])ans+=cp1[i][lb[i][x-1]][lb[i][y]-1];
			for(int i=bl+2;i<br;++i)
				ans+=cp0[i][i-1][lb[i][y]]-cp0[i][bl][lb[i][y]]-cp0[i][i-1][lb[i][x-1]]+cp0[i][bl][lb[i][x-1]],
				ans-=ll(cnt1[i][y]-cnt1[i-1][y]-cnt1[i][x-1]+cnt1[i-1][x-1])*(cnt1[i-1][x-1]-cnt1[bl][x-1]);
			pi(ans);
		}
	}
	return 0;
}