나무 커버 트 리 - 선분 나무 커버 밸 런 스 트 리

역할.
선분 트 리 의 역할 은 구간 수정 과 조회 이 고 균형 트 리 의 역할 은 k 대, k 의 순위, 전구, 후계 조회 이다.이 두 가 지 를 결합 하면 구간 수정 과 조회 가 가능 한 k 대, k 의 순위, 전구, 후계 의 데이터 구조: 나무 세트 트 리 - 선분 트 리 세트 균형 트 리 가 된다.
이루어지다
먼저 선분 나 무 를 만 들 고 모든 선분 나 무 는 왼쪽 경계 와 오른쪽 경 계 를 기록 하 는 것 외 에 균형 트 리 (물론 실제 적 으로 뿌리 노드 만 저장 해 야 한다) 를 저장 하여 이 구간 의 모든 수 에 대응 한다.구간 L ~ R 을 수정 할 때마다 L ~ R 을 포함 하 는 모든 선분 트 리 노드 의 밸 런 스 트 리 를 수정 해 야 한다.조작 은 사실 어 려 운 점 이 없습니다. 일반 선분 트 리 와 같이 블록 으로 나 누 어 처리 하면 됩 니 다. 효율 은 O (log 22 (n) 입 니 다.
그러나 검색 구간 k 가 크 면 일반 선분 트 리 처럼 2 점 으로 정 답 mid 를 매 거 한 다음 mid 의 순 위 를 조회 해 야 합 니 다. 순위 < = k 가 크 면 mid 를 늘 리 고 그렇지 않 으 면 mid 를 줄 여야 합 니 다.2 분 간격 이 t 라 고 가정 하면 효율 은 O (log 22 (n) 이 고 8727 ° log 2 (t) 이다.ps: 나무 커버 는 상수 가 많 으 니 조심 하 세 요.
템 플 릿
BZOJ 3196 의 경우 선분 트 리 트 랩 을 사용한다.세부 처리 에 주의 하 세 요.

#include
#include
#include
using namespace std;
const int maxn=50000,maxt=1700000,MAXINT=((1<<30)-1)*2+1;

int n,te,a[maxn+5];
//============================================================
struct Node
{
    Node *son[2];
    int val,fix,si,w;
    int cmp(int k) {if (k==val) return -1;if (kreturn 0; else return 1;}
    void Pushup() {si=son[0]->si+w+son[1]->si;}
};
typedef Node* P_node;
Node tem[maxt+5];
P_node null=tem,len=null;
P_node newNode(int k)
{
    len++;len->son[0]=len->son[1]=null;
    len->si=len->w=1;len->val=k;len->fix=rand();
    return len;
}
void Rotate(P_node &p,int d)
{
    P_node t=p->son[d^1];p->son[d^1]=t->son[d];t->son[d]=p;
    p->Pushup();t->Pushup();p=t;
}
void Insert(P_node &p,int k)
{
    if (p==null) {p=newNode(k);return;}
    int d=p->cmp(k);
    if (d==-1) p->w++; else
    {
        Insert(p->son[d],k);
        if (p->son[d]->fix>p->fix) Rotate(p,d^1);
    }
    p->Pushup();
}
void Delete(P_node &p,int k)
{
    if (p==null) return;
    int d=p->cmp(k);
    if (d==-1)
    {
        if (p->w>1) p->w--; else
        if (p->son[0]==null) p=p->son[1]; else
        if (p->son[1]==null) p=p->son[0]; else
        {
            int d;if (p->son[0]->fix>p->son[1]->fix) d=0; else d=1;
            Rotate(p,d);if (p==null) return;Delete(p->son[d],k);
        }
        if (p==null) return;
    } else Delete(p->son[d],k);
    p->Pushup();
}
int getrank(P_node p,int k) //      k，   k     
{
    if (p==null) return 1;
    int d=p->cmp(k);
    if (d==-1) return p->son[0]->si+1; else
    if (d==0) return getrank(p->son[0],k); else
    return getrank(p->son[1],k)+p->son[0]->si+p->w;
}
int getpre(P_node p,int k)
{
    if (p==null) return -MAXINT;
    int d=p->cmp(k);
    if (d==1) return max(getpre(p->son[1],k),p->val); else
    return getpre(p->son[0],k);
}
int getsuf(P_node p,int k)
{
    if (p==null) return MAXINT;
    int d=p->cmp(k);
    if (d==0) return min(getsuf(p->son[0],k),p->val); else
    return getsuf(p->son[1],k);
} //   Treap
//============================================================
struct SegmentTree
{
    int l[4*maxn+5],r[4*maxn+5];P_node ro[4*maxn+5]; //      
    void Build(int p,int L,int R)
    {
        l[p]=L;r[p]=R;ro[p]=null;
        if (L==R) return;
        int mid=L+(R-L>>1);
        Build(p<<1,L,mid);Build(p<<1|1,mid+1,R);
    }
    void Seg_Insert(int p,int L,int k)
    {
        if (Lreturn;
        if (l[p]<=L&&L<=r[p]) Insert(ro[p],k);
        //    L<=l[p]&&r[p]<=L，      L       k
        if (l[p]==r[p]) return;
        Seg_Insert(p<<1,L,k);Seg_Insert(p<<1|1,L,k);
    }
    void Seg_Delete(int p,int L,int k)
    {
        if (Lreturn;
        if (l[p]<=L&&L<=r[p]) Delete(ro[p],k);
        //  
        if (l[p]==r[p]) return;
        Seg_Delete(p<<1,L,k);Seg_Delete(p<<1|1,L,k);
    }
    int Seg_rank(int p,int L,int R,int k) //           -1，    
    {
        if (Rreturn 0;
        if (L<=l[p]&&r[p]<=R) return getrank(ro[p],k)-1;
        //          ，   L<=l[p]&&r[p]<=R
        return Seg_rank(p<<1,L,R,k)+Seg_rank(p<<1|1,L,R,k);
    }
    int Seg_kth(int l,int r,int k)
    {
        int L=0,R=1e8;
        while (L<=R) //  
        {
            int mid=L+(R-L>>1),rk=Seg_rank(1,l,r,mid)+1;
            if (rk<=k) L=mid+1; else R=mid-1;
        }
        return R;
    }
    int Seg_pre(int p,int L,int R,int k)
    {
        if (Rreturn -MAXINT;
        if (L<=l[p]&&r[p]<=R) return getpre(ro[p],k);
        return max(Seg_pre(p<<1,L,R,k),Seg_pre(p<<1|1,L,R,k));
    }
    int Seg_suf(int p,int L,int R,int k)
    {
        if (Rreturn MAXINT;
        if (L<=l[p]&&r[p]<=R) return getsuf(ro[p],k);
        return min(Seg_suf(p<<1,L,R,k),Seg_suf(p<<1|1,L,R,k));
    }
};
SegmentTree tr; //      
//============================================================
bool Eoln(char ch) {return ch==10||ch==13||ch==EOF;}
int readi(int &x)
{
    int tot=0,f=1;char ch=getchar(),lst=' ';
    while ('9''0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
void LNR(P_node ro)
{
    if (ro==null) return;
    LNR(ro->son[0]);for (int i=1;i<=ro->w;i++) printf("%d
",ro->val);LNR(ro->son[1]);
}
int main()
{
    freopen("STBST.in","r",stdin);
    freopen("STBST.out","w",stdout);
    readi(n);readi(te);tr.Build(1,1,n);
    for (int i=1;i<=n;i++) readi(a[i]),tr.Seg_Insert(1,i,a[i]);
    while (te--)
    {
        int td,x,y,z;readi(td);readi(x);readi(y);
        switch (td)
        {
            case 1:readi(z);printf("%d
",tr.Seg_rank(1,x,y,z)+1);break;
            case 2:readi(z);printf("%d
",tr.Seg_kth(x,y,z));break;
            case 3:tr.Seg_Delete(1,x,a[x]);tr.Seg_Insert(1,x,y);a[x]=y;break;
            case 4:readi(z);printf("%d
",tr.Seg_pre(1,x,y,z));break;
            case 5:readi(z);printf("%d
",tr.Seg_suf(1,x,y,z));break;
        }
    }
    return 0;
}