首页 > 代码库 > cogs1612. 大话西游

cogs1612. 大话西游

1612. 大话西游

http://www.cogs.pro/cogs/problem/problem.php?pid=1612

★★   输入文件:westward.in   输出文件:westward.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

 

“大话西游”是一个在中国非常流行的在线游戏,由NIE公司开发和维护。这个游戏来源于著名的小说《西游记》和周星弛的电影,游戏的背景故事充满奇幻色彩,引人入胜。

游戏里面有很多片区域,不同的区域由不同的统治者管辖,其中有一个地方名叫“树国”,由一个妖怪控制着。这里有N个城堡,每个城堡都有其重要程度值(一个正整数,不超过10^8),这些城堡被N-1条双向道路所连接,任意两个城堡均可互达,城堡的重要程度值是可变的。现在,妖怪想知道如果破坏其中的一条道路会发生什么。本题中,你总共需要处理Q条指令,每一个都具有下面所述的格式:

(1)CHANGE

i w

本指令的含义为:将第i个城堡的重要程度值变为w(1<=w<=10^8)

(2)QUERY

j

本指令的含义为:输出min1*max1+min2*max2的值,详细如下:

第j条道路可以把“树国”分成两个连通块,分别称为part1和part2,其中

min1为part1中的最小重要程度值;

max1为part1中的最大重要程度值;

min2为part2中的最小重要程度值;

max2为part2中的最大重要程度值。

 

【输入格式】

 

第一行有两个整数N(2<=N<=100000)和Q(1<=Q<=100000),分别表示城堡的个数及指令的数目。

 

接下来的一行有N个整数(正整数,不超过10^8),表示起初每一个城堡的重要程度值(城堡的编号为1~N)。

 

接下来有N-1行,每行有两个整数u,v,表示在城堡u和城堡v之间有一条无向边相连,(边的编号依次为1~N-1)。

接下来有Q行,每行有一个指令,格式如下所述。

 

【输出格式】

对于每个"QUERY"指令,在单独一行输出结果。

【样例输入】

5 31 2 3 4 51 22 33 44 5QUERY 1CHANGE 1 10QUERY 1

【样例输出】

11110

维护每个点的dfs序,以此为建线段树的根据。

由于一棵子树上所有点的dfs序都是连续的,所以在查询时只需区间查询即可,这题不涉及边权,所以修改也是普通的单点修改。

只用到了树剖的第一个dfs,为的是求dfs序和子数大小

#include<cstdio>#include<iostream>using namespace std;#define maxn 100010int num,n,q,g,Ev[maxn],fa[maxn],dfn[maxn],id[maxn],head[maxn],point[maxn],sz[maxn];struct node{int to,pre,d;}e[maxn*4];struct Node{int l,r,mn,mx;}tr[maxn*4];void Insert(int from,int to,int d){e[++num].to=to,e[num].d=d;e[num].pre=head[from];head[from]=num;}void dfs(int father,int now){    sz[now]=1;    dfn[now]=++g;    fa[now]=father;    id[g]=now;    for(int i=head[now];i;i=e[i].pre){        int to=e[i].to;        if(to==father)continue;        point[e[i].d]=to;        dfs(now,to);        sz[now]+=sz[to];    }}void up(int k){    tr[k].mn=min(tr[k<<1].mn,tr[(k<<1)|1].mn);    tr[k].mx=max(tr[k<<1].mx,tr[(k<<1)|1].mx);}void build(int l,int r,int k){    tr[k].l=l;tr[k].r=r;    if(tr[k].l==tr[k].r){tr[k].mn=tr[k].mx=Ev[id[l]];return;}    int mid=(l+r)>>1;    build(l,mid,k<<1);build(mid+1,r,(k<<1)|1);    up(k);}int findmax(int l,int r,int k){    if(tr[k].l==l&&tr[k].r==r)return tr[k].mx;    int mid=(tr[k].l+tr[k].r)>>1;    if(r<=mid)return findmax(l,r,k<<1);    else if(l>mid)return findmax(l,r,(k<<1)|1);    else return max(findmax(l,mid,k<<1),findmax(mid+1,r,(k<<1)|1));}int findmin(int l,int r,int k){    if(tr[k].l==l&&tr[k].r==r)return tr[k].mn;    int mid=(tr[k].l+tr[k].r)>>1;    if(r<=mid)return findmin(l,r,k<<1);    else if(l>mid)return findmin(l,r,(k<<1)|1);    else return min(findmin(l,mid,k<<1),findmin(mid+1,r,(k<<1)|1));}void update(int pos,int v,int k){    if(tr[k].l==tr[k].r){tr[k].mn=tr[k].mx=v;return;}    int mid=(tr[k].l+tr[k].r)>>1;    if(pos<=mid)update(pos,v,k<<1);    if(pos>mid)update(pos,v,(k<<1)|1);    up(k);}int main(){    freopen("westward.in","r",stdin);    freopen("westward.out","w",stdout);    //freopen("Cola.txt","r",stdin);    scanf("%d%d",&n,&q);    for(int i=1;i<=n;i++)scanf("%d",&Ev[i]);    int x,y;    for(int i=1;i<n;i++){        scanf("%d%d",&x,&y);        Insert(x,y,i);Insert(y,x,i);    }    dfs(0,1);    build(1,n,1);    char ch[10];    for(int i=1;i<=q;i++){        scanf("%s",&ch);        int a,b;        if(ch[0]==C){            scanf("%d%d",&a,&b);            update(dfn[a],b,1);        }        if(ch[0]==Q){            scanf("%d",&a);            int s=dfn[point[a]],t=s+sz[point[a]]-1;            int max1,max2;int min1,min2;min1=min2=0x7fffffff;            max1=findmax(s,t,1);min1=findmin(s,t,1);            if(s!=1)max2=findmax(1,s-1,1),min2=findmin(1,s-1,1);            if(t!=n) max2=max(max2,findmax(t+1,n,1)),min2=min(min2,findmin(t+1,n,1));            //int ans=min1*max1+min2*max2;            printf("%lld\n",(long long)min1*(long long)max1+(long long)min2*(long long)max2);        }    }    return 0;}

 

cogs1612. 大话西游