A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3435 [wc2014] 紫荆花之恋
发表于: | 分类: Oi | 评论:0 | 阅读:110

~~我不相信有比这个更闹挺 的动态点分治~~
陈老师我仰慕您
新年伊始,我感觉自己人生圆满了,这是新年第一题
首先这题确实做到了动态树/分治……
不再是动态/树分治了

首先考虑如果这玩意是个静态的怎么玩
我们可以直接枚举lca
然后这样

假设我们枚举到了圆圈
然后新加入的点在右面的三角形里面
根据题中的条件 $\text{dist}(i,j)\le r_i+r_j$
我们把它拆开
然后他就变成了$\text{dist}(lca,j)-r_j \le r_i -\text{dist}(lca,i)$
然后我们在每个节点维护一个$treap$
每次查询整棵树符合条件的数量
再减去右面那个三角形符合条件的数量
为了满足条件,我们可以在右面那个子树里面再开一个treap,维护的是该子树的信息,注意,信息还是对于上面那个点的
恩这样就行了
~~别逗了,这样又T又MLE不死才怪~~

显然这样是不行的,所以我们可以用一个替罪羊维护一个分治树,把分治树的每个节点作为要枚举的$lca$,显然这样是没有问题的
然后每次修改的时候发现一个子树的$size$太大的时候就重建一下
看起来好像还是挺简单的~
~~说简单的过来写一个吧~~

作为一名重写两次调试三个小时的前辈,我还是传授一点人生经验吧……

1.在重建子树的时候,你要记着维护对于上一个分治中心的那一部分你没有重新做,但是不用重新做,你只需要继承一下原来的标号就行了
2.请注意原树的根和新树的根的衔接问题……【md坑了我一个小时
3.对于分治树的图要用$set$存,原因是这样的,你需要删除原来的分治中心然后插上一个新的分治中心。什么数据弱?扯犊子吧……我人手调的点每个都是特殊点……
4.替罪羊的平衡因子千万别调的太小,千万……9,10两个点都是一条长链……我最开始因子太大无限重构,后来因子太小不重构……
5.不能时刻重构……千万要记下需要重构的最后一个,千万千万……千万千万……

~~我才不会告诉你最后两个点我跑了60+然后+cheat才过的呢,因此uoj上还是90分[cheat的部分就不显示了……~~

#include <set>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100100+5;
const int M = N << 1;
typedef long long LL;
using namespace std;

int head[N];
LL lastans;
int n;
int r[N],v[N],f[N];


char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
  
int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}

struct graph{
    int next,to,val,ban;
    graph () {}
    graph (int _next,int _to,int _val,int _ban=0)
    :next(_next),to(_to),val(_val),ban(_ban){}
}edge[M];

inline void add(int x,int y,int z){
    static int cnt = 1;
    edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z); head[y] = cnt;
}

int fa[N][17],depth[N],dis[N];

inline int lca(int x,int y){
    if(depth[x] < depth[y]) swap(x,y);
    int tt = depth[x] - depth[y];
    for(int i=16;~i;--i) if((1<<i)&tt) x = fa[x][i];
    for(int i=16;~i;--i) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return x == y ? x : fa[x][0];
}

inline void init(int i){
    for(int j=1;j<=16;++j)
        fa[i][j] = fa[fa[i][j-1]][j-1];
}

inline int calc(int x,int y){
    return dis[x] + dis[y] - 2*dis[lca(x,y)];
}

struct Treap{

    int root[N], sz;

    struct treap{
        int l,r,val,rnd,cnt,size;
    }tr[M*30];
    queue <int> q;

    inline int newnode(){
        if(!q.empty()){
            int tt = q.front();
//          cout << tt << endl;
            q.pop(); return tt;
        }
        else {
//          cout << sz << endl;
            return ++sz;
        }
    }

    inline void updata(int k){
        tr[k].size = tr[tr[k].l].size + tr[tr[k].r].size + tr[k].cnt;
    }

    inline void rturn(int &k){
        int t = tr[k].l;
        tr[k].l = tr[t].r;
        tr[t].r = k;
        updata(k);
        updata(t);
        k = t;
    }

    inline void lturn(int &k){
        int t = tr[k].r;
        tr[k].r = tr[t].l;
        tr[t].l = k;
        updata(k);
        updata(t);
        k = t;
    }

