【BZOJ 3196】二逼平衡树 线段树套splay 模板题
我写的是线段树套splay，网上很多人写的都是套treap，然而本蒟蒻并不会treap奉上sth神犇的模板：//bzoj3196二逼平衡树，支持修改某个点的值，查询区间第k小值，查询区间某个值排名，查询区间某个值值前驱、后继。查询第k小值是log^3(n)的，其他都是log^2(n)的#includ...
Wow! Such Sequence!(线段树4893)
Wow!SuchSequence!TimeLimit:10000/5000MS(Java/Others)MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):3808AcceptedSubmission(s):1079ProblemDescr...
【权值线段树】bzoj3224 Tyvj 1728 普通平衡树
一个板子。#include<cstdio>#include<algorithm>usingnamespacestd;#defineN100001structData{intv,p;}t[N];boolcmp(constData&a,constData&b){r...
【POJ2482】【线段树】Stars in Your Window
DescriptionFleetingtimedoesnotblurmymemoryofyou.Canitreallybe4yearssinceIfirstsawyou?Istillremember,vividly,onthebeautifulZhuhaiCampus,4yearsago,fromt...
BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)
首先嘛，还是太弱了，想了好久QAQ然后，这道题么，明显就是求sigma（size[x]）(x是y的儿子且层树小于k)然后就可以发现：把前n个节点按深度建可持久化线段树，就能用前缀和维护了其实不难打==#include<cstdio>#include<iostream>#inc...
bzoj 3653: 谈笑风生 可持久化线段树
题目大意在一棵单位边权的有根树上支持询问:给定a,k求满足下列条件的有序三元对的个数.a,b,c互不相同a,b均为c的祖先a,b树上距离<=k题解solution1首先我们知道,c一定在以a为根的子树内,否则不满足条件2对于一个询问a,k,我们知道b一定在a的k步以内所以我们把问题分为两部分:...
bzoj 4196 [Noi2015]软件包管理器 (树链剖分+线段树）
4196:[Noi2015]软件包管理器TimeLimit: 10Sec MemoryLimit: 512MBSubmit: 2852 Solved: 1668[Submit][Status][Discuss]DescriptionLinux用户和OSX用户一定对软件包管理器不会陌生。通过软件包...
hdu 4578 Transformation 线段树多种操作裸题
自己写了一个带结构体的WA了7.8次但是测了几组小数据都对。。感觉问题应该出在模运算那里。写完这波题解去对拍一下。以后线段树绝不写struct！一般的struct都带上l,r但是一条线段的长度确定的话，每一个节点的l,r都可以确定的，没必要用struct存上，如果不带上l，r那不是更没必要用结构体h...
HDU - 1542 扫描线入门+线段树离散化
扫描线算法+线段树维护简介：像这种求面积的并集的题目，就适合用扫描线算法解决，具体来说就是这样类似这种给出点的矩形的对角的点的坐标，然后求出所有矩形面积的交集的问题，可以采用扫描线算法解决。图如下，我们要求红色部分的面积：我们可以通过一条叫扫描线的东西解决问题。具体来说：我们首先给自己一条线，这条可...
hdu acm 1166 敌兵布阵 （线段树）
敌兵布阵TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):37903 AcceptedSubmission(s):15985ProblemDescription...
BZOJ3626[LNOI2014]LCA——树链剖分+线段树
题目描述给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出lrz，求sigma_{l<=i<=r}dep[LCA(i,z)]。（即，求在[l,...
线段树模板hdu 1166:敌兵布阵
敌兵布阵TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):121643 AcceptedSubmission(s):50879ProblemDescript...
Codeforces Round #370 (Div. 2) E. Memory and Casinos (数学&&概率&&线段树)
题目链接： http://codeforces.com/contest/712/problem/E题目大意：一条直线上有n格,在第i格有pi的可能性向右走一格,1-pi的可能性向左走一格,有2中操作：单点修改pi以及询问从L格出发最终从R格离开区间[L,R]的概率。这题在cf上A的人比较少,本来不打...
HDU 1754 I Hate It(线段树区间查询，单点更新)
描述很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。Input本题目包含多组测试，请处理到文件结束。在每个测试的第一行，有两...
【IOI1998】Picture（扫描线+线段树）
问题来源：IOI1998D2T1题意：就是在一个平面内给出n个矩形，叫你计算将这些矩形合并以后，新图形的周长。例如：上图是原本的矩形们---------->合并后的图形解题思路：拿一条扫描线横着扫一次，遇到左边的边就在这条扫描线上+1，遇到右边的边就在这条扫描线上-1，在边被扫到的时候计算一下...
HDU 5775 Bubble Sort(线段树)(2016 Multi-University Training Contest 4 1012)
原址地址：http://ibupu.link/?id=31ProblemDescriptionPisapermutationoftheintegersfrom1toN(indexstartingfrom1).HereisthecodeofBubbleSortinC++.for(inti=1;i<...
HIHO 线段树(单点)
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>usingnamespacestd;constintMM=;//...
线段树---poj2528 Mayor’s posters【成段替换|离散化】
poj2528Mayor’sposters题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报思路:这题数据范围很大,直接搞超时+超内存,需要离散化:离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]我们用不到[-∞,999][1001,198...
POJ-2528 Mayor's posters (离散化， 线段树)
题目传送门:POJ-2528题意就是在一个高度固定的墙面上贴高度相同宽度不同的海报，问贴到最后还能看到几张?本质上是线段树区间更新问题，但是要注意的是题中所给数据范围庞大，直接搞肯定会搞出问题，所以要离散化，而离散化的过程中要注意一个问题，比方说1-10，1-5，6-10，本来是可以三张海报都可以看...
hdu1540（线段树）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1540题意：是一条线上的点，Dx是破坏这个点，Qx是表示查询以x所在的最长的连续的点的个数，R是恢复上一次破坏的点。线段树功能：单点修改，区间求值。分析： pre数组记录区间左端点开始的最大连续个数， ...