题解 P4422 (线段树二分)[20181103模拟T2] [COCI2017-2018#1] Deda

· · 题解

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

「年龄大于等于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),但是我太弱的暂时写不起来.又想到有一题和这题有些类似(线段树二分)推荐大家也写一写.