Description
题目链接：P6774
给定长度为 n 的序列，其中第 i 个点的权值为 p_i，保证 p_i 为 [1,n] 的排列。
有 m 个询问，每个询问给定 l,r,x,y 表示求出序列区间为 [l,r] 的矩形的值在 [x,y] 的顺序对数量。
nleq 10^5,mleq 2times 10^5
Solution
历经 9 个月，终于回来补这道题了。
一道非常优秀的分块入门题，值得分块初学者花时间思考，不值得一写。 ——BFqwq
假设我们需要询问的是 (l,r,x,y) 的答案，那么我们就可以把这个区间拆成中间是整块，两边是散块的结构。那么我们只需要分别考虑对应的贡献即可。
- 首先是左右散块之内的 事先预处理所有块内排序，并离散化，预处理出前缀权值、位置的点的数量，查询时直接暴力枚举所有权值，每个点直接查询前缀和即可。
- 其次是左散块对右散块的贡献 块内事先排序，查询时直接归并排序查询顺序对数。
- 左右散块对中间整块的贡献 直接暴力枚举散块内所有点，预处理时开个前缀和记录前缀块、权值点的数量，查询时直接用前缀和计算即可。
- 中间整块之间 显然整块之间的答案可以通过容斥解决，直接暴力枚举每个块，考虑先加上之前块（包含本块）对这个块的贡献（预处理后前缀和查询），显然此时肯定会导致重复，那么再减去这个块自己内部的重复，再减去剩下之前的块的重复即可。
至此，你就切掉了这个分块入门题，祝你好运！>.<
Code
代码语言：javascript复制/*
s[i][j]表示1~i块权值<=j的数
g[i]表示块内离散化后的值
r[i][j]表示第i块离散化后j还原对应值
v[i][j]第i块<=j数个数
F1[k][i][j]第k块离散化后权值<=i位置<=j的权值的个数
F2[k][i][j]第k块离散化后权值<=i与<=j的块构成顺序对的个数
F3[k][i][j]第k块离散化后权值在[i,j]的顺序对数
*/
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=1e5 10,M=sqrt(N) 10;
int n,m,S,a[N],bl[N],tot,L[M],R[M],v[M][N],s[M][N],g[N],r[M][M],id,F1[M][M][M],F2[M][M][M],F3[M][M][M];
I void Build(){
RI i,j,k;S=sqrt(n);for(i=1;i<=n;i ) !((i-1)%S)&&(R[tot]=i-1,L[ tot]=i),bl[i]=tot;R[tot]=n;
for(j=1;j<=tot;j ){
for(i=L[j];i<=R[j];i ) v[j][a[i]]=i;
for(id=0,i=1;i<=n;i ) v[j][i]&&(r[j][g[v[j][i]]= id]=v[j][i],v[j][i]=1),v[j][i] =v[j][i-1],s[j][i]=s[j-1][i] v[j][i];
}
for(k=1;k<=tot;k ){
for(i=L[k];i<=R[k];i ) F1[k][g[i]][i-L[k] 1]=1;
for(i=1;i<=R[k]-L[k] 1;i ) for(j=1;j<=R[k]-L[k] 1;j ) F1[k][i][j] =F1[k][i][j-1] F1[k][i-1][j]-F1[k][i-1][j-1];
for(i=L[k];i<=R[k];i ) for(j=i 1;j<=R[k];j ) g[i]<g[j]&&(F3[k][g[i]][g[j]]=1);
for(i=1;i<=R[k]-L[k] 1;i ) for(j=1;j<=R[k]-L[k] 1;j ) F3[k][i][j] =F3[k][i][j-1] F3[k][i-1][j]-F3[k][i-1][j-1];
for(i=L[k];i<=R[k];i ){
for(j=1;j<k;j ) F2[k][g[i]][j]=s[j][a[i]]-s[j-1][a[i]];
F2[k][g[i]][k]=F3[k][g[i]][g[i]]-F3[k][g[i]][g[i]-1];
}for(i=1;i<=R[k]-L[k] 1;i ) for(j=1;j<=tot;j ) F2[k][i][j] =F2[k][i][j-1] F2[k][i-1][j]-F2[k][i-1][j-1];
}
}
#define QS(O,l,r,x,y) (O[r][y]-O[(l)-1][y]-O[r][(x)-1] O[(l)-1][(x)-1])
I LL Q(CI k,CI l,CI r,RI x,RI y){
RI i;x=v[k][x-1] 1,y=v[k][y];LL Ans=0;for(i=l;i<=r;i ) if(x<=g[i]&&g[i]<=y) Ans =QS(F1[k],x,g[i],l-L[k] 1,i-L[k]);
return Ans;
}
vector<int> A,B;
I LL Q(CI bL,CI bR,CI Ll,CI Lr,CI Rl,CI Rr,CI x,CI y){
A.clear(),B.clear();RI i,j,Ans=0;for(i=v[bL][x-1] 1;i<=v[bL][y];i ) if(Ll<=r[bL][i]&&r[bL][i]<=Lr) A.push_back(a[r[bL][i]]);
for(i=v[bR][x-1] 1;i<=v[bR][y];i ) if(Rl<=r[bR][i]&&r[bR][i]<=Rr) B.push_back(a[r[bR][i]]);
for(i=j=0;j<B.size();j ){W(i<A.size()&&A[i]<=B[j]) i ;Ans =i;}return Ans;
}
I LL Q(CI l,CI r,CI x,CI y){
RI i,bL=bl[l],bR=bl[r];if(bL==bR) return Q(bL,l,r,x,y);
LL Ans=Q(bL,l,R[bL],x,y) Q(bR,L[bR],r,x,y) Q(bL,bR,l,R[bL],L[bR],r,x,y);
for(i=l;i<=R[bL];i ) if(x<=a[i]&&a[i]<=y) Ans =QS(s,bL 1,bR-1,a[i],y);
for(i=L[bR];i<=r;i ) if(x<=a[i]&&a[i]<=y) Ans =QS(s,bL 1,bR-1,x,a[i]);
for(i=bL 1;i<=bR-1;i ){
RI X=v[i][x-1] 1,Y=v[i][y];
Ans =QS(F2[i],X,Y,bL 1,i)-QS(F3[i],1,X-1,X,Y)-(Y-X 1)*QS(s,bL 1,i-1,1,x-1);
}return Ans;
}
int main(){
RI i,l,r,x,y;for(read(n,m),i=1;i<=n;i ) read(a[i]);Build();W(m--) read(l,r,x,y),writeln(Q(l,r,x,y));return 0;
}
