「NOI2020」时代的眼泪

前言

这种东西看到就给人一种

分块分块分块分块分块分块!

啊啊啊啊啊啊啊啊啊啊啊

问题分析

这是一个二维区间顺序对问题，对于普通的区间顺序对问题，我们有简单分块解法

预处理整块的答案，有$n\sqrt n$个数要插入预处理，也就是有$O(\sqrt n)$个区间查询

对于散点暴力求，也是$n\sqrt n$个区间查询问题

那么离线+分块就可以做到$O(\sqrt n)$插入一个数，$O(\sqrt 1)$查询，并且有办法将空间实现到$O(n)$

那么对于二维区间考虑部分沿用上面的思路

Solution

首先对于散块的部分，是完全一样的处理，可以$O(n)$内存实现

具体的：

散点之间可以暴力$for$答案，每次还需要一个二维区间个数查询

每次需要查询的散点又是一段区间

可以描述为$O(m)$个查询，总共查询$O(m\sqrt n)$个散点

问题在于整块部分的查询$[p1,p2],[u,d]$

对于同一个块内的答案，可以暴力预处理出来

而块之间，可以转化为$[1,d]-[1,u-1]-[1,u-1]\times [u,d]$

前面两个前缀型问题，可以用如下方法实现：

按照$p_i$从小到大插入，同时维护每个块内已经出现的个数

每次插入$i$后，对于$i$前面的块，会产生$O(\sqrt n)$对 顺序对

我们要查询的是一个块编号$[p1,p2]$内块的关系，这是一个二维前缀和

可以把两个维度的前缀和分开给插入和查询

具体的，在插入时，处理$S_{l,r}=\sum_{i\ge l} C_{i,r}$

查询$[p1,p2]$时，就可以暴力求$S_{l,i}i\in[l,r]$的和

这样可以分摊复杂度为$O(n\sqrt n)$，并且内存为$O(n)$，常数较小

对于$[1,u-1]\times [u,d]$，从左到右一段段 查询过来，每次查询块内$[1,u-1]$$，[u,d]$个数即可

这个统计和上面的块内答案统计都需要预处理每个数在块内排名

但是也可以通过离线去掉这个步骤，避免了一个$O(n\sqrt n)$的数组

实际实现时，发现散块暴力的部分枚举起来实在太慢，所以块开大了一点，加了一点底层玄学优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
typedef vector <int> V;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e5+10,M=2e5+10,S=1000;

int n,m,A[N],len,P[N];
struct Blocker{
	int s[M],t[N];
	void clear(){ memset(s,0,(n+1)<<2),memset(t,0,(n+1)<<2); }
	void Add(int x){
		int p=x/len;
		rep(i,x,(p+1)*len-1) s[i]++;
		rep(i,p+1,n/len) t[i]++;
	}
	int operator [](const int &x) const{ return s[x]+t[x/len]; }
} B;
int L[M],R[M],U[M],D[M],p1[M],p2[M],I[M],T[M];
ll Ans[M];
struct Que{ int l,r,k,id; };
vector <Que> Q[N];
// 处理散点
void SolvePoints(){
	rep(i,1,n) {
		B.Add(A[i]);
		for(Que x:Q[i]) {
			rep(j,x.l,x.r) {
				int u=U[x.id],d=D[x.id];
				if(A[j]<u || A[j]>d) continue;
				if(j>i) cmin(d,A[j]-1);
				else cmax(u,A[j]+1);
				Ans[x.id]+=x.k*(B[d]-B[u-1]);
			}
		}
	}
}

vector <Pii> E[N];
// 处理块区间的 前缀逆序对
void SolveB1(){
	static ll s[S][S],c[S];
	rep(k,1,n) {
		int i=P[k],t=0,p=i/len;
		c[p]++;
		drep(j,p-1,0) t+=c[j],s[j][p]+=t;
		for(Pii x:E[k]) {
			int u=x.first,l=p1[u]+1,r=p2[u]-1;
			rep(j,l+1,r) Ans[u]+=s[l][j]*x.second;
		}
    }
}

//处理块内答案
void SolveB2(){
	static int s[S][S],C[N];
	rep(i,0,n/len) {
		int l=max(1,i*len),r=min(n,(i+1)*len-1);
		rep(j,1,n) C[j]=C[j-1]+(l<=P[j] && P[j]<=r);
		int L=C[n];
		rep(a,1,L+1) rep(b,a-1,L+1) s[a][b]=0;
		rep(a,l,r) rep(b,a+1,r) if(A[a]<=A[b]) s[C[A[a]]][C[A[b]]]++;
		drep(a,L,1) rep(b,a,L) s[a][b]+=s[a+1][b]+s[a][b-1]-s[a+1][b-1];
		rep(j,1,m) if(p1[j]<i && i<p2[j]) {
			Ans[j]+=s[C[U[j]-1]+1][C[D[j]]];
			Ans[j]-=1ll*T[j]*(C[D[j]]-C[U[j]-1]);
			T[j]+=C[U[j]-1];
		}
	}
}

// 本来是暴力for l,r内的逆序对的，但是太慢，加了一点底层优化
int Que(int i,int l,int r,int u,int d){
	if(r-l>45) {
		int mid=(l+r*3)/4;
		Q[l-1].pb({mid+1,r,-1,i});
		Q[mid].pb({mid+1,r,1,i});
		return Que(i,l,mid,u,d)+Que(i,mid+1,r,u,d);
	}
	int ans=0;
	rep(i,l,r) if(u<=A[i] && A[i]<=d) rep(j,i+1,r) ans+=A[i]<=A[j] && A[j]<=d;
	return ans;
}

int main(){
	freopen("tears.in","r",stdin),freopen("tears.out","w",stdout);
	n=rd(),m=rd(),len=ceil(sqrt(n/4.0));
	fprintf(stderr,"Block len=%d ,Block Count=%d\n",len,n/len);
	rep(i,1,n) P[A[i]=rd()]=i;
	clock_t ti=clock();
	rep(i,1,m) {
		I[i]=i,L[i]=rd(),R[i]=rd(),U[i]=rd(),D[i]=rd();
		p1[i]=L[i]/len,p2[i]=R[i]/len;
		if(p1[i]==p2[i]){ Ans[i]=Que(i,L[i],R[i],U[i],D[i]); continue; }
		Ans[i]=Que(i,L[i],(p1[i]+1)*len-1,U[i],D[i])+Que(i,p2[i]*len,R[i],U[i],D[i]);
		Q[L[i]-1].pb({p2[i]*len,R[i],-1,i});
		Q[p2[i]*len-1].pb({p2[i]*len,R[i],1,i});
		if(p1[i]<p2[i]-1) {
			Q[(p1[i]+1)*len-1].pb({L[i],(p1[i]+1)*len-1,-1,i});
			Q[p2[i]*len-1].pb({L[i],(p1[i]+1)*len-1,1,i});
			E[D[i]].pb(mp(i,1));
			E[U[i]-1].pb(mp(i,-1));
		}
	}
	fprintf(stderr,"Part0 %d\n",int(clock()-ti)),ti=clock();
	SolvePoints();
	fprintf(stderr,"Part1 %d\n",int(clock()-ti)),ti=clock();
	sort(I+1,I+m+1,[&](int x,int y){ return L[x]<L[y]; });
	SolveB1();
	fprintf(stderr,"Part2 %d\n",int(clock()-ti)),ti=clock();
	SolveB2();
	fprintf(stderr,"Part3 %d\n",int(clock()-ti)),ti=clock();
	rep(i,1,m) printf("%lld\n",Ans[i]);
}