BZOJ 3786: 星系探索 欧拉游览树
2024-08-31 06:12:05
一个叫 Euler-Tour-Tree 的数据结构,说白了就是用 Splay_Tree 维护欧拉序
#include <cstring> #include <algorithm> #include <string> #include <cstdio> using namespace std; void setIO(string a){ freopen((a+".in").c_str(),"r",stdin); freopen((a+".out").c_str(),"w",stdout); } #define maxn 300000 #define ll long long int euler[maxn], w[maxn], cnt=1; int head[maxn],to[maxn],nex[maxn],edges,root; ll sumv[maxn], val[maxn], lazy[maxn]; void addedge(int u,int v){ nex[++edges]=head[u],head[u]=edges,to[edges]=v; } void dfs(int u){ euler[++cnt]=u*2, val[u*2]=w[u]; for(int v=head[u];v;v=nex[v]) dfs(to[v]); euler[++cnt]=u*2+1, val[u*2+1]=-w[u]; } struct Splay_Tree{ int f[maxn],ch[maxn][2],sta[maxn],siz[maxn]; int rson(int x) { return ch[x][1]; } int lson(int x) { return ch[x][0]; } int get(int x) { return ch[f[x]][1]==x; } void update(int x,int c) { val[x]+=(x%2==0?1:-1)*c; lazy[x]+=c; sumv[x]+=siz[x]*c; } void pushup(int x) { sumv[x]=sumv[lson(x)]+sumv[rson(x)]+val[x]; siz[x]=siz[lson(x)]+siz[rson(x)]; siz[x]+=(x>=200099 ? 0: (x%2==0?1:-1)); } void pushdown(int x) { if(lazy[x]) update(lson(x),lazy[x]), update(rson(x),lazy[x]),lazy[x]=0; } int pre(int x) { splay(x,root); x=lson(root); while(rson(x)) x=rson(x); return x; } int las(int x) { splay(x,root); x=rson(root); while(lson(x)) x=lson(x); return x; } void build(int l,int r,int &o,int fa) { if(l>r)return; int mid=(l+r)>>1; o=euler[mid], f[o]=fa; build(l,mid-1,ch[o][0],o); build(mid+1,r,ch[o][1],o); pushup(o); } void rotate(int x) { int old=f[x], oldf=f[old], which=get(x); ch[old][which]=ch[x][which^1], f[ch[old][which]]=old; ch[x][which^1]=old,f[old]=x,f[x]=oldf; if(oldf) ch[oldf][ch[oldf][1]==old]=x; pushup(old),pushup(x); } void splay(int x,int &tar) { int v=0,u=x,a=f[tar]; while(u!=a) sta[++v]=u,u=f[u]; while(v) pushdown(sta[v--]); for(int fa;(fa=f[x])!=a;rotate(x)) if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x); tar=x; } void opt1(int a) { int x=las(a*2); splay(200100,root),splay(x,ch[root][1]); printf("%lld\n",sumv[ch[ch[root][1]][0]]); } void opt2(int a,int b) { int x=pre(a*2),y=las(a*2+1),tmp; splay(x,root),splay(y,ch[root][1]); tmp=ch[ch[root][1]][0], ch[ch[root][1]][0]=f[tmp]=0; pushup(ch[root][1]), pushup(root); x=las(b*2); splay(b*2,root), splay(x,ch[root][1]); ch[ch[root][1]][0]=tmp,f[tmp]=ch[root][1]; pushup(ch[root][1]),pushup(root); } void opt3(int a,int b) { int x=pre(a*2),y=las(a*2+1); splay(x,root),splay(y,ch[root][1]); update(ch[ch[root][1]][0],b); pushup(ch[root][1]),pushup(root); } }tree; int main(){ //setIO("input"); int n,x,m; scanf("%d",&n); for(int i=2;i<=n;++i) scanf("%d",&x),addedge(x,i); for(int i=1;i<=n;++i) scanf("%d",&w[i]); dfs(1); euler[1]=200100, euler[++cnt]=200101; tree.build(1,cnt,root,0); scanf("%d",&m); while(m--) { char opt[10]; int a,b; scanf("%s",opt); if(opt[0]=='Q') { scanf("%d",&a); tree.opt1(a); } if(opt[0]=='C') { scanf("%d%d",&a,&b); tree.opt2(a,b); } if(opt[0]=='F') { scanf("%d%d",&a,&b); tree.opt3(a,b); } } return 0; }
最新文章
- ble示例代码
- 安装完ODAC,出现ORA-12560:TNS:协议适配器错误 12541 无监听程序的解决
- 浅析 - 提高xib(Interface Builder)高效工作的几个小技巧
- 定时器图片轮播淡入淡出基本功能已实现,正在修改BUG中。。(附图效果和源代码)
- Silverlight:版本控制的衍化
- javascript与服务器3
- XML 实体扩展攻击
- 资料Link集合
- Delphi中多线程下使用使用 UniDAC+MSSQL 需要注意的问题(连接前调用CoInitialize)
- Delphi实现窗口一直在桌面工作区内显示(重写WM_WINDOWPOSCHANGING消息)
- thinkphp框架实现删除上传的文件
- python全栈开发day118-Mui
- 如何阅读jdk源码?
- Scrapy基础(三) ------xpath基础
- sql server 转置 和实现随机分配和一串代码的含义拼在一行
- Javascript中的Bind,Call和Apply
- java为什么匿名内部类的参数引用时final(转)
- 前段时间,接手一个项目使用的是原始的jdbc作为数据库的访问,发布到服务器上在运行了一段时间之后总是会出现无法访问的情况,登录到服务器,查看tomcat日志发现总是报如下的错误。 Caused by: com.mysql.jdbc.exceptions.jdbc4.MySQLNonTransientConnectionException: Data source rejected est
- C#学习笔记(七):结构体、数组、冒泡排序和调试
- ucenter 认证登录
热门文章
- zzulioj--1777--和尚特烦恼3——何时能下山(水题)
- springMVC接受参数总结
- handsontable在线编辑excel扩展功能-踩坑篇
- Angular4集成ng2-file-upload
- ARM的六大类指令集---LDR、LDRB、LDRH、LDM、STR、STRB、STRH、STM
- 获取新浪微博的Access_token
- vue 事件上加阻止冒泡 阻止默认事件
- 对同层数据进行处理,做成树状图形式的数据结构,并符合elementui中的tree结构
- 【Computer Vision】图像单应性变换/投影/仿射/透视
- vue中的methods、computed和watch