CF1404C Fixed Point Removal解题报告

解题报告

CF1404C Fixed Point Removal解题报告：

更好的阅读体验

题意

给定长为 $n$ 的序列 $a$ ，一次操作可以删除一个满足 $a_i=i$ 的位置 $i$ ，同时之后的数向前移动一位。
$q$ 次询问，每次给定 $x,y$ ，求不能删去前 $x$ 个元素与后 $y$ 个元素的情况下最多能删除多少元素。（$1\leqslant n\leqslant 3\times 10^5$ ）

分析

套路题。

观察数据范围可知算法复杂度差不多是单 $\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;
}