当前位置: 首页 > news >正文

[2019.3.20]BZOJ4573 [Zjoi2016]大森林

发现一个重要的性质:由于不存在删点的操作,所以之后的加点并不会对之前的询问的答案造成影响。

所以我们可以先处理修改,再处理询问。

考虑从左到右扫描每一颗树,每次将前一棵树通过一些修改变为后一棵树。

发现我们修改一段区间的生长点的位置,相当于在扫描到这个区间的左端点时,将接在原来生长点下面的子树全部转移到新的生长点下面,在扫描右端点结束后,将新的生长点下面的子树移回去。

如下图(红色为原来生长点,蓝色为修改后生长点)

tree-before->tree-during

但是这样不方便对子树进行转移,我们想到可以将一棵子树的转移变为一个点的转移,然后用LCT维护。

于是我们在每次的生长点的孩子位置建一个虚点,将所有从生长点生长出来的点接在虚点的孩子上。

这样一来,我们转移子树的时候,只需要切断虚点和它的父亲的边,再把它连到新的生长点上就好了。

如下图

tree-after-before->tree-after-after

我们用\((1,p,x,y)\)表示在第\(p\)棵树上,将虚点\(x\)移动到点\(y\)的孩子上的操作。

然后,我们对于每一个1操作\(1\ l\ r\ y\),将它拆成两个操作:

\((1,l,x,y)\)将一个虚点\(x\)在左端点\(l\)的树上移动到\(y\)的孩子上(关于虚点\(x\)从哪里来之后会讲);

\((1,r+1,x,li)\)将一个虚点\(x\)在右端点后一个点\(r+1\)的树上移动到\(x\)被建立时的上一个虚点\(li\)的孩子上(之后会讲),即撤销之前在左端点上的移动。

然后考虑具体实现

一开始,我们维护第0棵树,即所有的节点都生长在1号节点的孩子上。

初始有两个节点:实点1和虚点2,2是1的孩子。

对于一个0操作,我们新建一个节点,同时维护一个从实点集合到节点集合的映射\(mp\),\(mp_i\)表示第\(i\)个实点是第几个节点,将它连接在目前上一个被建立的虚点上,并同时记录存在第\(i\)个实点的树的区间\([sgl_i,sgr_i]\)

对于一个1操作,我们新建一个虚点\(x\),执行上述操作。

对于一个2操作,我们用\((2,p,x,y)\)表示询问第\(p\)棵树上,节点(注意不是实点)\(x\)\(y\)的距离。

注意,此时我们并没有执行由\(1\)操作和\(2\)操作获得的操作和询问。

然后,我们要对所有的操作排序,第一关键字为操作或者询问的位置(位置靠前的排在前面),第二关键字为询问或操作(询问排在操作前面)

然后对于一个操作,我们断开需要移动的点和它原来的父亲,然后将它连在新父亲的孩子上。

对于一个询问,我们运用树上差分,给实点赋权为1,虚点赋权为0(这一步在建立节点时就可以实现),记录\(sum_x\)表示节点\(x\)到1路径上节点的权值和,那么节点\(i,j\)之间的路径长度=\(sum_i+sum_j-sum_{LCA(i,j)}\)

最后一个问题,如何在LCT上求LCA?

显然我们不能\(Split\)(即进行\(Makeroot\)然后\(Access\)),因为这是一棵有根(1)树,这样会改变它的结构。

于是我们对于节点\(i,j\)分别进行\(Access\),后一次中最后一个与右孩子切断实边的节点即为LCA。

为什么?其实最后一次切断目前节点与右孩子的实边后,目前节点到根的部分即为两点到根路径的公共部分,自然这个点就是\(i\)\(j\)的LCA。

code:

