Bzoj 3307 雨天的尾巴（線段樹合并+樹上差分）

C. 雨天的尾巴

題目描述

N個點，形成一個樹狀結構。有M次發放，每次選擇兩個點x,y對于x到y的路徑上（含x,y)每個點發一袋Z類型的物品。完成所有發放後，每個點存放最多的是哪種物品。

輸入格式

第一行數字N，M

接下來N-1行，每行兩個數字a,b,表示a與b間有一條邊

再接下來M行，每行三個數字x,y,z.如題

輸出格式

輸出有N行

每i行的數字表示第i個點存放最多的物品是哪一種，如果有

多種物品的數量一樣，輸出編号最小的。如果某個點沒有物品則輸出0

樣例

樣例輸入

20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50      

View Code

樣例輸出

87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50      

View Code

資料範圍與提示

1<=N,M<=100000

1<=a,b,x,y<=N

1<=z<=10910^910​9​​

暴力能得50分呢……

樹上操作首先會想到樹剖和樹上差分吧，這裡隻說差分;

離線處理，權值線段樹維護每一個點的狀态（每種物品出現次數及其最大值），對于每次操作，将x+1，y+1，LCA（x，y）-1，fa[LCA]-1最後dfs合并線段樹統計答案即可。

注意合并（修改）葉子節點時最大值是加而不是取max。

這道題比較惡心的是卡記憶體，卡了我四節課…

如果線段樹合并操作是建新節點的話會MLE，代碼如下：

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    int now=++cnt;
    sum(now)=sum(x)+sum(y);
    l(now)=merge(l(x),l(y));
    r(now)=merge(r(x),r(y));
    if(!l(x) && !r(x))maxn(now)=maxn(x)+maxn(y);
    else maxn(now)=max( maxn(l(now)) , maxn(r(now)) );
    return now;
}      

但是顯然不這樣的話資料會出錯（将y的子樹同時變為x的子樹，之後在合并x時會修改資料），但是其實并不需要讓線段樹最後是正确的，隻需要在y資料發生錯誤之前記錄答案即可。

标程

#include<iostream>
#include<cstdio>
#include<map>
#include<time.h>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct edge
{
    int u,v,next;
    #define u(x) ed[x].u
    #define v(x) ed[x].v
    #define n(x) ed[x].next
}ed[200010];
int first[100010],num_e;
#define f(x) first[x]
int n,m,Q,fa[100010][21],bin[21],dep[100010];
int x[100010],y[100010],z[100010],z2[100010];
map<int,int> mp;
int mmp[100010];
int ans[100010];

struct tree
{
    int l,r,sum,maxn;
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define sum(x) tr[x].sum
    #define maxn(x) tr[x].maxn
}tr[20000000];
int cnt,rt[100010];

int ask(int l,int r,int a)
{
    if(sum(a)==0)return 0;
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(maxn(l(a))>=maxn(r(a)))return ask(l,mid,l(a));
    return ask(mid+1,r,r(a));
}
void add(int &mark,int l,int r,int loc,int val)
{
    if(!mark)mark=++cnt;
    if(l==r){sum(mark)+=val;maxn(mark)+=val;return;}
    int mid=(l+r)>>1;
    if(loc<=mid)add(l(mark),l,mid,loc,val);
    else        add(r(mark),mid+1,r,loc,val);
    sum(mark)=sum(l(mark))+sum(r(mark));
    maxn(mark)=max( maxn(l(mark)) , maxn(r(mark)));
}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    l(x)=merge(l(x),l(y));
    r(x)=merge(r(x),r(y));
    sum(x)=sum(x)+sum(y);
    if(!l(x) && !r(x))maxn(x)=maxn(x)+maxn(y);
    else               maxn(x)=max( maxn(l(x)) , maxn(r(x)) );
    return x;
}
void dfs2(int x,int ffa);
inline int read();
int LCA(int x,int y);
void dfs(int x,int ffa);
inline void add_e(int u,int v);
signed main()
{
//    freopen("4.in","r",stdin);
//    freopen("out.txt","w",stdout);
    
    bin[0]=1;
    for(int i=1;i<=20;i++)bin[i]=bin[i-1]*2;
    n=read(),Q=read();
    int ta,tb;
    for(int i=1;i<n;i++)
    {
        ta=read(),tb=read();
        add_e(ta,tb);
        add_e(tb,ta);
    }
    for(int j=1;j<=Q;j++)
        x[j]=read(),y[j]=read(),z[j]=read(),z2[j]=z[j];
    sort(z2+1,z2+Q+1);
    m=unique(z2+1,z2+Q+1)-z2-1;
    for(int i=1;i<=Q;i++)
    {
        int loc=lower_bound(z2+1,z2+m+1,z[i])-z2;
        mp[z[i]]=loc;
        mmp[loc]=z[i];
    }
    dfs(1,0);
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    mmp[0]=0;        
    for(int i=1;i<=Q;i++)    
    {
        int loc=mp[z[i]],
            lca=LCA(x[i],y[i]),
            ffa=fa[lca][0];
        add(rt[x[i]],1,m,loc,1);
        add(rt[y[i]],1,m,loc,1);
        add(rt[lca], 1,m,loc,-1);
        if(ffa)
        add(rt[ffa] ,1,m,loc,-1);
    }
    dfs2(1,0);
    ans[1]=ask(1,m,rt[1]);
    for(int i=1;i<=n;i++)    
        printf("%d\n",mmp[ans[i]]);
}
void dfs2(int x,int ffa)
{
    for(int i=f(x);i;i=n(i))
    if(v(i)!=ffa)
    {
        dfs2(v(i),x);
        ans[v(i)]=ask(1,m,rt[v(i)]);
        rt[x]=merge(rt[x],rt[v(i)]);
    }
}
inline int read()
{
    int s=0;char a=getchar();
    while(a<'0'||a>'9')a=getchar();
    while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
    return s;
}
inline void add_e(int u,int v)
{
    ++num_e;
    u(num_e)=u;
    v(num_e)=v;
    n(num_e)=f(u);
    f(u)=num_e;
}
void dfs(int x,int ffa)
{
    fa[x][0]=ffa;
    dep[x]=dep[ffa]+1;
    for(int i=f(x);i;i=n(i))
    if(v(i)!=ffa)
        dfs(v(i),x);
}
int LCA(int x,int y)
{
    if(dep[x]>dep[y])swap(x,y);
    while(dep[x]!=dep[y])
    for(int i=0;;i++)
        if(dep[fa[y][i]]<dep[x])
        {
            y=fa[y][i-1];
            break;
        }
    if(x==y)return x;
    while(fa[x][0]!=fa[y][0])
        for(int i=0;;i++)
            if(fa[x][i]==fa[y][i])
                {x=fa[x][i-1],y=fa[y][i-1];break;}
    return fa[x][0];
}      

View Code

轉載于:https://www.cnblogs.com/Al-Ca/p/11045904.html