主席树 - hzwer.com

2016 CCPC Changchun Onsite
hdu5912.Fraction计算连分数的答案，直接模拟即可[crayon-683bd02b15fdd284345251/]hdu5914.Triangle问长度1到n的线段，至少要去掉多少，使得剩下的线段无法构成三角形\(1\leqn\leq20\)斐波那契数列，手算完打表[crayon-683bd02b15fe8294958388/]hdu5916.HarmonicValueDescription定义全排列的权值为相邻两个数的gcd，求1到n的所有全排列中第K小的排列\(1\leq2k\leqn\leq10000\)容易发现，第k大的全排列的权值为n-2+k构造方式...
02016年11月6日6,020递推与动规,模拟,KMP,贪心,深度搜索,构造,主席树,二分法

「CF538X」Codeforces Round #300
A.CuttingBanner枚举切掉中间部分匹配[crayon-683bd02b172a8015021912/]B.QuasiBinary用最少的只包含01的数凑出n每次贪心在非0位上取1[crayon-683bd02b172b1051005132/]C.Tourist'sNotes根据每俩个的时间及高度差可计算答案[crayon-683bd02b172b6715246077/]D.WeirdChess暴力暴力暴力[crayon-683bd02b172bb245267051/]E.DemiurgesPlayAgain考虑进入某个根，最终会取得子树第几小的叶子[crayon-683bd02b172c1655421...
02015年4月27日7,075模拟,贪心,主席树,调和级数
「BZOJ3932」[CQOI2015] 任务查询系统
好好的一道主席树题我写成了树状数组套主席树TT原因是为了练习模板（一开始根本没想。。。）TTbzoj16s通过，倒数第二是9s。。。多个log萌萌哒[crayon-683bd02b177e6162544328/] ...
72015年4月8日7,865主席树,树状数组
「BZOJ3772」精神污染
Description兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游，为了方便...
02015年1月27日6,431dfs序,主席树
「BZOJ3514」Codechef MARCH14 GERALD07加强版
DescriptionN个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。Input第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。接下来M行，代表图中的每条边。接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为Lxorlastans和Rxorlastans。Output K行每行一个整数代表该组询问的联通块...
32014年9月11日8,101主席树,link cut tree
「BZOJ3551」[ONTAK2010] Peaks加强版
Description「题目描述」同3545Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk，表示一组询问。v=vxorlastans，x=xxorlastans，k=kxorlastans。如果lastans=-1则不变。Output同3545HINT「数据范围」同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树，但合并两结点x，y的时新建结点ext，把ext连向fa...
22014年8月30日9,088kruskal,主席树
「BZOJ2588」SPOJ 10628. Count on a tree
Description给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答uxorlastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。Input第一行两个整数N,M。第二行有N个整数，其中第i个整数表示点i的权值。后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。最后M行每行两个整数(u,v,k)，表示一组询问。OutputM行，表示每个询问的答案。SampleInput8...
62014年6月17日8,162主席树
「POJ2104」K – th Number
DescriptionYouareworkingforMacrohardcompanyindatastructuresdepartment.Afterfailingyourprevioustaskaboutkeyinsertionyouwereaskedtowriteanewdatastructurethatwouldbeabletoreturnquicklyk-thorderstatisticsinthearraysegment.Thatis,givenanarraya[1...n]ofdifferentintegernumbers,yourprogrammustansweraseriesofquestionsQ(i,j,k)intheform:"Whatwouldbethek-thnumberina[i...j]segment,ifthissegmentwassorted...
02014年5月14日9,500树套树,treap,主席树,线段树
「BZOJ1901」Zju2112 Dynamic Rankings
Description给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。第一行有两个正整数n(1≤n≤...
12014年4月28日8,986主席树,树状数组
「BZOJ3524 / 2223」[POI2014] Couriers
Description给一个长度为n的序列a。1≤a[i]≤n。m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。Input第一行两个数n，m。第二行n个数，a[i]。接下来m行，每行两个数l,r，表示询问[l,r]这个区间。Outputm行，每行对应一个答案。SampleInput7511323431314371766SampleOutput10304HINT「数据范围」n,m≤500000SourceByDzy题解coolinging：可持久化...
32014年4月19日7,354主席树