1103: 插线板
时间限制: 1 Sec 内存限制: 128 MB
提交: 14 解决: 7
题目描述
从前有一堆古老的插线板，任意两个插线板之间只有一根导线相连，最终形成一个树状结构。我们假设电线的电阻可以忽略。由于年代久远，插线板的状况不容乐观。每个插线板都对电流有一定的影响，用一个整数表示，若为正，表示对电流起到稳定作用，越大越稳定，若为负，代表对电流产生不好的影响。插线板在连接后。这种影响会叠加，比如a和b连接，a的影响为-1，b为3，则a到b的影响为2。现在提供操作1和2，操作1表示求出插线板a到插线板b之间对电流影响最为乐观的一段的影响数值。(注：数据有问题，这一段元素可以为空）即将a到b的这条“链”取出，形成一个关于影响的序列，这个序列的最大子段和。操作2表示将a到b的链上所有插线板对电流的影响改为一个数值(包括a和b)。现给出插线板的初始状况，请按照要求进行操作，输出结果。
输入
单组测试数据
第一行为插线板个数n。
第二行为插线板1到n初始状态对电流的影响数值。（数值绝对值不超过10000）
第三行开始有n-1行，每行两个数a和b，表示a、b有电线连接，保证形成一棵树。
之后一行有一个正整数m，代表操作个数。
最后m行，每行第一个数为1或2，代表操作种类，若为1，后面跟随两个数l和r，代表求出l和r之间的最好影响数值。若为2，后面跟随三个数l、r和c，代表修改l到r的插线板的影响为c。
输出
对每个操作1输出一个整数，代表最好影响数值，每个输出用一个空格隔开。
样例输入
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
样例输出
5 9
提示
n,m<=100000
来源
emm这题卡了我好久。。。
由于我校oj的数据贼弱。。暴力就可以过，甚至比我写的o(log(n)^2*n)还快。
暴力的做法就是对于题目所说的点求最近公共祖先（Tarjan+并查集,欧拉序列+st，求2^k的祖先然后不断向上找公共祖先），然后修改的时候把所有点逐个修改，求值的时候把所有点拿出来，求前缀和，维护最小值搞一下就好了。
学长的博客链接做法：http://www.cnblogs.com/neopenx/p/4503066.html ，暴力法。
#include "cstdio"
#include "cstring"
#include "vector"
#include "algorithm"
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
int head[maxn],qhead[maxn],lag[maxn],kth[maxn],tot1,tot2,f[maxn],vis[maxn],ancestor[maxn],p[maxn],s1[maxn],s2[maxn];
bool isUpdate[maxn];
struct Edge
{
int to,next;
}e[maxn*];
struct Query
{
int from,to,next,idx,c;
}q[maxn*];
void addedge(int u,int v)
{
e[tot1].to=v;
e[tot1].next=head[u];
head[u]=tot1++;
}
void addquery(int u,int v,int idx,int c=inf)
{
q[tot2].from=u;
q[tot2].to=v;
q[tot2].next=qhead[u];
q[tot2].idx=idx;
if(c!=inf) q[tot2].c=c;
qhead[u]=tot2++;
}
int find(int x) {return x!=f[x]?f[x]=find(f[x]):x;}
void Union(int u,int v)
{
u=find(u),v=find(v);
if(u!=v) f[v]=u;
}
void LCA(int u)
{
vis[u]=true;
f[u]=u;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
p[v]=u;
LCA(v);
Union(u,v);
}
}
for(int i=qhead[u];i!=-;i=q[i].next)
{
int v=q[i].to;
if(vis[v]) ancestor[q[i].idx]=find(v);
//or storage e[i].lca=e[i^1].lca=find(v)
}
}
int sum(int num)
{
s2[]=s1[];
int Max=,Min=;
for(int i=; i<num; i++)
s2[i]=s2[i-]+s1[i];
for(int i=;i<num;i++)
{
Min=min(Min,s2[i]);
Max=max(Max,s2[i]-Min);
}
return Max;
}
int main()
{
//freopen("in.txt","r",stdin);
int T,n,m,u,v,c,cmd,qcnt=;
scanf("%d",&n);
tot1=tot2=;
memset(head,-,sizeof(head));
memset(qhead,-,sizeof(qhead));
memset(vis,,sizeof(vis));
memset(isUpdate,,sizeof(isUpdate));
for(int i=;i<=n;i++) scanf("%d",&lag[i]);
for(int i=; i<n-; i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
scanf("%d",&m);
for(int i=; i<m; i++)
{
scanf("%d",&cmd);
if(cmd==)
{
scanf("%d%d%d",&u,&v,&c);
addquery(u,v,i,c);
addquery(v,u,i,c);
isUpdate[i]=true;
}
else
{
scanf("%d%d",&u,&v);
addquery(u,v,i);
addquery(v,u,i);
}
}
LCA();
vector<int> ans;
for(int i=; i<tot2; i=i+)
{
int u=q[i].from,v=q[i].to,idx=q[i].idx;
int ed=ancestor[idx],cnt=;
if(isUpdate[qcnt])
{
int c=q[i].c;
while(u!=ed) lag[u]=c,u=p[u];
lag[ed]=c;
while(v!=ed) lag[v]=c,v=p[v];
}
else
{
while(u!=ed) s1[cnt++]=lag[u],u=p[u];
s1[cnt++]=lag[ed];
vector<int> rev;
while(v!=ed) rev.push_back(lag[v]),v=p[v];
for(int j=rev.size()-; j>=; j--) s1[cnt++]=rev[j];
int x=sum(cnt);
ans.push_back(x);
}
qcnt++;
}
for(int i=;i<ans.size()-;i++) printf("%d ",ans[i]);
printf("%d\n",ans[ans.size()-]);
}
然后我的做法是经典的线段树求区间最大子段和的做法，维护包含区间左端点的最大值lt,右端点的最大值rt，区间内最大值in，以及区间总和all。但是题目给的是一棵树，我们把它树链刨分以后再把一段一段地求前述四个值并合并。然后找到合并后的最大值即为答案。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define mod 1000000007
#define LL long long
using namespace std;
const int N=1e4+;
struct edg
{
int next,to;
}edge[N<<];
int head[N],etot;
void addedge(int u,int v)
{
edge[++etot]=(edg){head[u],v};
head[u]=etot;
return ;
}
int fro[N],bac[N],dep[N],fa[N],val[N],top[N],clk,tsize[N],son[N],dfn[N];
struct node
{
int l,r,tag,lt,rt,in,all;
}tree[N<<];
int n,m,k,u,v,c,op;
void init()
{
etot=;
clk=;
clr_1(head);
dep[]=;
fa[]=;
return ;
}
void dfs1(int u)
{
top[u]=u;
tsize[u]=;
son[u]=;
int p;
for(int i=head[u];i!=-;i=edge[i].next)
{
p=edge[i].to;
if(p!=fa[u])
{
fa[p]=u;
dep[p]=dep[u]+;
dfs1(p);
tsize[u]+=tsize[p];
if(!son[u] || tsize[p]>tsize[son[u]] )
son[u]=p;
}
}
return ;
}
void dfs2(int u)
{
fro[u]=++clk;
dfn[clk]=u;
int p;
if(son[u])
{
top[son[u]]=top[u];
dfs2(son[u]);
}
for(int i=head[u];i!=-;i=edge[i].next)
{
p=edge[i].to;
if(p!=fa[u] && p!=son[u])
dfs2(p);
}
bac[u]=clk;
return ;
}
void pushup(int i)
{
tree[i].all=tree[i<<].all+tree[i<<|].all;
tree[i].lt=max(max(tree[i<<].lt,tree[i<<].all+tree[i<<|].lt),tree[i].all);
tree[i].rt=max(max(tree[i<<|].rt,tree[i<<|].all+tree[i<<].rt),tree[i].all);
tree[i].in=max(max(tree[i<<].in,tree[i<<|].in),tree[i<<].rt+tree[i<<|].lt);
return ;
}
void pushdown(int i)
{
if(tree[i].tag!=INF)
{
if(tree[i].l!=tree[i].r)
{
tree[i<<].tag=tree[i].tag;
tree[i<<].all=(tree[i<<].r-tree[i<<].l+)*tree[i<<].tag;
tree[i<<].lt=tree[i<<].rt=tree[i<<].in=(tree[i<<].tag>=?tree[i<<].all:tree[i<<].tag);
tree[i<<|].tag=tree[i].tag;
tree[i<<|].all=(tree[i<<|].r-tree[i<<|].l+)*tree[i<<|].tag;
tree[i<<|].lt=tree[i<<|].rt=tree[i<<|].in=(tree[i<<|].tag>=?tree[i<<|].all:tree[i<<|].tag);
}
tree[i].tag=INF;
}
return ;
}
void init(int i,int l,int r)
{
tree[i]=(node){l,r,INF};
if(l==r)
{
tree[i].lt=tree[i].rt=tree[i].in=tree[i].all=val[dfn[l]];
return ;
}
int mid=(l+r)>>;
init(i<<,l,mid);
init(i<<|,mid+,r);
pushup(i);
return ;
}
void update(int i,int l,int r,int c)
{
if(tree[i].l>=l && tree[i].r<=r)
{
tree[i].all=(tree[i].r-tree[i].l+)*c;
tree[i].lt=tree[i].rt=tree[i].in=(c>=?tree[i].all:c);
tree[i].tag=c;
return ;
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>;
if(l<=mid)
update(i<<,l,r,c);
if(r>mid)
update(i<<|,l,r,c);
pushup(i);
return ;
}
node query(int i,int l,int r)
{
if(tree[i].l>=l && tree[i].r<=r)
return tree[i];
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>;
if(l>mid)
return query(i<<|,l,r);
else if(r<=mid)
return query(i<<,l,r);
else
{
node tmplt=query(i<<,l,r),tmprt=query(i<<|,l,r);
node tmp;
tmp.all=tmplt.all+tmprt.all;
tmp.lt=max(max(tmplt.lt,tmplt.all+tmprt.lt),tmp.all);
tmp.rt=max(max(tmprt.rt,tmprt.all+tmplt.rt),tmp.all);
tmp.in=max(max(tmplt.in,tmprt.in),tmplt.rt+tmprt.lt);
return tmp;
}
}
void tupdate(int u,int v,int c)
{
int tpu=top[u],tpv=top[v];
while(tpu!=tpv)
{
if(dep[tpu]<dep[tpv])
{
swap(u,v);
swap(tpu,tpv);
}
update(,fro[tpu],fro[u],c);
u=fa[tpu];
tpu=top[u];
}
if(dep[u]<dep[v])
swap(u,v);
update(,fro[v],fro[u],c);
return ;
}
int tquery(int u,int v)
{
int tpu=top[u],tpv=top[v];
node tmp[];
clr(tmp);
bool flag[]={,};
int now=;
node tmpn,tp;
int ans=;
while(tpu!=tpv)
{
if(dep[tpu]<dep[tpv])
{
swap(u,v);
swap(tpu,tpv);
now^=;
}
tmpn=query(,fro[tpu],fro[u]);
if(!flag[now])
{
tmp[now]=tmpn;
flag[now]=;
}
else
{
tp.all=tmp[now].all+tmpn.all;
tp.lt=max(max(tmpn.lt,tmpn.all+tmp[now].lt),tp.all);
tp.rt=max(max(tmp[now].rt,tmp[now].all+tmpn.rt),tp.all);
tp.in=max(max(tmp[now].in,tmpn.in),tmpn.rt+tmp[now].lt);
tmp[now]=tp;
}
u=fa[tpu];
tpu=top[u];
}
if(dep[u]<dep[v])
swap(u,v),now^=;
tmpn=query(,fro[v],fro[u]);
if(flag[now])
{
tp.all=tmp[now].all+tmpn.all;
tp.lt=max(max(tmpn.lt,tmpn.all+tmp[now].lt),tp.all);
tp.rt=max(max(tmp[now].rt,tmp[now].all+tmpn.rt),tp.all);
tp.in=max(max(tmp[now].in,tmpn.in),tmpn.rt+tmp[now].lt);
tmpn=tp;
}
if(flag[now^])
{
tp.in=max(max(tmp[now^].in,tmpn.in),tmpn.lt+tmp[now^].lt);
tmpn=tp;
}
return tmpn.in;
}
int main()
{
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&val[i]);
for(int i=;i<=n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs1();
dfs2();
init(,,n);
scanf("%d",&m);
bool inf=;
for(int i=;i<=m;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&u,&v);
if(!inf)
{
inf=;
printf("%d",max(tquery(u,v),));
}
else printf(" %d",max(tquery(u,v),));
}
else
{
scanf("%d%d%d",&u,&v,&c);
tupdate(u,v,c);
}
}
printf("\n");
return ;
}
所以。。暴力出奇迹？