P6774 [NOI2020] 时代的眼泪

(Updated: )
oi

Description

题目链接：P6774

给定长度为 $n$ 的序列，其中第 $i$ 个点的权值为 $p_i$，保证 $p_i$ 为 $[1,n]$ 的排列。

有 $m$ 个询问，每个询问给定 $l,r,x,y$ 表示求出序列区间为 $[l,r]$ 的矩形的值在 $[x,y]$ 的顺序对数量。

$n\leq 10^5,m\leq 2\times 10^5$

Solution

历经 9 个月，终于回来补这道题了。

一道非常优秀的分块入门题，值得分块初学者花时间思考，不值得一写。

——BFqwq

假设我们需要询问的是 $(l,r,x,y)$ 的答案，那么我们就可以把这个区间拆成中间是整块，两边是散块的结构。那么我们只需要分别考虑对应的贡献即可。

  1. 首先是左右散块之内的 事先预处理所有块内排序，并离散化，预处理出前缀权值、位置的点的数量，查询时直接暴力枚举所有权值，每个点直接查询前缀和即可。
  2. 其次是左散块对右散块的贡献 块内事先排序，查询时直接归并排序查询顺序对数。
  3. 左右散块对中间整块的贡献 直接暴力枚举散块内所有点，预处理时开个前缀和记录前缀块、权值点的数量，查询时直接用前缀和计算即可。
  4. 中间整块之间 显然整块之间的答案可以通过容斥解决，直接暴力枚举每个块，考虑先加上之前块（包含本块）对这个块的贡献（预处理后前缀和查询），显然此时肯定会导致重复，那么再减去这个块自己内部的重复，再减去剩下之前的块的重复即可。

至此，你就切掉了这个分块入门题，祝你好运！>.<

Code

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
/*
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%10+'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;
}