1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#define rg register
#define rep(i,x,y) for(rg int i=(x);i<=(y);++i)
#define per(i,x,y) for(rg int i=(x);i>=(y);--i)
using namespace std;
const int N=1e6+10,alp=26,P=N<<1;
inline bool vaild(char c){return c>='a'&&c<='z';}
inline char gc(){char c=getchar();while(!vaild(c))c=getchar();return c;}
inline void up(int&x,int y){if(y>x)x=y;}
int s[N],n;
const int TP=N<<2;
#define ls (k<<1)
#define rs (k<<1|1)
struct SGT{
    int son[TP][2],mark[TP];
    void maintain(int k){
        up(mark[ls],mark[k]);up(mark[rs],mark[k]);
    }
    void modify_mark(int ll,int rr,int v,int k,int l,int r){
        if(ll<=l&&r<=rr){up(mark[k],v);return;}
        int m=(l+r)>>1;
        if(ll<=m)modify_mark(ll,rr,v,ls,l,m);
        if(rr>m)modify_mark(ll,rr,v,rs,m+1,r);
    }
    int query(int p,int k,int l,int r){
        if(l==r)return mark[k];
        maintain(k);
        int m=(l+r)>>1;
        if(p<=m)return query(p,ls,l,m);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX