BZOJ 3307 雨天的尾巴 線段樹

題目大意：給定一棵樹，有m個操作，每次給一條路徑上的每個點分發一個顏色為z的物品，所有操作結束後輸出每個點上數量最多的是哪種物品
對於每個操作，我們在x和y上各打上一個插入z的標記，然後在LCA(x,y)和Fa(LCA(x,y))上各打上一個刪除z的標記
然後我們對z維護線段樹
DFS一遍，對於每個節點進行如下操作：
1.將所有子節點的線段樹合並過來
2.處理標記，該插♂入的插♂入，該刪除的刪除
3.查詢最大值作為答案
這樣的復雜度是O(mlogm)的
然而跑不過樹鏈剖分什麼鬼……是我沒離散化的關系？

#include 
#include 
#include 
#include 
#include 
#define M 100100
using namespace std;

struct Segtree{
    Segtree *ls,*rs;
    int pos,val;
    void* operator new (size_t)
    {
        static Segtree *mempool,*C;
        if(C==mempool)
            mempool=(C=new Segtree[1<<15])+(1<<15);
        C->ls=C->rs=0x0;
        C->pos=0;C->val=0;
        return C++;
    }
    void Push_Up()
    {
        val=0;
        if(ls&&ls->val>val)
            val=ls->val,pos=ls->pos;
        if(rs&&rs->val>val)
            val=rs->val,pos=rs->pos;
    }
    friend void Modify(Segtree *&p,int x,int y,int pos,int val)
    {
        int mid=x+y>>1
        if(!p) p=new Segtree;
        if(x==y)
        {
            p->pos=mid;
            p->val+=val;
            if(!p->val)
                p=0x0;
            return ;
        }
        if(pos<=mid)
            Modify(p->ls,x,mid,pos,val);
        else
            Modify(p->rs,mid+1,y,pos,val);
        p->Push_Up();
        if(!p->val)
            p=0x0;
    }
    friend void Merge(Segtree *&p1,Segtree *p2,int x,int y)
    {
        int mid=x+y>>1;
        if(!p2) return ;
        if(!p1)
        {
            p1=p2;
            return ;
        }
        if(x==y)
        {
            p1->val+=p2->val;
            return ;
        }
        Merge(p1->ls,p2->ls,x,mid);
        Merge(p1->rs,p2->rs,mid+1,y);
        p1->Push_Up();
    }
}*tree[M];

struct abcd{
    int to,next;
}table[M<<1];

int n,m;
int dpt[M],fa[M][17],ans[M];

vector operations;

void Add(int x,int y)
{
    table[++tot].to=y;
    table[tot].next=head[x];
    head[x]=tot;
}

void DFS1(int x)
{
    int i,j;
    dpt[x]=dpt[fa[x][0]]+1;
    for(j=1;j<=16;j++)
        fa[i][j]=fa[fa[i][j-1]][j-1];
    for(i=head[x];i;i=table[i].next)
        if(table[i].to!=fa[x])
            fa[table[i].to][0]=x,DFS1(table[i].to);
}

int LCA(int x,int y)
{
    int j;
    for(j=16;~j;j--)
        if(dpt[fa[x][j]]>=dpt[y])
            x=fa[x][j];
    if(x==y) return x;
    for(j=16;~j;j--)
        if(fa[x][j]!=fa[y][j])
            x=fa[x][j],y=fa[y][j];
    return fa[x][0];
}

void DFS2(int x)
{
    int i;
    for(i=head[x];i;i=table[i].next)
        if(table[i].to!=fa[x][0])
        {
            DFS2(table[i].to);
            Merge(tree[x],tree[table[i].to]);
        }
    vector::iterator it;
    for(it=operations[x].begin();it!=operations[x].end();it++)
        if(*it>0)
            Modify(tree[x],1,1000000000,*it,1);
        else
            Modify(tree[x],1,1000000000,-*it,-1);
    if(tree[x])
        ans[x]=tree[x]->pos;
}

int main()
{
    int i,x,y,z;
    cin>>n>>m;
    for(i=1;i