2016shenyang-1002-HDU5893-List wants to travel-树链剖分+线段树维护不同区间段个数

肯定先无脑树链剖分，然后线段树维护一段区间不同个数，再维护一个左右端点的费用。
线段树更新，pushDown，pushUp的时候要注意考虑链接位置的费用是否相同
还有就是树链剖分操作的时候，维护上一个更新的位置的费用。
总之就是出现区间合并，就考虑总数是否要减一
好想不好写
//场上根本写不完啊
 /*--------------------------------------------------------------------------------------*/

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 //debug function for a N*M array

 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

 {for(int j=;j<(M);j++){\

 printf("%d",G[i][j]);}printf("\n");}

 //debug function for int,float,double,etc.

 #define debug_var(X) cout<<#X"="<<X<<endl;

 #define LL long long

 const int INF = 0x3f3f3f3f;

 const LL LLINF = 0x3f3f3f3f3f3f3f3f;

 /*--------------------------------------------------------------------------------------*/

 using namespace std;

 int N,M,T;

 const int maxn = 2e5+;

 struct Edge{

     int x,y,val;

 }e[maxn];

 vector <int> G[maxn];

 int val[maxn],dep[maxn],siz[maxn],top[maxn],id[maxn],son[maxn],fa[maxn];

 int topw;

 void init()

 {

     for(int i=;i<maxn;i++) G[i].clear();

     topw = ;

 }

 void dfs_1(int u,int f,int d)

 {

     fa[u] = f;

     son[u] = ;

     siz[u] = ;

     dep[u] = d;

     for(int i=;i<G[u].size();i++) if(G[u][i] != f)

     {

         dfs_1(G[u][i],u,d+);

         siz[u] += siz[G[u][i]];

         if(siz[son[u]] < siz[G[u][i] ])

         {

             son[u] = G[u][i];

         }

     }

 }

 void dfs_2(int u,int tp)

 {

     top[u] = tp;

     id[u] = ++topw;

     if(son[u]) dfs_2(son[u],tp);

     for(int i=;i<G[u].size();i++) if(G[u][i]!=fa[u] && G[u][i] != son[u] )

     {

         dfs_2(G[u][i],G[u][i]);

     }

 }

 void debug()

 {

     for(int i=;i<=N;i++)

     {

         printf("%d siz:%d son:%d dep:%d fa:%d ",i,siz[i],son[i],dep[i],fa[i]);

         printf("top:%d id:%d\n",top[i],id[i]);

     }

     return ;

 }

 /*-----------------------------------*/

 #define lson(x) (x<<1)

 #define rson(x) (x<<1|1)

 struct SegmentTree{

     int l,r;

     int lazy;

     int num,lcost,rcost;

 }segtree[*maxn];

 void pushUp(int x)

 {

     segtree[x].num = segtree[lson(x)].num + segtree[rson(x)].num - (segtree[lson(x)].rcost==segtree[rson(x)].lcost?  : );

     segtree[x].lcost = segtree[lson(x)].lcost;

     segtree[x].rcost = segtree[rson(x)].rcost;

     //printf("x:%d [%d,%d] num:%d\n",x,segtree[x].l,segtree[x].r,segtree[x].num);

     //printf("lcost:%d rcost:%d\n",segtree[x].lcost,segtree[x].rcost);

     //printf("l->rcost:%d r->lcost:%d\n",segtree[lson(x)].rcost,segtree[rson(x)].lcost);

 }

 void pushDown(int x)

 {

     if(segtree[x].lazy != -)

     {

         segtree[lson(x)].lcost = segtree[lson(x)].rcost = segtree[x].lazy;

         segtree[rson(x)].lcost = segtree[rson(x)].rcost = segtree[x].lazy;

         segtree[lson(x)].num = segtree[rson(x)].num = ;

         segtree[lson(x)].lazy = segtree[rson(x)].lazy = segtree[x].lazy;

         segtree[x].lazy = -;

     }

 }

 void Build(int l,int r,int x)

 {

     segtree[x].l = l;

     segtree[x].r = r;

     segtree[x].lazy = -;

     if(l == r)

     {

         segtree[x].num = ;

         segtree[x].lcost = segtree[x].rcost = val[l];

         return ;

     }

     int mid = (l+r)>>;

     Build(l,mid,lson(x));

     Build(mid+,r,rson(x));

     pushUp(x);

 }

 void update(int x,int L,int R,int cost)

 {

     if(segtree[x].l >= L && segtree[x].r <= R)

     {

         segtree[x].lcost = segtree[x].rcost = cost;

         segtree[x].num = ;

         segtree[x].lazy = cost;

         return ;

     }

     pushDown(x);

     int mid = (segtree[x].l + segtree[x].r) >> ;

     if(L <= mid) update(lson(x),L,R,cost);

     if(R >  mid) update(rson(x),L,R,cost);

     pushUp(x);

     return ;

 }

 int query(int x,int L,int R)

 {

     if(segtree[x].l >= L && segtree[x].r <= R)

     {

         return segtree[x].num;

     }

     pushDown(x);

     int mid = (segtree[x].l + segtree[x].r) >> ;

     int ans = ;

     if(R <= mid) ans = query(lson(x),L,R);

     else if(L > mid) ans = query(rson(x),L,R);

     else ans = query(lson(x),L,R) + query(rson(x),L,R) - (segtree[lson(x)].rcost==segtree[rson(x)].lcost ?  : ) ;

     pushUp(x);

     return ans;

 }

 int query_edge(int x,int pos)

 {

     if(segtree[x].l == segtree[x].r)

     {

         return segtree[x].lcost;

     }

     pushDown(x);

     int res = ;

     int mid = (segtree[x].l + segtree[x].r) >> ;

     if(pos <= mid) res =  query_edge(lson(x),pos);

     else           res =  query_edge(rson(x),pos);

     pushUp(x);

     return res ;

 }

 int Find(int u,int v)

 {

     int ans = ,fu = top[u],fv = top[v];

     int last_u=- , last_v = -;

     int last_u_color,last_v_color;

     //printf("%d->%d\n",u,v);

     while(fu != fv)

     {

         if(dep[fu] < dep[fv])

         {

             swap(fu,fv);swap(u,v);

             swap(last_u,last_v);

             swap(last_u_color,last_v_color);

         }

         //printf("query:[%d,%d] %d->%d ",id[fu],id[u],u,fu);

         //printf("%d\n",query(1,id[fu],id[u]));

         ans += query(,id[fu],id[u]);

         if(last_u == -)

         {

             last_u = fu;

             last_u_color = query_edge(,id[fu]);

         }

         else

         {

             if(last_u != - && fa[last_u] == u)

             {

                 //printf("u sub:%d\n",(last_u_color==query_edge(1,id[u]) ? 1 : 0));

                 ans -= (last_u_color==query_edge(,id[u]) ?  : );

                 last_u = fu;

                 last_u_color = query_edge(,id[fu]);

             }

         }

         u = fa[fu];

         fu = top[u];

     }

     if(u == v)

     {

         if(last_u != - && last_v != - && last_u_color==last_v_color) ans -= ;

         return ans;

     }

     if(dep[u] < dep[v])

     {

         swap(u,v);

         swap(last_u,last_v);

         swap(last_u_color,last_v_color);

     }

     //printf("query:[%d,%d] %d->%d ",id[son[v]],id[u],u,son[v]);

     ans += query(,id[son[v] ],id[u]);

     //printf("%d*\n",query(1,id[son[v]],id[u]));

     //printf("last_u:%d last_v:%d\n",last_u,last_v);

     if(last_u != - && fa[last_u] == u)

     {

         //printf("u sub:%d last_u_color:%d u_color:%d\n",(last_u_color==query_edge(1,id[u]) ? 1 : 0),last_u_color,query_edge(1,id[u]));

         ans -= (last_u_color==query_edge(,id[u]) ?  : );

         last_u = fu;

         last_u_color = query_edge(,id[u]);

     }

     if(last_v != - && fa[last_v] == v)

     {

         //printf("v sub:%d last_v_color:%d son[v]_color:%d\n",(last_v_color==query_edge(1,id[son[v]]) ? 1 : 0),last_v_color,query_edge(1,id[son[v]] ));

         ans -= (last_v_color==query_edge(,id[son[v]]) ?  : );

         last_v = fv;

         last_v_color = query_edge(,id[son[v]]);

     }

     return ans;

 }

 void Change(int u,int v,int cost)

 {

     int fu = top[u],fv = top[v];

     //printf("%d->%d\n",u,v);

     while(fu != fv)

     {

         if(dep[fu] < dep[fv])

         {

             swap(fu,fv);swap(u,v);

         }

         //printf("change:[%d,%d] %d->%d %d\n",id[fu],id[u],u,fu,cost);

         update(,id[fu],id[u],cost);

         u = fa[fu];

         fu = top[u];

     }

     if(u == v) return ;

     if(dep[u] < dep[v]) swap(u,v);

     //printf("change:[%d,%d] %d->%d %d\n",id[son[v]],id[u],u,son[u],cost);

     update(,id[son[v]],id[u],cost);

     return ;

 }

 int main()

 {

     //freopen("input","r",stdin);

     while(~scanf("%d%d",&N,&M))

     {

         init();

         int u,v,w;

         for(int i=;i<N;i++)

         {

             scanf("%d%d%d",&u,&v,&w);

             e[i].x = u;e[i].y = v;e[i].val = w;

             G[u].push_back(v);

             G[v].push_back(u);

         }

         topw = ;

         dfs_1(,,);

         dfs_2(,);

         //debug();

         for(int i=;i<N;i++)

         {

             if(dep[e[i].x] < dep[e[i].y]) swap(e[i].x,e[i].y);

             val[id[e[i].x]] = e[i].val;

         }

         Build(,topw,);

         char op[];

         //printf("-----------------\n");

         for(int i=;i<M;i++)

         {

             scanf("%s",op);

             if(op[] == 'Q')

             {

                 scanf("%d%d",&u,&v);

                 printf("%d\n",Find(u,v));

             }

             else

             {

                 scanf("%d%d%d",&u,&v,&w);

                 Change(u,v,w);

             }

             //puts("");

         }

     }

 }
巴特西

2016shenyang-1002-HDU5893-List wants to travel-树链剖分+线段树维护不同区间段个数

最新文章

热门文章
