hdu 5029 Relief grain(ツリーチェーン分割+セグメントツリー)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5029
題意:木と操作を与える.操作a,b,kは,ツリー上のa,bノード間の経路上のノードにk値を加算し,最後に各ノードに最大回加算された数を出力することに相当する.
構想:まず木の鎖で分割して問題を線形構造に変換して、それからどのように線形でこの問題を解決するかを考えます.区間染色に相当し、最後にポイントごとに最も多く染められた色を聞く.
方法:各操作a,b,kに対して、私たちはaノードにkをマークし、b+1ノードに-kをマークし、複数のマークしない私たちはvectorで記憶することができ、まずすべての操作をこの線形の構造に打ち込み、線分ツリーで維持することができる.
区間a~bには、色aから色bまでで最も多く現れる色のラベルが維持されている.これにより、マークされた線形構造を左から右にスキャンし、ノードごとに格納されたラベルを線分ツリーに更新することができる.
は、正の値で対応する色の回数+1、そうでなければ-1、すべてのマークを伝えた後、ルートノードの値(メンテナンスは全区間)をとると、現在最も染められた回数が多い値がわかります.感覚の仕方が巧みだ.
code:

#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment(linker, "/STACK:102400000,102400000") 

using namespace std;

const int maxn=105000;
const int maxe=400010;

struct edge
{
    int to,next;
} P[maxe];

int head[maxn],si;
int fa[maxn],deep[maxn],son[maxn],num[maxn];
int top[maxn],p[maxn],fp[maxn],pos;

void init()
{
    si=0;
    memset(head,-1,sizeof(head));
    pos=1;
    memset(son,-1,sizeof(son));
}

void add_edge(int s,int t)
{
    P[si].to=t;
    P[si].next=head[s];
    head[s]=si++;
}

void dfs1(int u,int pre,int d)
{
    deep[u]=d;
    fa[u]=pre;
    num[u]=1;
    for(int i=head[u];i!=-1;i=P[i].next){
        int v=P[i].to;
        if(v!=pre){
            dfs1(v,u,d+1);
            num[u]+=num[v];
            if(son[u]==-1||num[v]>num[son[u]]) son[u]=v;
        }
    }
}
void getpos(int u,int sp)
{
    top[u]=sp;
    p[u]=pos++;
    fp[p[u]]=u;
    if(son[u]==-1) return ;
    getpos(son[u],sp);
    for(int i=head[u];i!=-1;i=P[i].next){
        int v=P[i].to;
        if(v!=son[u]&&v!=fa[u]) getpos(v,v);
    }

}
vector w[maxn];
void add(int u,int v,int tt)
{
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if(deep[f1]deep[v]) swap(u,v);
    w[p[u]].push_back(tt);
    w[p[v]+1].push_back(-tt);
}
//     
int n,cc[maxn];
struct ppp
{
    int l,r,dat;
} ss[4*maxn+10];

void Build(int k,int ll,int rr)
{
    ss[k].l=ll;
    ss[k].r=rr;
    if(ll==rr){
        ss[k].dat=ll;
        return ;
    }
    else    ss[k].dat=0;
    Build((k<<1)+1,ll,(ll+rr)/2);
    Build((k<<1)+2,(ll+rr)/2+1,rr);
}
void init_tree(int n_)
{
    n=1;
    while(n0){
        k=(k-1)/2;
        if(cc[ss[2*k+1].dat]>=cc[ss[2*k+2].dat])
            ss[k].dat=ss[2*k+1].dat;
        else
            ss[k].dat=ss[2*k+2].dat;
    }
}

int ans[maxn];
int main()
{
    int nn,mm,col;
    int s,t,tt;
    while(scanf("%d%d",&nn,&mm),nn!=0||mm!=0){
        init();
        col=0;
        memset(ans,0,sizeof(ans));
        memset(cc,0,sizeof(cc));
        for(int i=1;i0) update(w[i][j],1);
                else          update(-w[i][j],-1);
            }
            ans[fp[i]]=ss[0].dat;
        }
        for(int i=1;i<=nn;i++) printf("%d
",ans[i]);
    }
    return 0;
}

もう1つの方法はsetを使って、まず1つのpairを定義して、そのfirst値は色が現れる回数を保存して、second値は対応する色を保存して、setはまずfisrtを押してソートして、次にsecondのソートを押して、それでいいです.