#include<bits/stdc++.h>
#define ci const int&
using namespace std;
struct query{
    int op,pos,x,y,id;//move x to son of y(op=1),query the lenth of (x,y)(op=2)
}q[400010];
struct node{
    int f,c[2],tag,val,sum;
}t[200010];
int n,m,sz,tt,T,len,op,a,b,c,cnt,li,mp[200010],rn,sgl[200010],sgr[200010],prt[200010];
bool cmp(query x,query y){
    return x.pos!=y.pos?x.pos<y.pos:x.op<y.op;
}
void Upd(ci x){
    t[x].sum=t[t[x].c[0]].sum+t[t[x].c[1]].sum+t[x].val;
}
void Psd(ci x){
    t[x].tag?swap(t[x].c[0],t[x].c[1]),t[t[x].c[0]].tag^=1,t[t[x].c[1]].tag^=1,t[x].tag=0:0;
}
bool Isroot(ci x){
    return t[t[x].f].c[0]!=x&&t[t[x].f].c[1]!=x;
}
void Rotate(ci x){
     int y=t[x].f,z=t[y].f;
     Psd(y),Psd(x);
     int c=t[y].c[1]==x,gc=t[z].c[1]==y;
     !Isroot(y)?t[z].c[gc]=x:0,t[x].f=z;
     t[y].c[c]=t[x].c[c^1],t[t[x].c[c^1]].f=y;
     t[x].c[c^1]=y,t[y].f=x;
     Upd(y),Upd(x);
}
void Splay(ci x){
    while(!Isroot(x)){
        int y=t[x].f,z=t[y].f;
        if(Isroot(y))Rotate(x);
        else{
            Psd(z),Psd(y);
            (t[y].c[1]==x)==(t[z].c[1]==y)?Rotate(y):Rotate(x),Rotate(x);
        }
    }
}
int Access(ci x,ci lst){
    if(!x)return 0;
    Splay(x),t[x].c[1]=lst,Upd(x);
    int tmp=Access(t[x].f,x);
    return tmp?tmp:x;
}
void Cut(ci x){
    Access(x,0),Splay(x),t[x].c[0]=t[t[x].c[0]].f=0,Upd(x);
}
void Link(ci x,ci y){
    Splay(y),t[y].f=x;
}
void printpath(int x){
    if(!x)return;
    Splay(x);
    t[x].c[0]?printpath(t[x].c[0]):printpath(t[x].f);
}
int main(){
    scanf("%d%d",&n,&m);
    rn=1,li=cnt=2,t[1].val=t[1].sum=1,Link(1,2),mp[1]=sgl[1]=1,sgr[1]=n;
    while(m--){
        scanf("%d",&op);
        if(op==0)scanf("%d%d",&a,&b),mp[++rn]=++cnt,sgl[rn]=a,sgr[rn]=b,Link(li,cnt),t[cnt].val=t[cnt].sum=1;
        else if(op==1){
            scanf("%d%d%d",&a,&b,&c),a=max(a,sgl[c]),b=min(b,sgr[c]);
            if(a>b)continue;
            Link(li,++cnt),q[++sz]=(query){1,a,cnt,mp[c],0},q[++sz]=(query){1,b+1,cnt,li,0},li=cnt;
        }else ++sz,scanf("%d%d%d",&q[sz].pos,&q[sz].x,&q[sz].y),q[sz].x=mp[q[sz].x],q[sz].y=mp[q[sz].y],q[sz].op=2,q[sz].id=++tt;
    }
    sort(q+1,q+sz+1,cmp);
    for(int i=1;i<=sz;++i){
        if(q[i].op==1)Cut(q[i].x),Link(q[i].y,q[i].x);
        else Access(q[i].x,0),Splay(q[i].x),len=0,len+=t[q[i].x].sum,T=Access(q[i].y,0),Splay(q[i].y),len+=t[q[i].y].sum,Access(T,0),prt[q[i].id]=len-(t[T].sum<<1);
    }
    for(int i=1;i<=tt;++i)printf("%d\n",prt[i]);
    return 0;
}

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ4573.html

相关文章:

  • JQuery知识总结之选择器
  • 读书之法,在循序而渐进,熟读而精思。
  • REdis CPU百分百问题分析
  • abp 关于service 服务的定义
  • ORACLE-2
  • 第一章 初识Python
  • 吴恩达机器学习系列12:反向传播算法
  • Oracle_11g
  • 数据科学家为什要用Git?怎么用?
  • 阿里巴巴收购以色列VR公司,大厂死磕VR为哪般?
  • 搭建YUM仓库
  • 【springboot】 mybatis 集成代码生成器 shiro 权限 后台框架平台
  • 程序员跳槽高峰期:BAT面试合集JVM+Spring+数据库+中间件等
  • 项目总结21:项目总结21:input实现多图上传(FormData)(上传OSS并保存数据库)
  • 《Javascript高级程序设计 (第三版)》第五章 引用类型
  • 【JavaScript】通过闭包创建具有私有属性的实例对象
  • angular2开源库收集
  • co.js - 让异步代码同步化
  • express如何解决request entity too large问题
  • gf框架之分页模块(五) - 自定义分页
  • IOS评论框不贴底(ios12新bug)
  • Java 内存分配及垃圾回收机制初探
  • SQLServer之索引简介
  • Sublime text 3 3103 注册码
  • Vim Clutch | 面向脚踏板编程……
  • 分类模型——Logistics Regression
  • 三分钟教你同步 Visual Studio Code 设置
  • 小程序button引导用户授权
  • 学习HTTP相关知识笔记
  • 【运维趟坑回忆录】vpc迁移 - 吃螃蟹之路
  • python最赚钱的4个方向,你最心动的是哪个?
  • 从如何停掉 Promise 链说起
  • 国内开源镜像站点
  • ​无人机石油管道巡检方案新亮点:灵活准确又高效
  • #我与Java虚拟机的故事#连载06:收获颇多的经典之作
  • $.ajax()
  • (1/2)敏捷实践指南 Agile Practice Guide ([美] Project Management institute 著)
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • (webRTC、RecordRTC):navigator.mediaDevices undefined
  • (八十八)VFL语言初步 - 实现布局
  • (附源码)spring boot基于Java的电影院售票与管理系统毕业设计 011449
  • (论文阅读23/100)Hierarchical Convolutional Features for Visual Tracking
  • (四)【Jmeter】 JMeter的界面布局与组件概述
  • (算法设计与分析)第一章算法概述-习题
  • (五)关系数据库标准语言SQL
  • (一)Dubbo快速入门、介绍、使用
  • (转)eclipse内存溢出设置 -Xms212m -Xmx804m -XX:PermSize=250M -XX:MaxPermSize=356m
  • ***通过什么方式***网吧
  • .htaccess 强制https 单独排除某个目录
  • .libPaths()设置包加载目录
  • .NET Framework与.NET Framework SDK有什么不同?
  • .net 验证控件和javaScript的冲突问题
  • .net实现客户区延伸至至非客户区
  • .secret勒索病毒数据恢复|金蝶、用友、管家婆、OA、速达、ERP等软件数据库恢复