[HDU 4605]Magic Ball Game

我們先假設$N\leq 1000$且$Q\leq 1000$
這樣就可以直接從根出發，每到一個節點$u$就將機率依和$w_{u}$的大小關係乘上對應的分數
如果在走到$v$前走到$w_{u}=x$的，代表沒有答案

現在$N\leq 100000$且$Q\leq 100000$
會TLE的情況就是高度很高、接近一條鏈的樹
那我們能不能每個節點只要走一次就好呢？

可以的！

可以發現，每通過一個節點$u$
走到左子樹相當於為所有$x<w_{u}$的的詢問貢獻$\frac{1}{2}$，$x>w_{u}$的貢獻$\frac{1}{8}$
走到右子樹相當於為所有$x<w_{u}$的的詢問貢獻$\frac{1}{2}$，$x>w_{u}$的貢獻$\frac{7}{8}$
這是個離線操作的方式

乍看之下很像區間修改
沒錯，我們可以用線段樹或$treap$來實現區間修改！
可是線段樹不離散化就得$copy-on-write$
因此我這裡採用了$treap$

這裡的區間包含各種長度只有$1$的$[w_{u},w_{u}]$和剩餘右界是$w_{u}-1$，左界是右界往左走第一個碰到的$w_{v}+1$的區間 (左界有可能是$-INF$)，加上最右邊右界是$INF$的區間

直接將每個區間的右界選作代表存成一個節點，因此查詢$x$時只要找到最接近$x$且$\geq x$的節點就好了
在一條$\log N$的查詢路徑上，$\geq x$的節點中最接近$x$的就是所求，可以透過更新答案的方式

那遇到無解的情況要怎麼判斷？
我們可以為每個節點新增一個屬性：exist
在前往子節點前先將代表$w_{u}$的節點的exist設為$false$
這樣只要判斷查到的節點exist是不是$true$就好，不是的話代表無解

注意遞迴到子節點算完返回時要抵銷對$treap$的修改，才能再遞迴到另一個子節點繼續算

時間複雜度：$O((M+Q)\log N)$ (其實$M=\frac{N-1}{2}$永遠成立)

