ZJ Day7

平衡树：

一种特殊的二叉排序树，尽量减少了每个节点的左右子树高度差保证复杂度不会退化。
FHQ Treap:
基于随机数的性质来保证几点的排布不堆积在某个子树。

#include<bits/stdc++.h>
using namespace std;
int n,tot,rt,ls[100010],rs[100010],pri[100010],key[100010],siz[100010];
mt19937 rng(time(0));
void update(int q)
{
    siz[q]=siz[ls[q]]+siz[rs[q]]+1;
    return;
}
int merge(int l,int r) //l<=r
{
    if(l==0||r==0) 
    {
        return l+r;
    }
    if(pri[l]>pri[r]) 
    {
        rs[l]=merge(rs[l],r);
        update(l);
        return l;
    }
    else 
    {
        ls[r]=merge(l,ls[r]);
        update(r);
        return r;
    }
}
void split(int q,int k,int &l,int &r)
{
    if(q==0)
    {
        l=r=0;
        return;
    }
    if(key[q]<=k)
    {
        l=q;
        split(rs[q],k,rs[q],r);
    }
    else
    {
        r=q;
        split(ls[q],k,l,ls[q]);
    }
    update(q);
    return;
}
void insert(int x)
{
    tot++;
    ls[tot]=rs[tot]=0;
    pri[tot]=rng();
    key[tot]=x;
    siz[tot]=1;
    int l,r;
    split(rt,x,l,r);
    rt=merge(merge(l,tot),r);
    return;
}
void remove(int x)
{
    int l,r,m;
    split(rt,x-1,l,r);
    split(r,x,m,r);
    rt=merge(l,merge(merge(ls[m],rs[m]),r));
    return;
}
int getrank(int x)
{
    int l,r,res;
    split(rt,x-1,l,r);
    res=siz[l]+1;
    rt=merge(l,r);
    return res;
}
int kth(int q,int k)
{
    if(k==siz[ls[q]]+1) return q;
    else if(k<siz[ls[q]]+1) return kth(ls[q],k);
    return kth(rs[q],k-siz[ls[q]]-1);
}
int precursor(int x)
{
    int l,r,res;
    split(rt,x-1,l,r);
    res=key[kth(l,siz[l])];
    rt=merge(l,r);
    return res;
}
int successor(int x)
{
    int l,r,res;
    split(rt,x,l,r);
    res=key[kth(r,1)];
    rt=merge(l,r);
    return res;
}
int main()
{
    cin>>n;
    int op,x;
    while(n--)
    {
        cin>>op>>x;
        if(op==1)
        {
            insert(x);
        }
        else if(op==2)
        {
            remove(x);
        }
        else if(op==3)
        {
            cout<<getrank(x)<<endl;
        }
        else if(op==4)
        {
            cout<<key[kth(rt,x)]<<endl;
        }
        else if(op==5)
        {
            cout<<precursor(x)<<endl;
        }
        else
        {
            cout<<successor(x)<<endl;
        }
    }
    return 0;
}

千山鸟飞绝：

对于每个坐标点维护一个平衡树，存储历史最大，次大值，树的大小的历史最大值，使用懒标记在插入或删除时上传数据，更新答案即可。

抢鲜草：

区间dp，增加一维0/1，记录完成时在左或右顶点，即可转移。