BZOJ 4719:[Noip 2016]毎日ランニングが好きな線分樹の合併

title
BZOJ 4719
LUOGU 1600
問題の簡略化: c学生はランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.「毎日走るのが好き」は育成ゲームで、プレイヤーが毎日時間通りにオンラインになり、カードを打つ任務を完成する必要がある.
このゲームの地図は、(n)個のノードと(n-1)個のエッジを含むツリーと見なすことができ、各エッジが2つのノードを接続し、任意の2つのノードが1つのパスで互いに達することができる.ツリー上のノード番号は、(1)から(n)までの連続正の整数です.
現在、(m)個のプレイヤーがおり、(i)個目のプレイヤーの起点は(S_i)、終点は(T_i)である.毎日カードを打つ任務が始まる時、すべてのプレーヤーは(0)秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に走った後にそのプレーヤーはカードを打つ任務を完成したとしても.(地図は木なので、一人一人の経路は唯一です) cゲームの活躍度を知りたいので、各ノードにオブザーバーが1人ずつ置かれています.ノード(j)のオブザーバーは、(W_j)秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーが(W_j)秒目にもノード(j)に到達することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノード(j)を終点とするプレイヤーに対して、彼が(W_j)秒前に終点に到着すると、ノード(j)のオブザーバーはそのプレイヤーを観察できない.彼がちょうど(W_j)秒目にゴールに着いた場合、ノード(j)のオブザーバーはこのプレイヤーを観察することができる.
analysis
人にとって、彼の道のりは2つの段に分けられ、1段は上(根)に、1段は下に、上への過程で彼が貢献できる観察者がどんな性質を持っているかを考えます:出発点の深さを(dep[x])、観察者の深さを(dep[y])、観察の時間を(t)とし、(dep[x]-dep[y]=t)を満たす必要があります.言い換えれば(dep[y]+t=dep[x])です.次の段落の導出は類似しており,以下の部分も上向きの経路を例に挙げて説明するだけである.
各点の下の出発点の深さが(dep[x])の人数を記録するには、出発点から出発点と目的地までの(lca)のすべての点を出発点ごとに更新する必要があります.重み値の線分ツリーを開き、線分ツリーで統合して情報をアップロードし続け、(lca)で今回の更新の影響を除去したいと考えています.これで直接木の上で答えを統計することができます.ダウンパスの処理はアップパスと似ています.
code

#include

const int maxn=3e5+10;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    templateinline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    templateinline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

int ver[maxn<<1],Next[maxn<<1],head[maxn],len;
inline void add(int x,int y)
{
    ver[++len]=y,Next[len]=head[x],head[x]=len;
}

namespace SGT
{
    struct Orz{int l,r,z;}c[maxn*60];
    int num=0;
    inline void Change(int &x,int l,int r,int k,int z)
    {
        if (!x) x=++num;
        c[x].z+=z;
        if (l==r) return ;
        int mid=(l+r)>>1;
        if (k<=mid) Change(c[x].l,l,mid,k,z);
        else Change(c[x].r,mid+1,r,k,z);
    }

    inline int query(int x,int l,int r,int k)
    {
        if (l==r) return c[x].z;
        int mid=(l+r)>>1;
        if (k<=mid) return query(c[x].l,l,mid,k);
        else return query(c[x].r,mid+1,r,k);
    }

    inline int merge(int x,int y)
    {
        if (!x) return y;
        if (!y) return x;
        c[x].l=merge(c[x].l,c[y].l);
        c[x].r=merge(c[x].r,c[y].r);
        c[x].z=c[x].z+c[y].z;
        return x;
    }
}

using SGT::Change;
using SGT::query;
using SGT::merge;

namespace lca
{
    int dfn[maxn],id;
    int f[maxn][21],dep[maxn];
    inline void dfs(int x)
    {
        dfn[x]=++id;
        for (int i=1; i<=20; ++i) f[x][i]=f[f[x][i-1]][i-1];
        for (int i=head[x]; i; i=Next[i])
        {
            int y=ver[i];
            if (y==f[x][0]) continue;
            f[y][0]=x;
            dep[y]=dep[x]+1;
            dfs(y);
        }
    }

    inline int LCA(int x,int y)
    {
        if (dep[x]>dep[y]) std::swap(x,y);
        for (int i=20; i>=0; --i)
            if (dep[y]-(1<=dep[x]) y=f[y][i];
        if (x==y) return x;
        for (int i=20; i>=0; --i)
            if (f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
        return f[x][0];
    }
}

using lca::dfs;
using lca::LCA;
using lca::dep;
using lca::f;

int tot,n,m,u[maxn],v[maxn];
int ans[maxn],w[maxn];
inline void get(int x)
{
    for (int i=head[x]; i; i=Next[i])
    {
        int y=ver[i];
        if (y==f[x][0]) continue;
        get(y);
        u[x]=merge(u[x],u[y]), v[x]=merge(v[x],v[y]);
    }
    ans[x]=query(u[x],1,tot,dep[x]+w[x])+query(v[x],1,tot,w[x]-dep[x]+n);
}

int main()
{
    read(n);read(m); tot=n<<1;
    for (int i=1,x,y; i

転載先:https://www.cnblogs.com/G-hsm/p/11426646.html