「BZOJ3531」[SDOI2014] 旅行

2014年6月13日6,9403

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。

题解

因为宗教数量只有10^5，我们可以树链剖分完对于每一个宗教建立线段树，然后就是打码的问题了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#define M 10000005
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,place,size;
int s[17];
int w[100005],c[100005],root[100005];
int fa[100005][17],deep[100005],pl[100005],belong[100005],son[100005];
int ls[M],rs[M],mx[M],sum[M];
bool vis[100005];
struct data{int to,next;}e[200005];int head[100005];
void ins(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
//==========================================================
void dfs1(int x)
{
    vis[x]=1;son[x]=1;
    for(int i=1;i<=16;i++)
        if(s[i]<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];
        else break;
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to])continue;
        deep[e[i].to]=deep[x]+1;
        fa[e[i].to][0]=x;
        dfs1(e[i].to);
        son[x]+=son[e[i].to];
    }
}
void dfs2(int x,int chain)
{
    place++;pl[x]=place;belong[x]=chain;
    int k=0;
    for(int i=head[x];i;i=e[i].next)
        if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k])
            k=e[i].to;
    if(k)dfs2(k,chain);
    for(int i=head[x];i;i=e[i].next)
        if(deep[e[i].to]>deep[x]&&e[i].to!=k)
            dfs2(e[i].to,e[i].to); 
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;i<=16;i++)
        if(s[i]&t)x=fa[x][i];
    for(int i=16;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
//===========================================================预处理 
void update(int x)
{
    mx[x]=max(mx[ls[x]],mx[rs[x]]);
    sum[x]=sum[ls[x]]+sum[rs[x]]; 
}
void change(int &k,int l,int r,int x,int num)
{
    if(!k)k=++size;
    if(l==r){mx[k]=sum[k]=num;return;}
    int mid=(l+r)>>1;
    if(x<=mid)change(ls[k],l,mid,x,num);
    else change(rs[k],mid+1,r,x,num);
    update(k);
}
int askmx(int k,int l,int r,int x,int y)
{
    if(!k)return 0;
    if(l==x&&y==r)return mx[k];
    int mid=(l+r)>>1;
    if(y<=mid)return askmx(ls[k],l,mid,x,y);
    else if(x>mid)return askmx(rs[k],mid+1,r,x,y);
    else return max(askmx(ls[k],l,mid,x,mid),askmx(rs[k],mid+1,r,mid+1,y));
}
int asksum(int k,int l,int r,int x,int y)
{
    if(!k)return 0;
    if(l==x&&y==r)return sum[k];
    int mid=(l+r)>>1;
    if(y<=mid)return asksum(ls[k],l,mid,x,y);
    else if(x>mid)return asksum(rs[k],mid+1,r,x,y);
    else return asksum(ls[k],l,mid,x,mid)+asksum(rs[k],mid+1,r,mid+1,y);
}
//===========================================================线段树
int solvemx(int c,int x,int f)
{
    int mx=0;
    while(belong[x]!=belong[f])
    {
        mx=max(mx,askmx(root[c],1,n,pl[belong[x]],pl[x]));
        x=fa[belong[x]][0];
    }
    mx=max(mx,askmx(root[c],1,n,pl[f],pl[x]));
    return mx;
}
int solvesum(int c,int x,int f)
{
    int sum=0;
    while(belong[x]!=belong[f])
    {
        sum+=asksum(root[c],1,n,pl[belong[x]],pl[x]);
        x=fa[belong[x]][0];
    }
    sum+=asksum(root[c],1,n,pl[f],pl[x]);
    return sum;
}
//===========================================================树链剖分 
int main()
{
    s[0]=1;for(int i=1;i<=16;i++)s[i]=(s[i-1]<<1);
    n=read();m=read();
    for(int i=1;i<=n;i++)
        w[i]=read(),c[i]=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        ins(u,v);
    }
    dfs1(1);dfs2(1,1);
    for(int i=1;i<=n;i++)
        change(root[c[i]],1,n,pl[i],w[i]);
    for(int i=1;i<=m;i++)
    {
        char ch[5];scanf("%s",ch);
        int x=read(),y=read();
        if(ch[0]=='C')
        {
            if(ch[1]=='C')
            {
                change(root[c[x]],1,n,pl[x],0);
                c[x]=y;
                change(root[c[x]],1,n,pl[x],w[x]);
            }
            else {change(root[c[x]],1,n,pl[x],y);w[x]=y;}
        }
        else
        {
            int f=lca(x,y);
            if(ch[1]=='S')
            {
                int t=solvesum(c[x],x,f)+solvesum(c[x],y,f);
                if(c[x]==c[f])t-=w[f];
                printf("%d\n",t);
            }
            else
                printf("%d\n",max(solvemx(c[x],x,f),solvemx(c[x],y,f)));
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

#include<iostream>

#include<cstdio>

#include<cstring>

#define M 10000005

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt,place,size;

int s[17];

int w[100005],c[100005],root[100005];

int fa[100005][17],deep[100005],pl[100005],belong[100005],son[100005];

int ls[M],rs[M],mx[M],sum[M];

bool vis[100005];

struct data{int to,next;}e[200005];int head[100005];

void ins(int u,int v)

{

e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;

}

//==========================================================

void dfs1(int x)

{

vis[x]=1;son[x]=1;

for(int i=1;i<=16;i++)

if(s[i]<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];

else break;

for(int i=head[x];i;i=e[i].next)

{

if(vis[e[i].to])continue;

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

dfs1(e[i].to);

son[x]+=son[e[i].to];

}

void dfs2(int x,int chain)

{

place++;pl[x]=place;belong[x]=chain;

int k=0;

for(int i=head[x];i;i=e[i].next)

if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k])

k=e[i].to;

if(k)dfs2(k,chain);

for(int i=head[x];i;i=e[i].next)

if(deep[e[i].to]>deep[x]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=16;i++)

if(s[i]&t)x=fa[x][i];

for(int i=16;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

//===========================================================预处理

void update(int x)

{

mx[x]=max(mx[ls[x]],mx[rs[x]]);

sum[x]=sum[ls[x]]+sum[rs[x]];

}

void change(int &k,int l,int r,int x,int num)

{

if(!k)k=++size;

if(l==r){mx[k]=sum[k]=num;return;}

int mid=(l+r)>>1;

if(x<=mid)change(ls[k],l,mid,x,num);

else change(rs[k],mid+1,r,x,num);

update(k);

}

int askmx(int k,int l,int r,int x,int y)

{

if(!k)return 0;

if(l==x&&y==r)return mx[k];

int mid=(l+r)>>1;

if(y<=mid)return askmx(ls[k],l,mid,x,y);

else if(x>mid)return askmx(rs[k],mid+1,r,x,y);

else return max(askmx(ls[k],l,mid,x,mid),askmx(rs[k],mid+1,r,mid+1,y));

}

int asksum(int k,int l,int r,int x,int y)

{

if(!k)return 0;

if(l==x&&y==r)return sum[k];

int mid=(l+r)>>1;

if(y<=mid)return asksum(ls[k],l,mid,x,y);

else if(x>mid)return asksum(rs[k],mid+1,r,x,y);

else return asksum(ls[k],l,mid,x,mid)+asksum(rs[k],mid+1,r,mid+1,y);

}

//===========================================================线段树

int solvemx(int c,int x,int f)

{

int mx=0;

while(belong[x]!=belong[f])

{

mx=max(mx,askmx(root[c],1,n,pl[belong[x]],pl[x]));

x=fa[belong[x]][0];

}

mx=max(mx,askmx(root[c],1,n,pl[f],pl[x]));

return mx;

}

int solvesum(int c,int x,int f)

{

int sum=0;

while(belong[x]!=belong[f])

{

sum+=asksum(root[c],1,n,pl[belong[x]],pl[x]);

x=fa[belong[x]][0];

}

sum+=asksum(root[c],1,n,pl[f],pl[x]);

return sum;

}

//===========================================================树链剖分

int main()

{

s[0]=1;for(int i=1;i<=16;i++)s[i]=(s[i-1]<<1);

n=read();m=read();

for(int i=1;i<=n;i++)

w[i]=read(),c[i]=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read();

ins(u,v);

}

dfs1(1);dfs2(1,1);

for(int i=1;i<=n;i++)

change(root[c[i]],1,n,pl[i],w[i]);

for(int i=1;i<=m;i++)

{

char ch[5];scanf("%s",ch);

int x=read(),y=read();

if(ch[0]=='C')

{

if(ch[1]=='C')

{

change(root[c[x]],1,n,pl[x],0);

c[x]=y;

change(root[c[x]],1,n,pl[x],w[x]);

}

else {change(root[c[x]],1,n,pl[x],y);w[x]=y;}

}

else

{

int f=lca(x,y);

if(ch[1]=='S')

{

int t=solvesum(c[x],x,f)+solvesum(c[x],y,f);

if(c[x]==c[f])t-=w[f];

printf("%d\n",t);

}

else

printf("%d\n",max(solvemx(c[x],x,f),solvemx(c[x],y,f)));

}

return 0;

}

« 「BZOJ1651」[Usaco2006 Feb] Stall Reservations 专用牛棚「BZOJ1146」[CTSC2008] 网络管理Network »

zsO HZWER Orz

多棵线段树挤一起，跟主席树好像啊忽然觉得

- 慕°

我也觉得。。就是类似主席树一样省空间的。。

蒟蒻晚辈

黄学长的树链剖分写得很清晰，晚辈正在学这个，受教！

hzwer.com _ Home | http://hzwer.com

「BZOJ3531」[SDOI2014] 旅行

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论