线段树 - hzwer.com

2015程序设计实习实验班免修考试(校内）
【poj1037】decorativefence用f(i,j)表示长度为i，开头为j，开头为上升的序列用g(i,j)表示长度为i，开头为j，开头为下降的序列考虑在序列的第二位放一个数字，改变上升/下降预处理完之后，一位位枚举贪心[crayon-5994bd5011363733707394/]【poj1011】Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时，如果不能加入某根木棍，同种长度的木...
02017年2月19日1,565递推与动规,深度搜索,最大流,线段树,广度搜索,博弈论

【cf718X】Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-5994bd5012650099856431/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
02016年11月7日2,132模拟,贪心,线段树,树形动规,哈希表,广度搜索,状压动规,记忆化搜索,矩阵乘法
【小奇模拟赛】小奇的自动机
【题目背景】小奇在研究后缀自动机时遇到了一个难题。【问题描述】定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。【输入格式】第1行1个整数n。接下来n行，第i+1行包括1个字符串Si。再接下来n行，第n+1+i行的整数表示Ki。【输出格式】输出...
02016年5月21日1,404字典树,线段树
【省选模拟赛】小奇的花园
原题：【泉七培训-刘定峰】花园【题目背景】小奇在家中的花园漫步时，总是会思考一些奇怪的问题。【问题描述】小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。【输入格式】第一行为两个整数n，q，表示温室的数目和操作的数目。第二行有n个整数T1...
32015年12月19日3,858treap,树套树,STL,线段树,树链剖分
【bzoj3600】没有人的算术
http://pan.baidu.com/s/1B0JNovfk大大的题好厉害QAQWJMZBMR在论文中也有提到平衡树的这种用法《重量平衡树和后缀平衡树在信息学奥赛中的应用》大概就是用平衡树维护这些数，给每个数一个实数值表示其大小生成一个数(a,b)的时候，由于a,b都是之前出现过的数，所以我们可以直接在平衡树上插入，返回代表它的实数值用线段树求区间最大值[crayon-5994bd5013ce1939770517/] ...
12015年7月11日3,416替罪羊树,线段树
【cf339X】Codeforces Round #197 (Div. 2)
A.HelpfulMaths排序[crayon-5994bd50143a5119767417/]B.XeniaandRingroad题意即题解[crayon-5994bd50143af720535291/]C.XeniaandWeights搜索可过[crayon-5994bd50143b3644550585/]D.XeniaandBitOperations线段树模拟每次询问可以自底向上修改[crayon-5994bd50143b7555636795/]E.ThreeSwaps由于只有三次交换，所以数列最多被分成七段找到所有断点爆搜[crayon-5994bd50143bc891774935/] ...
12015年6月23日1,188模拟,深度搜索,线段树
【cf260X】Codeforces Round #158 (Div. 2)
A.AddingDigits模拟，每次可以根据当前模的结果，得出下一个添加的数字[crayon-5994bd5014cd5637340248/]B.AncientProphesy在串中枚举一段，用map统计出现次数[crayon-5994bd5014ce4351017932/]C.BallsandBoxes可以发现，拿来分的那个盒子现在的数量一定是最少的，于是模拟大法[crayon-5994bd5014cf0488230140/]D.BlackandWhiteTree将两色的结点排序后，依次贪心构造构造方法很简单[crayon-5994bd5014cf7456561096/]E...
02015年6月9日1,250贪心,STL,二分法,线段树
pkusc 2014 #2
A:QuadTiling对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可[crayon-5994bd5015599417728157/]B:Garden傻逼线段树[crayon-5994bd50155a9357004114/]D:One-movecheckmate枚举一下皇后能一步到达的位置，然后判一下是否将死注意细节较多具体见discuss[crayon-5994bd50155b7414036186/]E:ATP二分答案后，从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...
02015年6月1日1,335递推与动规,模拟,贪心,二分法,线段树,矩阵乘法
【bzoj3924】[Zjoi2015]幻想乡战略游戏
陈老师的博客：http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/先贴个暴力。。。每次暴力转移重心。。。bzoj能过[crayon-5994bd5015cf3428929064/]
02015年5月1日3,122线段树,树链剖分
【tyvj】五月有奖赛暨Loi 55 Round #1 Day1
题解http://pan.baidu.com/s/1bnjO0ij选择题（byDarkfalmes）[crayon-5994bd50162fa882030670/]王的对决！(byrainheart&seavot)[crayon-5994bd501630b557007051/]dC的肥皂（byskyfall（Orz））60暴力[crayon-5994bd5016316514980380/]DQS和序列（by帝江&Darkfalmes）[crayon-5994bd5016325690062625/] ...
22015年4月30日1,445递推与动规,线段树,广度搜索,筛法,莫比乌斯反演
【bzoj4034】[HAOI2015]T2
Description 有一棵点数为N的树，以点1为根，且树点有边权。然后有M个操作，分为三种：操作1：把某个节点x的点权增加a。操作2：把某个节点x为根的子树中所有点的点权都增加a。操作3：询问某个节点x到根的路径中所有点的点权和。Input 第一行包含两个整数N,M。表示点数和操作数。接下来一行N个整数，表示树中节点的初始权值。接下来N-1行每行三个正整数fr,to，表示该树中存在一条边(fr,to)。再接下来M行，每行分别表示一...
22015年4月30日3,723线段树,树链剖分
【bzoj1513】[POI2006]Tet-Tetris 3D
DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.Input第一行给出...
22015年4月28日2,122线段树
【bzoj2811】[Apio2012]Guard
DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。题解首先先将0的区间去除，可以用线段树TT如果去除0剩下的坐标编号等于忍者数，则所有剩下的坐标...
122015年4月24日2,809贪心,二分法,线段树