注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj3531】【Sdoi2014】【旅行】  

2014-04-30 14:21:09|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:一棵点带权的树,每一个点都有一个种类,然后有以下四个操作:
   1】修改某个点的点权。
   2】修改某个点的种类。
   3】询问u,v(保证u,v种类相同)路径上的所有相同的种类的点的点权和。
   4】询问u,v(保证u,v种类相同)路径上的所有相同的种类的点的最大点权。
   点数n<=10^5,操作数Q<=10^5。

   0.0一种做法比较好想...就是对于每一种种类的修改和询问都分离出来,然后每一种种类分开回答【即离线】,这个只需要树链剖分一次即可,然后枚举种类进行做,然后转化到新的种类的时候对之前所有修改过种类的点全部都改成0即可。
   然后还有一种是树链剖分然后树套树【ydc君的想法】【支持在线的?】,0.0咱yy的话会不会是对于树链的每一部分建立一棵不旋转的完全二叉树,然后每一个节点指向一棵平衡树【好吧咱这样乱yy够了...】,这种咱肯定不会额...
   然后还有一种名叫树链剖分套主席树0.0,【应该也是在线的?】咱们来yy一下...就是离散化之后对于每一个叶子维护一个sum和max? 0.0表示还是肯定不会额...
   咱竟然还看到了第四种做法...维护10万棵线段树233...= =
 
   所以弱弱的咱就只会写第一种算法去了...= =
   实际上就是准备去复习树链剖分的= =

   然后咱们一开始先用记录体表示读入的每一个操作,然后模拟,就可以把每一类询问所在的种类分好类。
   为了分类咱们只需要处理出每一个操作所涉及的宗教种类即可。
   关于修改,对于修改点权w,咱们直接把这个操作的宗教变成被修改点的宗教。对于修改宗教c,咱们把这个修改拆成两个操作,一个表示删除一个点权为w的点,一个表示插入一个点权为w的点,宗教标为修改前的宗教和修改后的宗教。
   对于询问,咱们把每一个操作标记为询问的两个点的宗教即可。
   然后以每一个操作的宗教为关键字快排一遍就可以分离出来了【对于询问推荐再记录一个这个询问是第几个】
 
   然后每一次计算新的宗教初始化的时候咱是直接用一个队列记录上一个宗教所涉及到的点,然后对队列里的所有点初始化点权为0,这个貌似是不会超过复杂度的。
   然后加入队列的时候傻叉了一下...少加入了一些点。WA两次。
==========================

program bzoj3531;
{$M 5000000}
const maxn=400010;
type edge=record
     v,w,pre:longint;
     end;
     node=record
     l,r,a,b,max:longint;
     sum:int64;
     end;
     th=record
     ty,u,v,w,c,bh,time:longint;
     end;

var e:array[0..maxn shl 1]of edge;
    t:array[0..maxn shl 1]of node;
    eve:array[0..maxn shl 1]of th;
    last,w,ww,c,cc,fa,
    size,son,id,top,dep,root:array[0..maxn]of longint;
    n,q,ln,tot,tt:longint;
    anss:int64;
    ans:array[0..maxn]of int64;
    que:array[0..maxn shl 1]of longint;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

procedure addedge(u,v:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].pre:=last[v];last[v]:=tot;
end;

procedure addedge(u,v,w:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].w:=w;e[tot].pre:=last[u];last[u]:=tot;
end;

procedure build(l,r:longint);
var now,mid:longint;
begin
  inc(tot);now:=tot;
  t[now].a:=l;t[now].b:=r;
  t[now].sum:=0;t[now].max:=0;
  if l+1<r then
   begin
     mid:=(l+r)shr 1;
     t[now].l:=tot+1;build(l,mid);
     t[now].r:=tot+1;build(mid,r);
   end;
end;

procedure maintain(x:longint);
begin
  t[x].sum:=t[t[x].l].sum+t[t[x].r].sum;
  t[x].max:=max(t[t[x].l].max,t[t[x].r].max);
end;

procedure query(l,r,x,c:longint);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
   begin
     if c=0 then anss:=anss+t[x].sum
            else anss:=max(anss,t[x].max);
     exit;
   end;
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then query(l,r,t[x].l,c);
  if mid<r then query(l,r,t[x].r,c);
end;

procedure insert(l,r,x,c:longint);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
   begin
     t[x].sum:=c;
     t[x].max:=c;
     exit;
   end;
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then insert(l,r,t[x].l,c);
  if mid<r then insert(l,r,t[x].r,c);
  maintain(x);
end;

procedure dfs(p:longint);
var tmp:longint;
begin
  tmp:=last[p];
  size[p]:=1;
  while tmp<>0 do
   begin
     if e[tmp].v<>fa[p] then
      begin
        fa[e[tmp].v]:=p;
        dep[e[tmp].v]:=dep[p]+1;
        dfs(e[tmp].v);
        size[p]:=size[p]+size[e[tmp].v];
        if size[son[p]]<size[e[tmp].v] then son[p]:=e[tmp].v;
      end;
     tmp:=e[tmp].pre;
   end;
end;

procedure dfs(p,u:longint);
var tmp:longint;
begin
  id[p]:=ln+1;
  if son[p]=0 then
   begin
     inc(ln);
     top[ln]:=u;
     root[ln]:=tot+1;
     build(dep[u]-1,dep[p]);
   end
  else dfs(son[p],u);
  tmp:=last[p];
  while tmp<>0 do
   begin
     if (e[tmp].v<>fa[p])and(e[tmp].v<>son[p]) then
      dfs(e[tmp].v,e[tmp].v);
     tmp:=e[tmp].pre;
   end;
