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

jytnb1的博客

日影斑驳,朽日浮尘;韶光荏苒,逡巡不前。

 
 
 

日志

 
 
关于我

有志者,事竟成,苦心人,天不负。

网易考拉推荐

【bzoj】3531: [Sdoi2014]旅行  

2015-10-16 20:25:19|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
日志的开篇,总要高端一点,然而弱如草芥的我认为能撑得住场面的题目,也许对于神犇来说太水了。【bzoj】3531: [Sdoi2014]旅行 - jytnb1 - jytnb1的博客
我不知道,未来的我心血来潮看完这篇日志时会是什么感受,是觉得很神,还是很水?但愿是后者。
题目链接:BZOJ3531

3531: [Sdoi2014]旅行

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 746  Solved: 391
Description
 S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教,  S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下途中(包括起点和终点)留宿过的城市的评级总和或最大值。
    在S国的历史上常会发生以下几种事件:
”CC x c”:城市x的居民全体改信了c教;
”CW x w”:城市x的评级调整为w;
”QS x y”:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级总和;
”QM x y”:一位旅行者从城市x出发,到城市y,并记下了途中留宿过
的城市的评级最大值。
    由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。    为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。
Input
    输入的第一行包含整数N,Q依次表示城市数和事件数。
    接下来N行,第i+l行两个整数Wi,Ci依次表示记录开始之前,城市i的
评级和信仰。
    接下来N-1行每行两个整数x,y表示一条双向道路。
    接下来Q行,每行一个操作,格式如上所述。
Output
    对每个QS和QM事件,输出一行,表示旅行者记下的数字。
Sample Input
    5 6
    3 1
    2 3
    1 2
    3 3
    5 1
    1 2
    1 3
    3 4
    3 5
    QS 1 5
    CC 3 1
    QS 1 5
    CW 3 3
    QS 1 5
    QM 2 4
Sample Output
    8
    9
    11
    3
HINT
N,Q < =10^5    , C < =10^5
 数据保证对所有QS和QM事件,起点和终点城市的信仰相同;在任意时
