BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得

题目大意:给定n个形如xi=ki*x_pi+bi mod p的同余方程组 支持修改操作和求解操作

确实好题 感谢此题作者 顺便吐槽一下作者的Splay不加空节点太蛋疼了0.0

将每个点i的父亲设为pi 我们将会得到一座基环树林 将环上的一条边拆掉,在边的起始节点新开个域special_father记录这条边(P.S:好浪费 但是没办法)

于是我们得到了一座森林 显然可以用LCT来维护 每个节点的权值是个二元组(k,b),记录每个点关于答案的线性关系,合并时左侧代入右侧中

查询时将root的special_father进行Access+Splay操作 然后借助这个环通过EXGCD求出root->special_father的值 然后Access+Splay(x)代入出解

若环上k=1 讨论b 若b=0则无穷多解 否则无解 注意k=0时要加一些处理 正常求EXGCD求不出来

单点修改 有向图 没有标记 爽爆了!

修改x的父节点时需要讨论:

首先切掉原先的父节点

如果x是所在树的根 直接切掉special_father

如果x不是根,切掉x与父节点的联系,然后讨论x是否在环上

设x所在树的根节点为root

若root->special_father所在树的根不为root 则x在环上 将root的special_father变为root的fa节点

否则切断父节点完毕

然后讨论新的父节点f是否在x的子树中

若在,将x的special_father设为f

若不在,将x的fa设为f

好题……RE一晚上……居然忘了对LCT中的任意节点进行修改操作都要先Access+Splay了……居然直接把爸爸换了……RE到死啊

#include #include #include #include #define M 30300 #define p 10007 using namespace std; struct line{ int k,b; line operator + (const line &y) const { line re; re.k=k*y.k%p; re.b=(b*y.k+y.b)%p; return re; } int F(int x) { return (k*x+b)%p; } }; struct abcd{ abcd *ls,*rs,*fa,*sfa; line num,sum; abcd(int k,int b); void Push_Up(); }*null=new abcd(1,0),*tree[M]; abcd :: abcd(int k,int b) { ls=rs=fa=sfa=null; num.k=sum.k=k; num.b=sum.b=b; } void abcd :: Push_Up() { sum=ls->sum+num+rs->sum; } void Zig(abcd *x) { abcd *y=x->fa; y->ls=x->rs; x->rs->fa=y; x->rs=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); } void Zag(abcd *x) { abcd *y=x->fa; y->rs=x->ls; x->ls->fa=y; x->ls=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; y->Push_Up(); } void Splay(abcd *x) { while(x->fa->ls==x||x->fa->rs==x) { abcd *y=x->fa,*z=y->fa; if(x==y->ls) { if(y==z->ls) Zig(y); Zig(x); } else { if(y==z->rs) Zag(y); Zag(x); } } x->Push_Up(); } void Access(abcd *x) { abcd *y=null; while(x!=null) { Splay(x); x->rs=y; x->Push_Up(); y=x; x=x->fa; } } abcd* Find_Root(abcd *x) { abcd *y; Access(x); Splay(x); for(y=x;y->ls!=null;y=y->ls); return y; } int n,m,fa[M],v[M],tot; pairEXGCD(int x,int y) { if(!y) return make_pair(1,0); pairtemp=EXGCD(y,x%y); return make_pair(temp.second,temp.first-x/y*temp.second); } int Inverse(int x) { int temp=EXGCD((x+p)%p,p).first; return (temp%p+p)%p; } void DFS(int x) { v[x]=tot; if(v[fa[x]]==tot) { tree[x]->sfa=tree[fa[x]]; return ; } tree[x]->fa=tree[fa[x]]; if(!v[fa[x]]) DFS(fa[x]); } int Query(abcd *x) { abcd *root=Find_Root(x); Access(root->sfa); Splay(root->sfa); int k=root->sfa->sum.k; int b=root->sfa->sum.b; if(k==1) { if(b==0) return -2; else return -1; } int temp=(p-b)*Inverse(k-1)%p; Access(x); Splay(x); return x->sum.F(temp); } void Modify(abcd *x,int k,abcd *f,int b) { abcd *root=Find_Root(x); x->num.k=k; x->num.b=b; x->Push_Up(); if(x==root) x->sfa=null; else { Access(x); Splay(x); x->ls->fa=null; x->ls=null; x->Push_Up(); if(Find_Root(root->sfa)!=root) { Access(root); Splay(root); root->fa=root->sfa; root->sfa=null; } } Access(x); Splay(x); if(Find_Root(f)==x) x->sfa=f; else x->fa=f; } int main() { int i,x,k,f,b; char o[10]; cin>>n; for(i=1;i>m; for(i=1;i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:LeetCode Palindrome Number
下一篇:探寻C/C++中更快的大数(自然数集)模板
相关文章