end;

procedure qsort(l,r:longint;flag:boolean);
var i,j,x:longint;y:th;
begin
  i:=l;j:=r;
  if flag then x:=eve[(l+r)shr 1].c
          else x:=eve[(l+r)shr 1].time;
  repeat
    if flag then while eve[i].c<x do inc(i)
            else while eve[i].time<x do inc(i);
    if flag then while eve[j].c>x do dec(j)
            else while eve[j].time>x do dec(j);
    if i<=j then
     begin
       y:=eve[i];eve[i]:=eve[j];eve[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r,flag);
  if j>l then qsort(l,j,flag);
end;

procedure ask(u,v,c:longint);
var ttt:longint;
begin
  anss:=0;
  while id[u]<>id[v] do
   begin
     if id[u]<id[v] then
      begin
        ttt:=u;u:=v;v:=ttt;
      end;
     query(dep[top[id[u]]]-1,dep[u],root[id[u]],c);
     u:=fa[top[id[u]]];
   end;
  if dep[u]>dep[v] then
   begin
     ttt:=u;u:=v;v:=ttt;
   end;
  query(dep[u]-1,dep[v],root[id[u]],c);
end;

procedure init;
var i,j,u,v,st,tmp,ll,rr:longint;
    ch1,ch2:char;
begin
  readln(n,q);
  for i:=1 to n do
   begin
    readln(w[i],c[i]);
    cc[i]:=c[i];
    ww[i]:=w[i];
   end;
  tot:=0;
  fillchar(last,sizeof(last),0);
  for i:=1 to n-1 do
   begin
     readln(u,v);
     addedge(u,v);
   end;
  fa[1]:=0;dep[1]:=1;tot:=0;ln:=0;
  fillchar(size,sizeof(size),0);
  fillchar(son,sizeof(son),0);
  fillchar(top,sizeof(top),0);
  fillchar(id,sizeof(id),0);
  dfs(1);
  dfs(1,1);
  tot:=0;tt:=0;
  for i:=1 to q do
   begin
     read(ch1,ch2);
     readln(u,v);
     if ch1+ch2='CC' then
      begin
        inc(tot);
        eve[tot].ty:=1;
        eve[tot].u:=u;
        eve[tot].c:=cc[u];
        eve[tot].w:=0;
        eve[tot].time:=tot;
        inc(tot);
        eve[tot].ty:=0;
        eve[tot].u:=u;
        eve[tot].c:=v;
        eve[tot].w:=ww[u];
        eve[tot].time:=tot;
        cc[u]:=v;
      end;
     if ch1+ch2='CW' then
      begin
        inc(tot);
        eve[tot].ty:=2;
        eve[tot].w:=v;
        eve[tot].u:=u;
        eve[tot].c:=cc[u];
        eve[tot].time:=tot;
        ww[u]:=v;
      end;
     if ch1+ch2='QS' then
      begin
        inc(tot);
        eve[tot].ty:=3;
        eve[tot].u:=u;
        eve[tot].v:=v;
        eve[tot].c:=cc[u];
        inc(tt);
        eve[tot].bh:=tt;
        eve[tot].time:=tot;
      end;
     if ch1+ch2='QM' then
      begin
        inc(tot);
        eve[tot].ty:=4;
        eve[tot].u:=u;
        eve[tot].v:=v;
        eve[tot].c:=cc[u];
        inc(tt);
        eve[tot].bh:=tt;
        eve[tot].time:=tot;
      end;
   end;
  qsort(1,tot,true);
  st:=1;q:=tot;tot:=0;
  fillchar(que,sizeof(que),0);
  fillchar(last,sizeof(last),0);
  for i:=1 to n do addedge(c[i],i,w[i]);
  for i:=1 to q do
   begin
     if (i=q)or(eve[i].c<>eve[i+1].c) then
      begin
        qsort(st,i,false);
        tmp:=last[eve[i].c];
        ll:=0;rr:=0;
        while tmp<>0 do
         begin
           insert(dep[e[tmp].v]-1,dep[e[tmp].v],root[id[e[tmp].v]],e[tmp].w);
           que[rr]:=e[tmp].v;
           inc(rr);
           tmp:=e[tmp].pre;
         end;
        for j:=st to i do
         case eve[j].ty of
         2:begin
             insert(dep[eve[j].u]-1,dep[eve[j].u],root[id[eve[j].u]],eve[j].w);
           end;
         4:begin
             ask(eve[j].u,eve[j].v,1);
             ans[eve[j].bh]:=anss;
           end;
         3:begin
             ask(eve[j].u,eve[j].v,0);
             ans[eve[j].bh]:=anss;
           end;
         0:begin
             insert(dep[eve[j].u]-1,dep[eve[j].u],root[id[eve[j].u]],eve[j].w);
             que[rr]:=eve[j].u;
             inc(rr);
           end;
         1:begin
             insert(dep[eve[j].u]-1,dep[eve[j].u],root[id[eve[j].u]],0);
           end;
         end;
        for j:=ll to rr-1 do
          insert(dep[que[j]]-1,dep[que[j]],root[id[que[j]]],0);
        st:=i+1;
      end;
   end;
  for i:=1 to tt do
   writeln(ans[i]);
end;

begin
  init;
end.


  评论这张
 
阅读(64)| 评论(6)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017