刻,城市的评级总是不大于10^4的正整数,且宗教值不大于C。
Source
Round 1 Day 1
===========================================================================
题目其实真的很水,对于每种宗教都开一棵线段树,动态开线段树节点即可。普通的线段树,对于点k,左儿子为2*k,右儿子为2*k+1,动态开节点只是开了个数组储存左右儿子的地址,每次修改到节点时,若节点还没有分配过地址,就新开一个地址。之后就是树剖模板的事了。
===========================================================================
#include<cstdio>
using namespace std;
const int N=100100,M=10001000;
int i,j,k,n,m,En,ch,T_sz,P_sz,x,y,t,fx,fy,ans;
char s[5];
int h[N],w[N],c[N],rt[N];
struct point {int sz,dp,fa,sn,tp,fv;} P[N];
struct edge {int s,n;} E[N<<1];
struct tree {int ls,rs,mx,sm;} T[M];
void R(int &x)
{
x=0;ch=getchar();
while (ch<'0' || '9'<ch) ch=getchar();
while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
}
void E_add(int x,int y)
{
En++;E[En].s=y;
E[En].n=h[x];h[x]=En;
En++;E[En].s=x;
E[En].n=h[y];h[y]=En;
}
void dfs1(int x,int F)
{
int mx=0;
P[x].sz=1;P[x].dp=P[F].dp+1;P[x].fa=F;
for (int k=h[x];k;k=E[k].n) if (E[k].s!=F)
{
dfs1(E[k].s,x);
P[x].sz+=P[E[k].s].sz;
if (P[E[k].s].sz>mx)
{
mx=P[E[k].s].sz;
P[x].sn=E[k].s;
}
}
}
void dfs2(int x,int tp,int F)
{
P[x].fv=++P_sz;P[x].tp=tp;
if (P[x].sn) dfs2(P[x].sn,tp,x);
for (int k=h[x];k;k=E[k].n) if (E[k].s!=F && E[k].s!=P[x].sn) dfs2(E[k].s,E[k].s,x);
}
void up(int k)
{
T[k].sm=T[k].mx=0;
if (T[k].ls)
{
int l=T[k].ls;
if (T[l].mx>T[k].mx) T[k].mx=T[l].mx;
T[k].sm+=T[l].sm;
}
if (T[k].rs)
{
int r=T[k].rs;
if (T[r].mx>T[k].mx) T[k].mx=T[r].mx;
T[k].sm+=T[r].sm;
}
}
void T_change(int L,int R,int x,int w,int &k)
{
if (!k) k=++T_sz;
if (L==R)
{
T[k].sm=T[k].mx=w;
return;
}
int mid=(L+R)>>1;
if (x<=mid) T_change(L,mid,x,w,T[k].ls);
else T_change(mid+1,R,x,w,T[k].rs);
up(k);
}
int T_sum(int L,int R,int l,int r,int k)
{
if (!k) return 0;
if (L==l && R==r) return T[k].sm;
int mid=(L+R)>>1;
if (r<=mid) return T_sum(L,mid,l,r,T[k].ls);
if (l>mid) return T_sum(mid+1,R,l,r,T[k].rs);
return T_sum(L,mid,l,mid,T[k].ls)+T_sum(mid+1,R,mid+1,r,T[k].rs);
}
int T_max(int L,int R,int l,int r,int k)
{
if (!k) return 0;
if (L==l && R==r) return T[k].mx;
int mid=(L+R)>>1;
if (r<=mid) return T_max(L,mid,l,r,T[k].ls);
if (l>mid) return T_max(mid+1,R,l,r,T[k].rs);
int t1=T_max(L,mid,l,mid,T[k].ls),t2=T_max(mid+1,R,mid+1,r,T[k].rs);
if (t1>=t2) return t1;
return t2;
}
int main()
{
R(n);R(m);
for (i=1;i<=n;i++) R(w[i]),R(c[i]);
for (i=1;i<n;i++)
{
R(x);R(y);
E_add(x,y);
}
dfs1(1,0);dfs2(1,1,0);
for (i=1;i<=n;i++) T_change(1,n,P[i].fv,w[i],rt[c[i]]);
for (i=1;i<=m;i++)
{
scanf("%s",s);
if (s[0]=='C')
{
if (s[1]=='C')
{
R(x);R(t);
T_change(1,n,P[x].fv,0,rt[c[x]]);
c[x]=t;
T_change(1,n,P[x].fv,w[x],rt[c[x]]);
}
else
{
R(x);R(w[x]);
T_change(1,n,P[x].fv,w[x],rt[c[x]]);
}
}
else
{
ans=0;
if (s[1]=='S')
{
R(x);R(y);t=rt[c[x]];
fx=P[x].tp;fy=P[y].tp;
while (fx!=fy)
{
if (P[fx].dp>P[fy].dp)
{
ans+=T_sum(1,n,P[fx].fv,P[x].fv,t);
x=P[fx].fa;fx=P[x].tp;
}
else
{
ans+=T_sum(1,n,P[fy].fv,P[y].fv,t);
y=P[fy].fa;fy=P[y].tp;
}
}
if (P[x].dp<=P[y].dp) ans+=T_sum(1,n,P[x].fv,P[y].fv,t);
else ans+=T_sum(1,n,P[y].fv,P[x].fv,t);
}
else
{
R(x);R(y);t=rt[c[x]];
fx=P[x].tp;fy=P[y].tp;
while (fx!=fy)
{
if (P[fx].dp>P[fy].dp)
{
ch=T_max(1,n,P[fx].fv,P[x].fv,t);
if (ch>ans) ans=ch;
x=P[fx].fa;fx=P[x].tp;
}
else
{
ch=T_max(1,n,P[fy].fv,P[y].fv,t);
if (ch>ans) ans=ch;
y=P[fy].fa;fy=P[y].tp;
}
}
if (P[x].dp<=P[y].dp)
{
ch=T_max(1,n,P[x].fv,P[y].fv,t);
if (ch>ans) ans=ch;
}
else
{
ch=T_max(1,n,P[y].fv,P[x].fv,t);
if (ch>ans) ans=ch;
}
}
printf("%d\n",ans);
}
}
}



  评论这张
 
阅读(28)| 评论(12)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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