自动搬运

查看原文

来自洛谷，原作者为

	Utsuji_risshū **

搬运于2025-08-24 22:00:00，当前版本为作者最后更新于2018-11-03 14:31:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没看懂楼下「竞赛树」什么鬼,这题本质不就线段树二分么。。

「年龄大于等于$B$且在第$Y$站（包含第$Y$站）以前下车的最年轻的小孩是多大？」这种询问就是求$[B,N]$区间里值小于$Y$的最小位置,那么就可以以年龄$[1,N]$为下标维护其区间最小值(这里的值指的是$i$岁的人下车位置),添加操作就是让$i$位置值为站点值,查询时就找到$[B,N]$区间,对这个完整区间看其最小值是否比询问值小,小就说明这个岁数区间里有下车点比查询值小的,就顺着找到这个区间最小的叶子结点.可能说的不太清楚,那么,看代码。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000+7,INF=0x3f7f3f7f;
inline int _min(int a,int b){return a<b?a:b;}
inline int read(){
	char c;int f=0,x=0;while(!isdigit(c=getchar()))if(c==45)f=1;
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return f?-x:x;
}
int minv[N<<2];
char s[3];
int n,q,x,k,ans,qr,ql;
#define l i<<1
#define r i<<1|1
void Update(int i,int L,int R){
	if(L==R){minv[i]=k;return;}
	int mid=L+R>>1;x<=mid?Update(l,L,mid):Update(r,mid+1,R);
	minv[i]=_min(minv[l],minv[r]);
}//维护最小站点位置
int Find(int i,int L,int R){
	if(minv[i]>k)return INF;
	else if(L==R) return L; 
	int mid=L+R>>1;return minv[l]<=k?Find(l,L,mid):Find(r,mid+1,R);
}//这里就是如果ql,qr覆盖了当前区间就在这区间里找满足要求最小岁数
void Query(int i,int L,int R){
	if(ql<=L&&qr>=R){ans=Find(i,L,R);return;}
	int mid=L+R>>1;
	if(ql<=mid){Query(l,L,mid);if(ans!=INF)return;}//小细节,年龄小的已经找到就不用找右边了.
	if(qr>mid)Query(r,mid+1,R);
}
#undef l
#undef r
int main(){
	qr=n=read(),q=read();memset(minv,INF,sizeof minv);//注意清零,想想为什么
	while(q--){
		scanf("%s",s);
		if(s[0]=='M')k=read(),x=read(),Update(1,1,n);
		else k=read(),ql=read(),ans=INF,Query(1,1,n),printf("%d\n",ans==INF?-1:ans);
	}
	return 0;
}

啊顺便吐槽这小孩能活200000岁怕不是神仙

Update: 对了这题也可以套三维偏序板子题来写啊,线段树$O(nlogn)$,三维偏序$O(nlog^2n)$,但是我太弱的暂时写不起来.又想到有一题和这题有些类似(线段树二分)推荐大家也写一写.