P6774 [NOI2020] 时代的眼泪（分块）

前言

看到题目名：别骂了别骂了。

一道很中规中矩的YNOI吧。
卡在整块对整块的贡献上了。
这也确实算是本题最不好做的部分了。

前置知识：Yuno loves sqrt technology I

解析

区间逆序对加强版？很难不想到两道 YLST。
然而多了两维限制，二离似乎没啥前途了。
考虑分块在线做法。

设询问区间为 $[l,r]$，值域区间为 $[bot,top]$。
还是老套路，把贡献分成散块内部、整块内部、散块对散块、整块对整块、散块对整块五部分，以及在同一块内的情况。

散块内部：.…这咋做啊这时难免会有上树状数组的冲动。但是稍加思考可以发现，每个块内的值只有 $O(\sqrt{n})$ 个，所以不妨直接预处理出每个数在块内的排名以及每个块内排名的前缀和，然后直接差分查一查就行了。
散块对散块：老套路，归并排序即可。
整块对整块：一个比较直观的思路是容斥一下，求出 $[1,top]$ 的答案，再减去 $[1,bot-1]$ 的答案，再减掉 $[1,bot-1]$ 的数对 $[bot,top]$ 产生的贡献。
最后减掉的贡献用前缀和搞一搞容易解决，那么如何求出整块之间值域形如 $[1,x]$ 的答案呢？（我就卡在这里勒）
答案形如 ${\sum }_b{\sum }_{a<b}ans(a,b,1,x)$，考虑转化为对所有 $b$ 求出所有 ${\sum }_{a<b}ans(a,b,1,x)$ 然后求和。
那么这个的形式似乎就非常好搞了，就是枚举 $b$ 块内所有处于 $[1,x]$ 的元素再在前面查顺序对那么预处理一下就行了。
散块对整块：枚举散块元素，前缀和即可。

同一块内：使用和散块内部类似的方法前缀和即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")

inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
bool mem1;

const int N=1e5+100;
const int inf=1e9+100;
const bool Flag=0;
const int mod=1e9+7;

const int B=405;//number of block
const int S=405;//size of block

int n,m;
int pos[N],a[N],b[N],rk[N];
int st[B],ed[B],bel[N],w,len[B];
int sum[B][N],pre[N][S],val[B][S],pl[B][S];
int f[B][B][S],s[B][S][S];
int lb[B][N];
int u[S],v[S],n1,n2;
void init(){
  w=sqrt(n);
  for(int i=1;i<=n;i++) bel[i]=(i+w-1)/w;
  for(int k=1;k<=bel[n];k++){
    st[k]=(k-1)*w+1;
    ed[k]=min(n,k*w);
    len[k]=ed[k]-st[k]+1;
    sort(b+st[k],b+ed[k]+1);
    for(int i=st[k];i<=ed[k];i++){
      int suf=i==ed[k]?n+1:b[i+1];
      for(int j=b[i];j<suf;j++){
	lb[k][j]=i-st[k]+1;
      }
    }
    for(int i=st[k];i<=ed[k];i++) rk[pos[b[i]]]=i-st[k]+1;
    for(int i=1;i<=n;i++) sum[k][i]=sum[k-1][i];
    for(int i=st[k];i<=ed[k];i++){
      sum[k][a[i]]++;
      if(i!=st[k]){
	for(int j=1;j<=len[k];j++) pre[i][j]=pre[i-1][j];
      }
      pre[i][rk[i]]++;
      pl[k][rk[i]]=i;
      val[k][rk[i]]=a[i];
    }    
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=len[bel[i]];j++) pre[i][j]+=pre[i][j-1];
  }
  for(int k=1;k<=bel[n];k++){
    for(int a=1;a<=len[k];a++){
      for(int b=a+1;b<=len[k];b++){
	int p=pl[k][b];
	s[k][a][b]=s[k][a][b-1]+(pre[p][b-1]-pre[p][a-1]);
      }
    }
  }
  for(int k=1;k<=bel[n];k++){
    for(int i=1;i<=n;i++) sum[k][i]+=sum[k][i-1];
  }
  for(int i=1;i<=bel[n];i++){
    for(int j=1;j<i;j++){
      for(int k=1;k<=len[i];k++){
	f[i][j][k]=sum[j][b[st[i]+k-1]]+f[i][j][k-1];
      }
    }
  }
  return;
}
void work(int l,int r,int bot,int top){
  if(l>r||bot>top){
    puts("0");
    return;
  }
  int x=bel[l],y=bel[r];
  if(x==y){
    ll res(0);
    for(int i=l;i<=r;i++){
      if(a[i]>=bot&&a[i]<=top){
	res+=(pre[i][rk[i]-1]-(l==st[x]?0:pre[l-1][rk[i]-1]))-(pre[i][lb[x][bot-1]]-(l==st[x]?0:pre[l-1][lb[x][bot-1]]));
      }
    }
    printf("%lld\n",res);
    return;
  }
  ll res(0);
  for(int i=x+1;i<y;i++){
    res+=s[i][lb[i][bot-1]+1][lb[i][top]];
  }
  for(int i=l;i<=ed[x];i++){
    if(a[i]>=bot&&a[i]<=top){
      res+=(pre[i][rk[i]-1]-(l==st[x]?0:pre[l-1][rk[i]-1]))-(pre[i][lb[x][bot-1]]-(l==st[x]?0:pre[l-1][lb[x][bot-1]]));
    }
  }
  for(int i=st[y];i<=r;i++){
    if(a[i]>=bot&&a[i]<=top){
      res+=pre[i][rk[i]-1]-pre[i][lb[y][bot-1]];
    }
  }
  int pp=st[x],cnt(0);
  for(int i=st[y];i<=ed[y];i++){
    while(pp<=ed[x]&&b[pp]<b[i]){
      cnt+=(pos[b[pp]]>=l&&b[pp]>=bot&&b[pp]<=top);
      ++pp;
    }
    if(pos[b[i]]<=r&&b[i]>=bot&&b[i]<=top) res+=cnt;
  }
  for(int i=l;i<=ed[x];i++){
    if(a[i]>=bot&&a[i]<=top) res+=(sum[y-1][top]-sum[x][top])-(sum[y-1][a[i]]-sum[x][a[i]]);
  }
  for(int i=st[y];i<=r;i++){
    if(a[i]>=bot&&a[i]<=top) res+=(sum[y-1][a[i]]-sum[x][a[i]])-(sum[y-1][bot-1]-sum[x][bot-1]);
  }
  for(int k=x+1;k<y;k++){
    if(lb[k][bot-1]<lb[k][top]){
      res+=(f[k][k-1][lb[k][top]]-f[k][x][lb[k][top]])-(f[k][k-1][lb[k][bot-1]]-f[k][x][lb[k][bot-1]]);
      res-=1ll*(lb[k][top]-lb[k][bot-1])*(sum[k-1][bot-1]-sum[x][bot-1]);
    }
  }
  printf("%lld\n",res);
}

bool mem2;
signed main(){
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  debug("mem=%.4lf\n",abs(&mem2-&mem1)/1024./1024);
  n=read();m=read();
  for(int i=1;i<=n;i++){
    b[i]=a[i]=read();pos[a[i]]=i;
  }
  init();
  for(int i=1;i<=m;i++){
    int l=read(),r=read(),bot=read(),top=read();
    work(l,r,bot,top);
  }
  return 0;
}

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151