p.s.如果你想用持久化結構寫出這題的在線作法，你會得到MLE (你想要記憶體回收？沒用的www)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<set>
#include<utility>
using namespace std;
const int INF=2147483647;
int Rand()
{
    static unsigned int seed=20160221;
    seed*=0xdefaced,seed+=115216;
    return (seed+=seed>>20)&0x7fffffff;
}
struct Node
{
    Node *ch[2];
    const int x;
    int sz;
    int cnt7,cnt2;
    int tag7,tag2;
    bool exist;
    Node(const int _x):ch{NULL,NULL},x(_x),sz(1),cnt7(),cnt2(),tag7(),tag2(),exist(true){}
    void Add(const int v7,const int v2)
    {
        cnt7+=v7,cnt2+=v2;
        tag7+=v7,tag2+=v2;
    }
};
void PutDown(Node *o)
{
    assert(o);
    if(!o->tag7&&!o->tag2)return;
    for(int d=0;d<2;d++)if(o->ch[d])o->ch[d]->Add(o->tag7,o->tag2);
    o->tag7=o->tag2=0;
}
int Sz(Node *o){return o?o->sz:0;}
void Maintain(Node *o)
{
    assert(!o->tag7&&!o->tag2);
    o->sz=Sz(o->ch[0])+1+Sz(o->ch[1]);
}
Node *Merge(Node *a,Node *b)
{
    if(!a||!b)return a?a:b;
    if(Rand()%(a->sz+b->sz)<(a->sz))
    {
        PutDown(a);
        a->ch[1]=Merge(a->ch[1],b);
        Maintain(a);
        return a;
    }
    else
    {
        PutDown(b);
        b->ch[0]=Merge(a,b->ch[0]);
        Maintain(b);
        return b;
    }
}
void Split(Node *o,Node* &a,Node* &b,const int x)
{
    if(!o){a=b=NULL;return;}
    if((o->x)<=x)
    {
        PutDown(a=o);
        Split(a->ch[1],a->ch[1],b,x);
        Maintain(a);
    }
    else
    {
        PutDown(b=o);
        Split(b->ch[0],a,b->ch[0],x);
        Maintain(b);
    }
}
void Query(Node *o,const int x,int &cnt7,int &cnt2,int &min_dist)
{//find the node closest to x by keep updating answer
    if(!o)return;
    PutDown(o);
    if(x<=(o->x))
    {
        if((o->x)-x<min_dist)min_dist=(o->x)-x,cnt7=(o->exist?o->cnt7:-1),cnt2=o->cnt2;
        Query(o->ch[0],x,cnt7,cnt2,min_dist);
    }
    else Query(o->ch[1],x,cnt7,cnt2,min_dist);
}
void Delete(Node *o)
{
    if(!o)return;
    for(int d=0;d<2;d++)Delete(o->ch[d]);
    delete o;o=NULL;
}
int N,W[100000],ANS7[100000],ANS2[100000];
vector<int>ET[100000];
vector<pair<int,int> >QUERY[100000];
void AnswerQuery(const int u,Node* &o)//reference of "o" is necessary
{
    static int min_dist;
    for(const pair<int,int>&p:QUERY[u])Query(o,p.first,ANS7[p.second],ANS2[p.second],min_dist=INF),assert(min_dist!=INF);
    if(ET[u].empty())return;
    assert((int)ET[u].size()==2);
    for(int d=0;d<2;d++)
    {
        Node *a,*b,*c;
        Split(o,b,c,W[u]);
        Split(b,a,b,W[u]-1);
        assert(a),assert(c),assert(Sz(b)==1);
        a->Add(0,1),b->exist=false,c->Add(d,3);
        AnswerQuery(ET[u][d],o=Merge(a,Merge(b,c)));
        //reference of "o" is necessary, or "o" might not be the root now
        Split(o,b,c,W[u]);
        Split(b,a,b,W[u]-1);
        assert(a),assert(c),assert(Sz(b)==1);
        a->Add(0,-1),b->exist=true,c->Add(-d,-3);
        o=Merge(a,Merge(b,c));
    }
}
void CheckValidify(Node *o)
{
    if(!o)return;
    PutDown(o);
    CheckValidify(o->ch[0]),CheckValidify(o->ch[1]);
    assert(o->cnt7==0&&o->cnt2==0);
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0;i<N;i++)scanf("%d",&W[i]);
        if(true)
        {
            int m;scanf("%d",&m);
            for(int u,a,b;m--;)
            {
                scanf("%d%d%d",&u,&a,&b),u--,a--,b--;
                ET[u].push_back(a),ET[u].push_back(b);
            }
        }
        int querycount;scanf("%d",&querycount);
        for(int i=0;i<N;i++)QUERY[i].clear();
        for(int i=0,v,x;i<querycount;i++)
        {
            scanf("%d%d",&v,&x),v--;
            QUERY[v].push_back(make_pair(x,i));
        }
        if(true)
        {
            set<int>tmp;
            for(int i=0;i<N;i++)tmp.insert(W[i]-1),tmp.insert(W[i]);
            tmp.insert(INF);
            Node *o=NULL;
            for(const int v:tmp)o=Merge(o,new Node(v));//,printf("%d ",v);puts("");
            assert(Sz(o)==(int)tmp.size());
            AnswerQuery(0,o);
            assert(Sz(o)==(int)tmp.size());
            CheckValidify(o);
            Delete(o);
        }
        for(int i=0;i<querycount;i++)
        {
            if(ANS7[i]==-1)puts("0");
            else printf("%d %d\n",ANS7[i],ANS2[i]);
        }
    }
    return 0;
}