luogu4422 [COCI2017-2018#1] Deda[线段树二分]

这题我一年前的模拟赛考场还切过，现在就不会了。。好菜啊。

显然直接线段树拆成$log n$个区间，然后每个区间在进行线段树二分即可。

UPD：复杂度分析。貌似是$O(nlog n)$的/yiw。每个区间线段树二分，左儿子min小于查询的x就走左儿子，右儿子min小于x就走右儿子，否则就不走，直到找到最早的一个区间，后面的区间直接返回不找力~。所以找出log个区间，只有一个区间进行二分，总的是两倍log，所以还是单log级别的。

这是一年前的code。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=200000+7,INF=0x3f7f3f7f;
 5 inline int _min(int a,int b){return a<b?a:b;}
 6 inline int read(){
 7     char c;int f=0,x=0;while(!isdigit(c=getchar()))if(c==45)f=1;
 8     while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return f?-x:x;
 9 }
10 int minv[N<<2];
11 char s[3];
12 int n,q,x,k,ans,qr,ql;
13 #define l i<<1
14 #define r i<<1|1
15 void Update(int i,int L,int R){
16     if(L==R){minv[i]=k;return;}
17     int mid=L+R>>1;x<=mid?Update(l,L,mid):Update(r,mid+1,R);
18     minv[i]=_min(minv[l],minv[r]);
19 }//维护最小站点位置
20 int Find(int i,int L,int R){
21     if(minv[i]>k)return INF;
22     else if(L==R) return L; 
23     int mid=L+R>>1;return minv[l]<=k?Find(l,L,mid):Find(r,mid+1,R);
24 }//这里就是如果ql,qr覆盖了当前区间就在这区间里找满足要求最小岁数
25 void Query(int i,int L,int R){
26     if(ql<=L&&qr>=R){ans=Find(i,L,R);return;}
27     int mid=L+R>>1;
28     if(ql<=mid){Query(l,L,mid);if(ans!=INF)return;}//小细节,年龄小的已经找到就不用找右边了.
29     if(qr>mid)Query(r,mid+1,R);
30 }
31 #undef l
32 #undef r
33 int main(){
34     qr=n=read(),q=read();memset(minv,INF,sizeof minv);//注意清零,想想为什么
35     while(q--){
36         scanf("%s",s);
37         if(s[0]=='M')k=read(),x=read(),Update(1,1,n);
38         else k=read(),ql=read(),ans=INF,Query(1,1,n),printf("%d
",ans==INF?-1:ans);
39     }
40     return 0;
41 }

View Code

还有单log做法，是hkk教的。。首先对于权值从小到大排序，把每种权值建一棵树，树的下标是序列下标，（显然这个是一个可持久化线段树，注意这样一个以权值建立线段树的方法在想不出的时候可以往这个上想想！），然后对于查询区间小于x的，直接在主席树上找1~x-1这些树上（实际是前缀和）最早的[L,R]有值处，这个的做法和复杂度分析也同上。