    void insert(int &k,int x){
        if(!k){
            k = newnode();
            tr[k].val = x;
            tr[k].cnt = tr[k].size = 1;
            tr[k].l = tr[k].r = 0;
            return;
        }
        if(x == tr[k].val){
            tr[k].cnt ++;
            tr[k].size ++;
            return ;
        }
        else if(x < tr[k].val){
            insert(tr[k].l,x);
            if(tr[tr[k].l].rnd < tr[k].rnd) rturn(k);
        }
        else {
            insert(tr[k].r,x);
            if(tr[tr[k].r].rnd < tr[k].rnd) lturn(k);
        }
        updata(k);
    }

    void DFS(int &k){
        if(tr[k].l) DFS(tr[k].l);
        if(tr[k].r) DFS(tr[k].r);
        tr[k].l = tr[k].r = tr[k].cnt = tr[k].size = 0;
        q.push(k); k = 0; return;
    }

    int ask(int k,int x){
        if(!k) return 0;
        if(x < tr[k].val) return ask(tr[k].l,x);
        else return tr[tr[k].l].size + tr[k].cnt + ask(tr[k].r,x);
    }
}T1,T2;

int last[N],times;

set <int> to[N];

void DFS(int x){
    set <int> ::iterator it;
    v[x] = times; 
    for(it = to[x].begin(); it != to[x].end(); it ++){
        DFS(*it);
        T2.DFS(T2.root[*it]);
    }
    to[x].clear();
    T1.DFS(T1.root[x]);
}

int size[N];

void DFS1(int x,int fa){
    size[x] = 1;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].ban !=  times && v[edge[i].to] == times && edge[i].to != fa){
            DFS1(edge[i].to,x);
            size[x] += size[edge[i].to];
        }
}

int sum,root;

void DFS2(int x,int fa){
    f[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && edge[i].ban != times && v[edge[i].to] == times){
            DFS2(edge[i].to,x);
            f[x] = max(f[x],size[edge[i].to]);
        }
    f[x] = max(f[x],sum - size[x]);
    if(f[x] < f[root]) root = x;
}

void DFS3(int x,int fa,int bl,int dis){
    T1.insert(T1.root[bl],dis-r[x]);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && edge[i].ban != times && v[edge[i].to] == times)
            DFS3(edge[i].to,x,bl,dis+edge[i].val);
}

void DFS4(int x,int fa,int bl,int dis){
    T2.insert(T2.root[bl],dis-r[x]);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && edge[i].ban != times && v[edge[i].to] == times)
            DFS4(edge[i].to,x,bl,dis+edge[i].val);
}

int temp;

void solve(int x){
    DFS1(x,0); root = 0, sum = size[x];
    DFS2(x,0); x = root; DFS1(x,0);  DFS3(x,0,x,0);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].ban != times && v[edge[i].to] == times){
            edge[i].ban = edge[i^1].ban = times;
        //  dis[edge[i].to] = dis[x] + edge[i].val;
            root = 0; sum = size[edge[i].to];
            DFS2(edge[i].to,x);
            DFS4(edge[i].to,x,root,edge[i].val);
    //      cout << root << endl;
            to[x].insert(root);  last[root] = x; solve(edge[i].to); 
        }
    temp = x;
}

void rebuild(int x){
    times ++; DFS(x);
    int F = last[x], tmp = T2.root[x]; 
    T2.root[x] = 0;
    solve(x); 
    last[temp] = F;
    if(F) to[F].insert(temp),to[F].erase(x);
    T2.root[temp] = tmp;
}

void insert(int x){
    for(int i=x;i;i=last[i]){
        if(last[i]){
            int tmp1 = calc(x,last[i]);
            lastans += T1.ask(T1.root[last[i]],r[x]-tmp1);
            lastans -= T2.ask(T2.root[i],r[x]-tmp1);
            T2.insert(T2.root[i],tmp1-r[x]);
        }
        int tmp = calc(x,i);
        T1.insert(T1.root[i],tmp-r[x]);
    }
    int tt = 0;
    for(int i=x;last[i];i=last[i])
        if(T1.tr[T1.root[i]].size * 5 > T1.tr[T1.root[last[i]]].size * 4)
            tt = last[i];
    if(tt)
        rebuild(tt);
}

int main(){
    f[0] = 0x3f3f3f3f;
    read(); n = read();
    for(int i=1;i<=n;++i){
        int x = read(), y = read(), z = read();
        x = x ^ (lastans%1000000000);
        add(i,x,y); fa[i][0] = x; init(i), r[i] = z;
        depth[i] = depth[x] + 1, dis[i] = dis[x] + y;
        to[x].insert(i); last[i] = x;
        insert(i);
        printf("%lld\n",lastans);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP