题解 CF1404C【Fixed Point Removal】
whiteqwq
·
·
题解
CF1404C Fixed Point Removal解题报告：
更好的阅读体验
题意
给定长为 n 的序列 a，一次操作可以删除一个满足 a_i=i 的位置 i，同时之后的数向前移动一位。
## 分析
套路题。
观察数据范围可知算法复杂度差不多是单 $\log$，根据套路，我们将询问挂在右端点上，并从左往右扫，用数据结构维护左端点为 $i$ 时的答案。
具体地，我们记 $v_i$ 为可以删除的区间左端点为 $i$ 时，有多少个点无法删除，可以发现加入一个点后我们只需要计算其对一段后缀的贡献。
扫描到 $i$ 时，若 $i<a_i$，不难发现其一定无法删除，于是直接全局加一。否则，我们二分一个位置使得其前面已经有 $a_i$ 个无法删除的位置，将这个位置对应的后缀与 $i+1$ 对应的后缀取并并直接更新。
这种操作用树状数组可以轻松维护，二分的时候在树状数组上二分就可以了，时间复杂度 $O(n\log n)$。
## 代码
```
#include<stdio.h>
#include<vector>
#define lowbit(x) x&-x
using namespace std;
const int maxn=300005;
int n,m;
int a[maxn],ans[maxn],t[maxn];
vector< pair<int,int> >v[maxn];
void update(int x,int v){
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=v;
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=t[i];
return res;
}
int getkth(int k){
int res=0;
for(int i=18;i>=0;i--)
if(res+(1<<i)<=n&&k>t[res+(1<<i)])
k-=t[res+(1<<i)],res+=(1<<i);
return res+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
x++,y=n-y;
if(x<=y)
v[y].push_back(make_pair(x,i));
}
for(int i=1,tot=0;i<=n;i++){
if(i-a[i]>=0){
tot++;
int pos=getkth(a[i]);
if(pos<=i)
update(pos,1);
else update(i+1,1);
}
for(int j=0;j<v[i].size();j++)
ans[v[i][j].second]=tot-query(v[i][j].first);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
```
本场全部题解可见：[Codeforces Round 1404考试总结](https://zybuluo.com/xiaoziyao/note/1812279)