[ONTAK 2010 Day1][Treap][Disjoint Set][Heuristic Merge] Peaks

原題連結
這道題的思路其實不難，只是同時考驗對於資料結構的信心和穩定度，寫起來code量略大，還是比較麻煩的。



查詢時有「權重不超過x」的約束條件，讓我們很自然(依據經驗)聯想到離線方法：將所有詢問按照x排序，只要查詢時x遞增，可以走的邊在某個時間點之後就一定保持可以走，這樣子我們成功的解決了這個約束。

再來是「v能走到」的這個條件。我們可以用并查集維護連通性，就不多說了。

最後是「第k大」的部份。顯然我們對於每條邊的加入有需要合併兩棵Treap的時候，一樣不多說，就是啟發式合併(如果有更好的科技請賜教<(_ _)>)。只要記得把size域維護好，第k大的查詢就按照一般的ranktree那樣做就可以了。

時間複雜度: O(n(lgn)^2 + M + Q + nlogn),最後一個logn是並查集
總而言之，思路簡單，實做要細心。
不要像我一樣，唯一的兩個bug是maxnode沒開夠，還有亂數函數竟然忘了加static導致樹退化成一條鏈......

#include<new>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
const int maxq=500000+5;
const int maxnode=1000000+5;
unsigned ran()
{
    static unsigned x=20150306;
    return x=x*0xdefaced+1;
}
struct Node
{
    static Node mem[maxnode];
    Node *lc,*rc;
    int size,val,pri;
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0)+1;}
    Node() {}
    Node(int v) {pri=ran();size=1;val=v;lc=rc=NULL;}
}*root[maxn],Node::mem[maxnode],*pmem=Node::mem;
struct Edge
{
    int from,to,w;
    bool operator < (const Edge& rhs) const {return w<rhs.w;}
};
vector<Edge> edges;
struct Query
{
    int v,x,k,id;
    bool operator < (const Query& rhs) const {return x<rhs.x;}
};
vector<Query> qu;
int fa[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
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();
    }
}
Node* merge(Node* a,Node* b)
{
    if(!a || !b) return a?a:b;
    else 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;
    }
}
int kth(Node* now,int k)
{
    if(now->size<k) return -1;
    if((now->rc?now->rc->size:0)+1==k) return now->val;
    else if((now->rc?now->rc->size:0)+1>k) return kth(now->rc,k);
    else return kth(now->lc,k-(now->rc?now->rc->size:0)-1);
}
void dfs(vector<int>& topush,Node* now)
{
    if(!now) return;
    dfs(topush,now->lc);
    topush.push_back(now->val);
    dfs(topush,now->rc);
}
int ans[maxq];
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    
    for(int i=1,x;i<=n;i++) {scanf("%d",&x);fa[i]=i;root[i]=new Node(x);}
    
    for(int i=0,a,b,c;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        edges.push_back((Edge){a,b,c});
    }
    sort(edges.begin(),edges.end());

    for(int i=0,v,x,k;i<q;i++)
    {
        scanf("%d%d%d",&v,&x,&k);
        qu.push_back((Query){v,x,k,i});
    }
    sort(qu.begin(),qu.end());
    
    Node *tl,*tr;
    int p=-1;
    for(int i=0;i<q;i++)
    {
        while(p+1<m && edges[p+1].w<=qu[i].x)
        {
            int u=findset(edges[p+1].from),v=findset(edges[p+1].to);p++;
            if(u==v) continue;

            if(root[u]->size < root[v]->size) swap(u,v); // heuristic

            vector<int> topush;
            dfs(topush,root[v]); 
            for(int j=0;j<topush.size();j++)
            {
                split(root[u],topush[j],tl,tr);
                root[u]=merge(tl,merge(new (pmem++) Node(topush[j]),tr));
            }
             
            fa[v]=u;
        }
        int u=findset(qu[i].v);
        ans[qu[i].id]=kth(root[u],qu[i].k);
    }
    for(int i=0;i<q;i++) printf("%d\n",ans[i]);
}