[TIOJ 1840][樹套樹] Coding Days

原題連結
動態區間第k小的作法基本上是這幾種：

1.BIT維護Persistent Segment Tree
時間是O(N(lgn)^2 + Q(lgn)^2)
空間也是O(N(lgn)^2 + Q(lgn)^2)
(if no 離散化 , lgn - > lgc)，這作法會有99%的機率吃MLE

2.Segment Tree 套 ranktree
時間是O(N(lgn)^2 + Q(lgn)^3)
空間是O(N)
(if no 離散化 , lgn->lgc)，這比較容易TLE

3.整體二分
時間是O((N+Qlgn)*lgn)
空間「可以」做到O(N+Q)
有興趣的同學可以戳戳這裡。

code是第二種作法，最後用了離散化成功加速。

第二種作法是三種裡面思維難度最低，debug難度也算低的，不過code量最大。

想看詳細題解的童鞋，可以去查clj大神的《持久化資料結構研究》，或是戳這裡。

#include<vector>
#include<algorithm>
#include<cassert>
#include<cstdio>
#include<new>
using namespace std;
const int maxn=50000+5;
const int maxQ=10000+5;
const int maxnode=2500000+5;
unsigned ran()
{
    static unsigned x=20160307;
    return x=x*0xdefaced+1;
}
struct Node
{
    static Node mem[maxnode];
    Node *lc,*rc;
    int val,pri,size;
    void pull() {size=(lc?lc->size:0)+1+(rc?rc->size:0);}
    Node() {}
    Node(int x) {val=x;pri=ran();size=1;lc=rc=NULL;}
}*root[maxn*8],Node::mem[maxnode],*pmem=Node::mem;
Node* merge(Node* a,Node* b)
{
    if(!a || !b) return a?a:b;
    if(a->pri > b->pri)
    {
        a->rc=merge(a->rc,b);
        a->pull();
        return a;
    }
    else
    {
        b->lc=merge(a,b->lc);
        b->pull();
        return b;
    }
}
void split(Node* t,int k,Node* &a,Node* &b)
{
    if(!t) {a=b=NULL;return;}
    else if(t->val<=k)
    {
        a=t;
        split(t->rc,k,a->rc,b);
        a->pull();
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        b->pull();
    }
}
int a[maxn];
void buildtree(int id,int L,int R)
{
    root[id]=NULL;
    if(L==R) {root[id]=merge(root[id],new (pmem++) Node(a[L]));return;}
    int M=L+(R-L)/2;
    buildtree(id*2,L,M);
    buildtree(id*2+1,M+1,R);

    vector<int> tmp;
    for(int i=L;i<=R;i++) tmp.push_back(a[i]);
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<tmp.size();i++) root[id]=merge(root[id],new (pmem++) Node(tmp[i]));
    vector<int> ().swap(tmp);
    
}
void split_size(Node* t,int k,Node* &a,Node* &b)
{
    if(!t) {a=b=NULL;return;}
    else if((t->lc?t->lc->size:0)+1<=k)
    {
        a=t;
        split_size(t->rc,k-(t->lc?t->lc->size:0)-1,a->rc,b);
        a->pull();
    }
    else
    {
        b=t;
        split_size(t->lc,k,a,b->lc);
        b->pull();
    }
}
void pull(int id,int mv,int initmv)
{
    Node *t1,*t2,*goodbye,*t3;
    split(root[id],initmv-1,t1,t2);
    split(t2,initmv,t2,t3);
    split_size(t2,1,goodbye,t2);
    root[id]=merge(t1,merge(t2,t3));

    split(root[id],mv,t1,t2);
    root[id]=merge(t1,merge(new (pmem++) Node(mv),t2));
}
void modify(int id,int L,int R,int mx,int mv)
{
    if(L==R)
    {
        root[id]=NULL;
        root[id]=merge(root[id],new (pmem++) Node(mv));
        return;
    }
    int M=L+(R-L)/2;
    if(mx<=M) modify(id*2,L,M,mx,mv);
    else modify(id*2+1,M+1,R,mx,mv);
    pull(id,mv,a[mx]);
}
int Rank;
void query(int id,int L,int R,int qL,int qR,int qv)
{
    if(qL<= L && R<=qR)
    {
        Node *t1,*t2;
        split(root[id],qv,t1,t2);
        Rank+=t1?t1->size:0;
        root[id]=merge(t1,t2);
        return;
    }
    int M=L+(R-L)/2;
    if(qL<=M) query(id*2,L,M,qL,qR,qv);
    if(qR >M) query(id*2+1,M+1,R,qL,qR,qv);
}
vector<int> disc;
struct Query
{
    int type,L,R,k;
}qu[maxQ];
int main()
{
    int T,N,Q;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&Q);
        pmem=Node::mem;
        for(int i=1;i<=N;i++) {scanf("%d",a+i);disc.push_back(a[i]);}
        for(int i=0;i<Q;i++)
        {
            scanf("%d",&qu[i].type);
            if(qu[i].type==2) {scanf("%d%d",&qu[i].L,&qu[i].k); disc.push_back(qu[i].k);}
            else if(qu[i].type==1) {scanf("%d%d%d",&qu[i].L,&qu[i].R,&qu[i].k); disc.push_back(qu[i].k);}
            else {scanf("%d%d",&qu[i].L,&qu[i].k);}
        }
        sort(disc.begin(),disc.end());
        disc.resize(unique(disc.begin(),disc.end())-disc.begin());
        
        buildtree(1,1,N);
        for(int i=0;i<Q;i++)
        {
            if(qu[i].type==2)
            {
                modify(1,1,N,qu[i].L,qu[i].k);
                a[qu[i].L]=qu[i].k;
            }
            else if(qu[i].type==1)
            {
                int bL=0,bR=disc.size()-1;
                while(bL!=bR)
                {
                    int M=bL+(bR-bL)/2;
                    Rank=0;
                    query(1,1,N,qu[i].L,qu[i].R,disc[M]);
                    if(Rank>=qu[i].k) bR=M;
                    else bL=M+1;
                }
                printf("%d\n",disc[bL]);
            }
            else printf("7122\n");
        }
    }
}