题解：AT_abc389_f [ABC389F] Rated Range
liuhongyang123
·
·
题解
解题方法
一道分块板子。
我们可以看到数值的范围很小，所以考虑分块。
$a$ 数组代表小块，也就是 $a[x]$ 代表数值 $x$ 无法在大块中体现的部分。
可能有点绕，大家可结合代码理解。
说完数组定义后讲一下方法。
对于每一对 $l$ 和 $r$，我们二分把其可以影响到的数值上限和下限求出来，对应把这段范围在块上面加其贡献，也就是 $+1$。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define qk(x) ((x-1)/B+1)
//qk(x) 求出数值x在哪一个块当中
using namespace std;
const int N=6e5,B=sqrt(N)+1,MAXN=1e7+10;
//N 数值范围，B 块的个数与大小
int n,m,p,q,len,len1,a[MAXN],b[MAXN];
//a[x]+b[qk(x)] 就是当前x经过前面评分变化后的值
int ef(int x){ //二分求上限下限
if(a[N]+b[qk(N)]<x) return N+1;
int l=1,r=N;
while(l<r){
int mid=(l+r)/2;
if(a[mid]+b[qk(mid)]<x) l=mid+1;
else r=mid;
}
return l;
}
signed main(){
cin>>n;
for(int i=1;i<=N;i++) a[i]=i;
for(int i=1;i<=n;i++) {
int l,r;
cin>>l>>r;
int l1=ef(l),r1=ef(r+1)-1,kl=qk(l1),kr=qk(r1);
if(kl==kr) for(int i=l1;i<=r1;i++) a[i]++;//在同一块中，小块直接加。
else{
//若上限下限不在同一块中
for(int i=l1;i<=kl*B;i++) a[i]++;//把前面多出来的算上
for(int i=kr*B-B+1;i<=r1;i++) a[i]++;//后面多的也算上
for(int i=kl+1;i<=kr-1;i++) b[i]++;//中间整块整块的，直接大块中加
//如果看不懂这里，建议复习一下分块模板
}
}
cin>>m;
for(int i=1,x;i<=m;i++){
cin>>x;
cout<<a[x]+b[qk(x)]<<endl;//单独贡献+同块贡献
}
return 0;
}
```
### 完结散花