C++对象布局及多态实现之动态和强制转

C++中的动态多维数组

C++中的动态多维数组

C++动态空间的申请

动态链接库的简单应用

C/C++ 2D数组的动态分配方法比较

自己动手实现动态外网ip管理和动态DNS

C++的动态绑定和静态绑定

如何在C/C++中动态分配二维数组

HDU OJ 2159 FATE [动态规划]

图文推荐
BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得
ZOJ 3640 Help Me
BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得
CF 518C(Anya and
BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-09 人气:7
本文关键词:
分享到:

相关文章

  • BZOJ 2049 Sdoi2008 Cave 洞穴勘测 动态树 Link-Cut-Tree 2012-12-27

    题目大意:有一些洞穴,现在都是彼此分开的,将会被一些无向边所连接。给一些操作,加边,删边,求在某状态下两点之间的联通状态。 思路:简单的Link-Cut-Tree维护图的联通性。基础题,建议初学者刷这个。(我才不会说我被坑第一道题刷的2631。。自己调了2天,然后让同学看2分钟就看出错误了。。。。。。要搞好基础啊!!!) 判断两点是否联通的时候只要暴力找根比较看看一不一样就可以了,不会超时。 CODE: #include #include #include #include #define MA

  • BZOJ 3282 Tree Link-Cut-Tree 动态树 2013-11-10

    题目大意:维护一种动态树形数据结构,支持: 1.求树上两点之间的点的异或和。 2.连接两点(不保证不连通) 3.删除连点之间的边(不保证两点联通) 4.将一个点的点权改成一个值 思路:还是LCT,思路也比较裸。主要是它各种不保证,所以要多加判断。 CODE: #include #include #include #include #define MAX 300010 using namespace std; struct Complex{ int val,_xor; bool reverse;

  • 探寻C/C++中更快的大数(自然数集)模板 2013-06-22

    本文系fcbruce个人原创整理,转载请注明出处http://blog.csdn.net/u012965890/article/details/40432511,谢谢! 我们知道在C/C++中int型可处理-2^31~2^31-1(32位及以上编译器),long long型可处理-2^63~2^63-1的数据,这实际上是非常有限的,在很多情况下,我们往往会处理范围更大的数据。Java中有BigInteger类,python中想要多大就有多大(取决于内存),但是C/C++就显得有些乏力,这时候我们

  • Apache Fast CGI C++程序开发 2012-11-07

    Apache Fast CGI开发 Author: Kagula 发起日期:2014-11-08 最后更新日期:2014-11-23 环境: [1]Win 8.1 64bits、 VMWare9,Cent OS 6.532bits, fcgid 2.3.9, boost 1.55, Apache 2.2.25, [2] Cent OS 6.6,Apache 2.2.15, CMake 2.8.12.2, GCC 4.4.7, boost 1.57 Fast CGI相比CGI,响应速度提高了好几倍

  • HDU 4362 Dragon Ball 线段树 2014-08-04

    #include #include #include #include #include #include #include #include #include #include using namespace std; #define lson l, mid, rt a[M]; int val[M][N][2]; ll d[M][N]; void Up(node& fa, node &ls, node& rs) { if (ls.min > rs.min) { f

  • C++ STL源码学习(list篇) 2015-01-01

    ///STL list为双向循环链表 struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; template struct _List_node : public _List_node_base { _Tp _M_data; }; struct _List_iterator_base { typedef size_t size_type; typedef ptrdiff_t differen

  • Codeforces Round #238 (Div. 2) B题 2014-10-02

    字符串处理题 B. Domino Effect time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Chris knows there's no fun in playing dominoes, he thinks it's too random and doesn't require skill. Instead,

  • kd-tree讲解 & bzoj 2648 & 2716 & 3053 题解 2013-09-17

    【KD-TREE介绍】在SYC1999大神的“蛊惑”下,我开始接触这种算法。 首先,大概的概念可以去百度百科。具体实现,我是看RZZ的代码长大的。 我们可以想象在平面上有N个点。首先,按横坐标排序找到最中间的那个点。然后水平划一条线,把平面分成左右两个部分。再递归调用左右两块。注意,在第二次(偶数次)调用的时候,是找到纵坐标中最中间的点,并垂直画一条线。 这样效率看上去很好。维护的时候有点像线段树。每个点记录它的坐标、它辖管的区间4个方向的极值、它的左右(或上下)的两个点的标号。递归两个子树时,

  • [LeetCode] Flatten Binary Tree to Linked List 2014-03-18

    Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 问题描述:给定一个二叉树,将它变成一个类似上面那样的链表,而且操作要原地进行。 根据上面两个树的样子,可以看到,在链表形式中,节点的左孩子为空,右孩子为先序遍历中当前节点的前一个节点

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.148 (s). 10 q(s)