CF1404C Fixed Point Removal 做题记录

给定一个含有 $n$ 个正整数的序列 $a$ ，对于一次操作，你可以任选一个位置 $i$ 且满足 $a_i=i$，那么就可以移除这个元素，并将后面所有的元素向前移动一位。

对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下，最多可以进行几次操作。

$n,q \leq 3\times 10^5$。

首先不难想到让 $a_i\to i-a_i$，这样问题就转变为每次操作可以删去 $a_i=0$ 的 $a_i$ 并且让 $a_{[i+1,n]}$ 减去 $1$。

不难发现 $a_i$ 能被删掉当且仅当 $a_{[1,i-1]}$ 中有至少 $a_i$ 个能被删掉，因为删掉 $a_i$ 的这次操作可以插到删掉 $a_i$ 个数之后。

发现询问相当于选一个区间 $[l,r]$ 里的 $a_i$ 出来算答案。在线不太好做，考虑离线。

把询问离线到序列上，把询问按 $r$ 从小到大排序，处理到第 $i$ 个询问的时候把把 $a_{[1,r_i]}$ 都加入某个可以维护从 $i$ 开始操作的答案 $f_i$ 的数据结构里即可。

考虑怎么维护 $f_i$，不难发现它具有单调性，即满足 $f_i\ge f_{i+1}$，那么设 $k$ 满足 $f_1\ge f_2\ge f_3\ge\dots\ge f_k\ge a_i > f_{k+1}\ge\dots\ge f_n$，则 $a_i$ 对 $f_{[1,k]}$ 都有 $1$ 的贡献。不难发现这个可以用树状数组维护，由于每次都是 $[1,x]$ 这样的区间，所以干脆直接维护每个位置减了多少次，然后找 $k$ 就可以用树状数组上二分来维护。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=300005;

struct node
{
	int l,r,id;
}que[S];

int n,m;
int a[S],c[S];
int ans[S];

inline void addt(int pos,int x)
{
	for(int i=pos;i<=n;i+=i&-i) c[i]+=x;
}

inline int quet(int pos)
{
	int res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=c[i];
	return res;
}

inline int fndk(int k)
{
	int pos=0,val=0;
	for(int i=20;i>=0;i--)
	{
		int nxt=pos+(1<<i);
		if(nxt<=n&&val+c[nxt]<=k) val+=c[nxt],pos=nxt;
	}
	return pos;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=i-a[i];
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		que[i].l=x+1,que[i].r=n-y;
		que[i].id=i;
	}
	sort(que+1,que+m+1,[&](node x,node y){return x.r<y.r;});
	int j=1;
	for(int i=1;i<=m;i++)
	{
		for(;j<=n&&j<=que[i].r;j++)
		{
			if(a[j]<0)
			{
				addt(1,1);
				continue;
			}
			int k=min(fndk(j-1-a[j]),j);
			addt(k+1,1);
		}
		ans[que[i].id]=j-1-quet(que[i].l);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]); 
	return 0;
}