BZOJ 2588 Count on a tree (COT) 可持久化线段树

题目大意:查询树上两点之间的第k大的点权。

思路:树套树,其实是正常的树套一个可持久化线段树。因为利用权值线段树可以求区间第k大,然后再应用可持久化线段树的思想,可以做到区间减法。详见代码。

CODE:

#include #include #include #include #define MAX 100010 #define NIL (tree[0]) using namespace std; pair src[MAX]; struct Complex{ Complex *son[2]; int cnt; Complex(Complex *_,Complex *__,int ___):cnt(___) { son[0] = _; son[1] = __; } Complex() {} }*tree[MAX]; int points,asks; int xx[MAX]; int head[MAX],total; int next[MAX > points >> asks; for(int i = 1;i son[0] = NIL->son[1] = NIL; DFS(1); SparseTable(); int now = 0; for(int x,y,k,i = 1;i > 1; if(x == y) return new Complex(NIL,NIL,pos->cnt + 1); if(val son[0],x,mid,val),pos->son[1],pos->cnt + 1); return new Complex(pos->son[0],BuildTree(pos->son[1],mid + 1,y,val),pos->cnt + 1); } int GetLCA(int x,int y) { if(deep[x] = deep[y]) x = father[x][i]; if(x == y) return x; for(int i = 19; ~i; --i) if(father[x][i] != father[y][i]) x = father[x][i],y = father[y][i]; return father[x][0]; } int GetAns(Complex *l,Complex *r,Complex *f,Complex *p,int x,int y,int k) { if(x == y) return x; int mid = (x + y) >> 1; int temp = l->son[0]->cnt + r->son[0]->cnt - f->son[0]->cnt - p->son[0]->cnt; if(k son[0],r->son[0],f->son[0],p->son[0],x,mid,k); return GetAns(l->son[1],r->son[1],f->son[1],p->son[1],mid + 1,y,k - temp); }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:HDOJ 2028 Lowest Common Multiple Plus
下一篇:AsyncSocket中tag参数的用处
相关文章

poj1066巧妙的线段相交的应用

poj 1823 Hotel 线段树,注意懒惰标

poj 1410 矩形与线段相交判断

hdu 4339 Query 线段树 多校联合赛

poj 3667 Hotel 线段树 内存分配问题

线段树和单调队列优化DP---POJ2373解题

poj 3162 线段树 hdu 4123 bfs

[线段树]POJ 2374 Fence Obstacle

POJ 1823 Hotel 线段树 + lazy标签

HDU OJ 1754 I Hate It [线段树

图文推荐
BZOJ 2588 Count on a tree (COT) 可持久化线段树
ZOJ 3640 Help Me
BZOJ 2588 Count on a tree (COT) 可持久化线段树
CF 518C(Anya and
BZOJ 2588 Count on a tree (COT) 可持久化线段树
hdu 1016 Prime R
UVA - 11987 - A

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

相关文章

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

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

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

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

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

    题目大意:给定n个形如xi=ki*x_pi+bi mod p的同余方程组 支持修改操作和求解操作 确实好题 感谢此题作者 顺便吐槽一下作者的Splay不加空节点太蛋疼了0.0 将每个点i的父亲设为pi 我们将会得到一座基环树林 将环上的一条边拆掉,在边的起始节点新开个域special_father记录这条边(P.S:好浪费 但是没办法) 于是我们得到了一座森林 显然可以用LCT来维护 每个节点的权值是个二元组(k,b),记录每个点关于答案的线性关系,合并时左侧代入右侧中 查询时将root的spe

  • BZOJ 1036: [ZJOI2008]树的统计Count 2013-10-26

    题目地址:http :// www . lydsy . com / JudgeOnline / problem . php ? id = 1036 题目大意:给出一棵树,每个点有一个权值,要求三种操作:1.修改某个点的权值,2.询问x到y路径上各点的权值最大值,3.询问x到y路径上各点的权值之和。 算法讨论:树链剖分模板题。 Code: #include #include #define N 30000 #define oo 0x7f7f7f7f using namespace std; int

  • 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;

  • leetcode Construct Binary Tree from Preorder and Inorder Traversal 2012-01-06

    Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 和construct binary tree from inorder and postorder trav

  • LeetCode OJ:Unique Binary Search Trees II 2012-02-19

    Unique Binary Search Trees II Given n, generate all structurally unique BST's (binary search trees) that store values 1...n. For example, Given n = 3, your program should return all 5 unique BST's shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \

  • Leetcode Recover Binary Search Tree 2012-03-06

    Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? c

  • BZOJ 3218 a + b Problem 可持久化线段树+最小割 2012-07-04

    题目大意:。。。自己看 从源点出发,分别向汇点连两条流量为a和b的边,跑最大流即是a+b。 代码: #include #include #include #include #define M 10 #define S 1 #define T 2 #define INF 0x3f3f3f3f using namespace std; struct abcd{ int to,f,next; }table[100]; int head[M],tot=1; void Add(int x,int y,in

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

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

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