[POJ 2104][Persistent Segment Tree] K-th Number

原題連結
本題作為經典的資料結構題，解法有非常多種。
就我能力上可作的就有持久化線段樹，線段樹套平衡樹。
這些解法各自的優點和缺點都不同。
想看題解和有興趣研究的可以去google clj大神撰寫的《持久化數據結構研究》，裡面有詳盡的解說和延伸。

說說我寫這題時遇到的癥結點。
這題的指標型持久化線段樹我寫的還算是不錯了，沒有出多大bug，只是有好長一段時間在糾結到底要離散化還是copy on write呢？

離散化的優點是直覺好寫，缺點是offline；copy on write的優點是配合持久化線段樹完全online，缺點是比較難debug。

最後，我兩個版本都有做出來，不過我要講的重點其實在讓我兩個都寫的原因：這兩個寫法都會TLE。

又過了不知道多久，我突然想到有個優化叫做placement new，在POJ上幫過我不少次，加上去之後就成功AC了，2246ms。

總而言之，這題給我最大的經驗就是：在POJ上能不用new就別用new，用了記得placement new......
我能想到最快的寫法大概是用陣列型持久化線段樹+離散化
(O(nlogn)和O(nlogc)還是有段差距的......)

註：code裡註解掉的部份是離散化的作法

#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
const int maxn=100000+5;
const int maxc=1000000000+5;
const int maxnode=4000000+5;
const int INF=(1<<30);
struct Node
{
    static Node mem[maxnode];
    Node *lc,*rc;
    int size;
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0);}
    Node() {size=0;lc=rc=NULL;}
}*root[maxn],Node::mem[maxnode],*pmem=&Node::mem[0];
void modify(Node* last,Node*& now,int L,int R,int mx,int mv)
{
    if(last) now=new (pmem++) Node(*last);
    else now=new (pmem++) Node();
    if(L==R) {now->size++;return;}
    int M=L+(R-L)/2;
    if(mx<=M) modify(last?last->lc:0,now->lc,L,M,mx,mv);
    else modify(last?last->rc:0,now->rc,M+1,R,mx,mv);
    now->pull();
}
void query(Node* tL,Node* tR,int L,int R,int kth,int& qv)
{
    if(L==R) {qv=L;return;}
    int M=L+(R-L)/2;
    int tmp=(tR->lc?(tR->lc->size - ((tL && tL->lc)?tL->lc->size:0)):-1);
    if(tmp>=0 && tmp>=kth) query(tL?tL->lc:0,tR->lc,L,M,kth,qv);
    else query(tL?tL->rc:0,tR->rc,M+1,R,kth-(tmp>=0?tmp:0),qv);
}
vector<int> disc;
int a[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        disc.push_back(a[i]);
    }
    sort(disc.begin(),disc.end());
    disc.resize(unique(disc.begin(),disc.end())-disc.begin());
    for(int i=1;i<=n;i++)
    {
//        a[i]=lower_bound(disc.begin(),disc.end(),a[i])-disc.begin();
//        modify(root[i-1],root[i],0,disc.size(),a[i],1);
        modify(root[i-1],root[i],-maxc,maxc,a[i],1);
    }
    for(int i=0,L,R,k,ans;i<m;i++)
    {
        scanf("%d%d%d",&L,&R,&k);
//        query(root[L-1],root[R],0,disc.size(),k,ans);
//        printf("%d\n",disc[ans]);
        query(root[L-1],root[R],-maxc,maxc,k,ans);
        printf("%d\n",ans);
    }
}