【GDOI 2016 Day1】第四题 疯狂动物城 题解+代码

2024-05-29 03:32

本文主要是介绍【GDOI 2016 Day1】第四题 疯狂动物城 题解+代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我恨码农题!!!
另外,这题可以当做可持久化线段树与树链剖分的模板题

题目大意

一棵树,三个操作
1、从X到Y的路径上每个点的权值加Z
2、查询X到Y的一些神奇东西
3、将树回复到第X次操作后的状态

输入

第一行n,m。n个点,m个操作
接下来n-1行每行两个数表示X连到Y
接下来一行n个数:每个点的初始权值
接下来M行对应上面的三种操作(其中X和Y要亦或上次的答案)

题解

deep[i]表示深度,a[i]为i的权值
其中有40% 的数据是一条链,其中的20%没有操作3,从这里开始。
简化一下求得一个东西,可以发现,在X到Y中一个点的贡献为:
第一部分:从X到lca
设点i到Y的距离为S,则 s=deep[i]+deep[y]2deep[lca] ,这个点对答案的贡献为 a[i]s(s+1)/2 ,先忽略 /2 ,设 T=deep[y]2deep[lca] ,贡献就变成了 a[i]deep[i]2+a[i]deep[i](2t+1)+a[i](t+t2)
第二部分:从lca到Y
s=deep[y]deep[i] ,贡献相同,那么 T=deep[y] ,贡献为 a[i]deep[i]2a[i]deep[i](2t+1)+a[i](t+t2)
那么只需要用线段树维护 a[i]deep[i]2 , a[i]deep[i] , a[i] ,即可。最后答案记得/2。
对于另外20%的数据,操作3:加上可持久化
对于其他的数据:由一条链变成一棵树:树链剖分

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 101000
#define ll long long
#define mo 20160501
#define ny 10080251
using namespace std;
struct note{int l,r;ll a,adf,ad,d,df,lz;
};
note tree[N*70];
int n,g[N],last[N*10],next[N*10],to[N*10],son[N],top[N],dfn[N],fdn[N],size[N],fa[N],tot=1,tt=0,t,totot=0,tn=0,f[N][18];
ll ans,deep[N],a[N];
void putin(int x,int y)
{next[++totot]=last[x];last[x]=totot;to[totot]=y;
}
void dg1(int x)
{size[x]=1;int jy=0;for(int i=last[x];i;i=next[i]){if (deep[to[i]]!=0) continue;deep[to[i]]=deep[x]+1;fa[to[i]]=x;dg1(to[i]);if (size[to[i]]>jy) son[x]=to[i],jy=size[to[i]];size[x]+=size[to[i]];}
}
void dg2(int x,int y)
{dfn[x]=++totot;fdn[totot]=x;if (son[x]) top[son[x]]=top[x],dg2(son[x],x);for(int i=last[x];i;i=next[i]){if (to[i]==son[x] || to[i]==y) continue;top[to[i]]=to[i];dg2(to[i],x);}
}
void build(int v,int i,int j)
{if (i==j) {ll k=fdn[i];tree[v].a=a[k];tree[v].ad=(a[k]*deep[k])% mo;tree[v].adf=(a[k]*deep[k]*deep[k])% mo;tree[v].d=deep[k];tree[v].df=(deep[k]*deep[k])% mo;return;}int mid=(i+j)/2;tree[v].l=++tot;build(tot,i,mid);tree[v].r=++tot;build(tot,mid+1,j);tree[v].a=(tree[tree[v].l].a+tree[tree[v].r].a)%mo;tree[v].ad=(tree[tree[v].l].ad+tree[tree[v].r].ad)%mo;tree[v].adf=(tree[tree[v].l].adf+tree[tree[v].r].adf)%mo;tree[v].d=(tree[tree[v].l].d+tree[tree[v].r].d)%mo;tree[v].df=(tree[tree[v].l].df+tree[tree[v].r].df)%mo;
}
void down(int v,int i,int j)
{if (i==j) {tree[v].lz=0;return;}ll mid=(i+j)/2;ll z=tree[v].lz;tree[++tot]=tree[tree[v].l];tree[tot].a=(tree[tot].a+(mid-i+1)*z)%mo;tree[tot].ad=(tree[tot].ad+z*tree[tot].d)%mo;tree[tot].adf=(tree[tot].adf+z*tree[tot].df)%mo;tree[tot].lz=(tree[tot].lz+z)%mo;tree[v].l=tot;tree[++tot]=tree[tree[v].r];tree[tot].a=(tree[tot].a+(j-mid)*z)% mo;tree[tot].ad=(tree[tot].ad+z*tree[tot].d)%mo;tree[tot].adf=(tree[tot].adf+z*tree[tot].df)%mo;tree[tot].lz=(tree[tot].lz+z)%mo;tree[v].r=tot;tree[v].lz=0;
}
void insert(int v,int i,int j,int x,int y,ll z)
{if (i==x && j==y) {tree[v].a=(tree[v].a+(j-i+1)*z)%mo;tree[v].ad=(tree[v].ad+z*tree[v].d)%mo;tree[v].adf=(tree[v].adf+z*tree[v].df)%mo;tree[v].lz=(tree[v].lz+z)%mo;return;}   int bz=0;if (tree[v].lz) down(v,i,j),bz=1;int mid=(i+j)/2;if (y<=mid) {if (!bz) tree[++tot]=tree[tree[v].l],tree[v].l=tot;insert(tree[v].l,i,mid,x,y,z);}else if (x>mid) {if (!bz) tree[++tot]=tree[tree[v].r],tree[v].r=tot;insert(tree[v].r,mid+1,j,x,y,z);}else{if (!bz) tree[++tot]=tree[tree[v].l],tree[v].l=tot;insert(tree[v].l,i,mid,x,mid,z);if (!bz) tree[++tot]=tree[tree[v].r],tree[v].r=tot;insert(tree[v].r,mid+1,j,mid+1,y,z);}tree[v].a=(tree[tree[v].l].a+tree[tree[v].r].a)%mo;tree[v].ad=(tree[tree[v].l].ad+tree[tree[v].r].ad)%mo;tree[v].adf=(tree[tree[v].l].adf+tree[tree[v].r].adf)%mo;tree[v].d=(tree[tree[v].l].d+tree[tree[v].r].d)%mo;tree[v].df=(tree[tree[v].l].df+tree[tree[v].r].df)%mo;
}
void find(int v,int i,int j,int x,int y,int z)
{if (i==x && j==y) {ans+=(tree[v].adf+(tree[v].a*((t+t*t)%mo))%mo)%mo;if (z==1) ans+=(tree[v].ad*((2*t+1)%mo))%mo;else ans-=(tree[v].ad*((2*t+1)%mo))%mo;ans=(ans+mo)%mo;return;}if (tree[v].lz) down(v,i,j);int mid=(i+j)/2;if (y<=mid) find(tree[v].l,i,mid,x,y,z);else if (x>mid) find(tree[v].r,mid+1,j,x,y,z);else find(tree[v].l,i,mid,x,mid,z),find(tree[v].r,mid+1,j,mid+1,y,z);
}
int lca(int x,int y)
{fd(i,16,0) if(deep[f[x][i]]>=deep[y]) x=f[x][i];fd(i,16,0) if(deep[f[y][i]]>=deep[x]) y=f[y][i];fd(i,16,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];if (x!=y) x=f[x][0],y=f[y][0];return x;
}
void lct(int x,int y,ll jy)
{int t1,t2,lc,bz=1;lc=lca(x,y);t1=deep[y]-2*deep[lc];t2=deep[y];while (x!=y){int f1=top[x],f2=top[y];if (f1!=f2){if (deep[f1]>=deep[f2]){t=t1;if (jy>0)insert(g[tn],1,n,dfn[f1],dfn[x],jy);elsefind(g[tn],1,n,dfn[f1],dfn[x],1);x=fa[f1];}else{t=t2;if (jy>0)insert(g[tn],1,n,dfn[f2],dfn[y],jy);elsefind(g[tn],1,n,dfn[f2],dfn[y],2);y=fa[f2];}}else{bz=0;if (deep[x]<=deep[y]){t=t2;if (jy>0)insert(g[tn],1,n,dfn[x],dfn[y],jy);elsefind(g[tn],1,n,dfn[x],dfn[y],2);}else{t=t1;if (jy>0)insert(g[tn],1,n,dfn[y],dfn[x],jy);elsefind(g[tn],1,n,dfn[y],dfn[x],1);}break;}}if (x!=0 && x==y && bz){t=t1;if (jy>0)insert(g[tn],1,n,dfn[y],dfn[x],jy);elsefind(g[tn],1,n,dfn[y],dfn[x],1);}
}
int main()
{freopen("zootopia.in","r",stdin);freopen("zootopia.out","w",stdout);int ac;scanf("%d%d",&n,&ac);fo(i,1,n-1) {int x,y;scanf("%d%d",&x,&y);putin(x,y);putin(y,x);}g[0]=1;fo(i,1,n) scanf("%d",&a[i]);deep[1]=1;dg1(1);totot=0;dfn[1]=1;top[1]=1;dg2(1,0);build(g[0],1,n);fo(i,1,n) f[i][0]=fa[i];fo(j,1,16)fo(i,1,n) f[i][j]=f[f[i][j-1]][j-1]; for(;ac;ac--){int yy;scanf("%d",&yy);if (yy==1) {int x,y;ll z;scanf("%d%d%lld",&x,&y,&z);x^=ans;y^=ans;g[++tt]=++tot;tree[tot]=tree[g[tn]];tn=tt;lct(x,y,z);}if (yy==2){int x,y;scanf("%d%d",&x,&y);x^=ans;y^=ans;ans=0;lct(x,y,-1);ans=(ans*ny)%mo;printf("%d\n",ans);}if (yy==3){int x;scanf("%d",&x);x^=ans;tn=x;}}fclose(stdin);fclose(stdout);
}

这篇关于【GDOI 2016 Day1】第四题 疯狂动物城 题解+代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1012521

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时