【GDKOI 2021提高组DAY2】群岛

一道需要动动脑的题，需要把题目转换一下，然后才好维护。

Description

题解

对于$a_i<i$ 的情况，我们发现$i$是一定能到达$a[i]$的。
那么说，我们假设把所有的$[a_i,i]$当做线段，那么我们每次的查询就是找与$[i,n]$ 相交最前的左端点。
用线段树维护，支持区间加以及找前缀区间最后一个0的位置。
特别的，为了避免把$[x,y],[y+1,z]$两个区间视为相交，我们塞进去的时候塞的是左闭右开区间。

Code

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+5;
struct Segment{
	int mn,tag;
}T[N<<2];
int n,ans;
int a[N];
bool bj;
void pushdown(int x){
	int p=x<<1,q=x<<1|1;
	T[p].mn+=T[x].tag;T[q].mn+=T[x].tag;
	T[p].tag+=T[x].tag;T[q].tag+=T[x].tag;
	T[x].tag=0;
	return;
}
void update(int x){
	T[x].mn=min(T[x<<1].mn,T[x<<1|1].mn);
	return;
}
void change(int x,int l,int r,int st,int en,int val){
	if (st>en) return;
	if (l==st&&r==en){
		T[x].mn+=val;
		T[x].tag+=val;
		return; 
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (en<=mid) change(x<<1,l,mid,st,en,val);
	else if (st>mid) change(x<<1|1,mid+1,r,st,en,val);
	else change(x<<1,l,mid,st,mid,val),change(x<<1|1,mid+1,r,mid+1,en,val);
	update(x);
	return;
}
void query(int x,int l,int r,int p){
	if (l>p||bj) return;
	if (T[x].mn!=0) return; 
	if (l==r){
		ans=l;
		bj=1;
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (T[x<<1|1].mn==0) query(x<<1|1,mid+1,r,p);
	query(x<<1,l,mid,p);
	return;
}
int main(){
	freopen("island.in","r",stdin);
	freopen("island.out","w",stdout);
	int _;
	scanf("%d%d",&n,&_);
	for (int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		change(1,0,n,a[i],i-1,1);
	}
	int co,x,y;
	while (_--){
		scanf("%d%d",&co,&x);
		if (co==1){
			scanf("%d",&y);
			change(1,0,n,a[x],x-1,-1);a[x]=y;
			change(1,0,n,a[x],x-1,1);
		}
		else bj=0,query(1,0,n,x-1),printf("%d\n",ans+1);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}