[HDU 4605][Segment Tree] Magic Ball Game

原題連結
嗚姆....這題讓我頗開心的獲得了1A XD

先不管樹這個型態，我們想要查詢的東西其實是「在一堆數字裡有幾個比我小(大)」，這讓我們想到權值線段樹或是Treap，這題兩種應該都是可以的，以下採用權值線段樹。

那麼我們來解決如何對樹的型態做處理。這題關鍵的東西是「從某點到根的路徑」，我們的目標就是要快速找出上面提到的「一堆數字」是哪些數字。

「從某點到根的路徑」一開始讓我想到了樹鏈剖分，可以在logn的時間裡獲得「一堆數字」，再花logn的時間去做剛剛提到的查詢；我看了一下原題的記憶體限制和時限，認為這方法實在有點不靠譜......如果有用這個方法做出來的人請務必跟我說XD，順帶一提，這樣做的好處是完全在線回答所有詢問。

之後我就想了離線怎麼好好處理詢問，很快發現：其實對於同一個點的詢問可以一次做完！我們只要確保dfs到達那個點的時候權值線段樹(or Treap)只有「從這個點到根的路徑上的數字(除了自己)」在裡面而已，這完全可以藉由在dfs下一層前modify，dfs的出口de_modify來達成。

這樣，就成功離線解決了問題。
時間複雜度:O(nlogc + Qlogc)，c是值域。 如果有離散化，logc可以壓成logn，也可以簡單的用BIT去做。

#include<cstdio>
#include<new>
#include<vector>
using namespace std;
const int maxn=100000+5;
const int maxnode=1000000+5;
const int maxc=1000000000;
struct Query
{
    int id,x;
    Query(int a,int b):id(a),x(b) {}
};
vector<Query> qu[maxn];
vector<int> G[maxn];
int val[maxn];
struct Node
{
    static Node mem[maxnode];
    Node *lc,*rc;
    int size,toleft;
    void pull()
    {
        size=(lc?lc->size:0)+(rc?rc->size:0);
        toleft=(lc?lc->toleft:0)+(rc?rc->toleft:0);
    }
    Node() {size=toleft=0;lc=rc=NULL;}
}*root,Node::mem[maxnode],*pmem=Node::mem;
void modify(Node*& now,int L,int R,int mx,int msize,int mtoleft)
{
    if(!now) now=new (pmem++) Node();
    if(L==R) {now->size+=msize;now->toleft+=mtoleft;return;}
    int M=L+(R-L)/2;
    if(mx<=M) modify(now->lc,L,M,mx,msize,mtoleft);
    else modify(now->rc,M+1,R,mx,msize,mtoleft);
    now->pull();
}
void query(Node* now,int L,int R,int qx,int& seven,int& two)
{
    if(L==R)
    {
        if(now && now->size!=0) seven=-1;
        return;
    }
    int M=L+(R-L)/2;
    if(qx<=M)
    {
        int rsize=(now && now->rc?now->rc->size:0),rtoleft=(now && now->rc?now->rc->toleft:0);
        seven+=0,two+=rsize;
        query(now?now->lc:0,L,M,qx,seven,two);
    }
    else
    {
        int lsize=(now && now->lc?now->lc->size:0),ltoleft=(now && now->lc?now->lc->toleft:0);
        seven+=lsize-ltoleft,two+=3*lsize;
        query(now?now->rc:0,M+1,R,qx,seven,two);
    }
}
int ans[maxn][2];
void dfs(int now)
{
    for(int i=0;i<qu[now].size();i++)
    {
        Query& q=qu[now][i];
        ans[q.id][0]=ans[q.id][1]=0;
        query(root,1,maxc,q.x,ans[q.id][0],ans[q.id][1]);
    }
    for(int i=0;i<G[now].size();i++)
    {
        modify(root,1,maxc,val[now],1,i==0?1:0);
        dfs(G[now][i]);
        modify(root,1,maxc,val[now],-1,i==0?-1:0);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        pmem=Node::mem;
        root=NULL;

        int n,m,q;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",val+i);
        
        scanf("%d",&m);
        for(int i=1;i<=n;i++) qu[i].clear(),G[i].clear();
        for(int i=0,u,a,b;i<m;i++)
        {
            scanf("%d%d%d",&u,&a,&b);
            G[u].push_back(a);
            G[u].push_back(b);
        }

        scanf("%d",&q);
        for(int i=0,p,x;i<q;i++)
        {
            scanf("%d%d",&p,&x);
            qu[p].push_back(Query(i,x));
        }
        dfs(1);

        for(int i=0;i<q;i++) if(ans[i][0]==-1) printf("0\n");
        else printf("%d %d\n",ans[i][0],ans[i][1]);
    }
}