我们知道我们可以通过主席树来维护静态区间第K大值.我们又知道主席树满足可加性,所以我们可以用树状数组来维护主席树,树状数组的每一个节点都可以开一颗主席树,然后一起做. 我们注意到树状数组的每一棵树都和前一颗树没有关系,so,并不需要可持久化,一个朴素的权值线段树就可以啦. 我们知道普通的线段树是刚开始就把所有的节点都开了,但我们发现并不需要,因为每个点里的操作并不是很多,很大一部分的节点是用不到的,那么我们就可以不开.用Ls 和 Rs 来记左右儿子的地址,随用随开即可. #include<bit

L3-002. 堆栈 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除).现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值.对于N个元素,若N是偶数,则中值定义为第N/2个最小元:若N是奇数,则中值定义为第(N+1)/2个最小元. 输入格式: 输入第一行给出正整

Distance on the tree DSM(Data Structure Master) once learned about tree when he was preparing for NOIP(National Olympiad in Informatics in Provinces) in Senior High School. So when in Data Structure Class in College, he is always absent-minded about

主席树的实质其实还是一颗线段树, 然后每一次修改都通过上一次的线段树,来添加新边,使得每次改变就改变logn个节点,很多节点重复利用,达到节省空间的目的. 1.不带修改的区间第K大. HDU-2665 模板题 代码: #include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt",&q

题目链接: http://poj.org/problem?id=2104 K-th Number Time Limit: 20000MSMemory Limit: 65536K 问题描述 You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data

传送门:Color the ball Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 25511    Accepted Submission(s): 12393 Problem Description N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele

题意:题目太玄了我无法用语言精简.. 题目要求的操作1是基于值的,所以用普通线段树基本无法维护(反正我不知道) 换做权值型后十分好做,因为连接处必然是更后面的,这时比较一下位置就好 PS.感觉周赛越来越硬核了 #include<bits/stdc++.h> #define rep(i,j,k) for(register int i=j;i<=k;i++) #define print(a) printf("%lld",(ll)(a)) #define println(a

点权树的模板题,另外发现树状数组也是可以区间更新的.. 注意在对链进行操作时方向不要搞错 线段树版本 #include<bits/stdc++.h> using namespace std; #define maxn 50005 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 ]; int a[maxn],head[maxn],tot; int deep[maxn],fa[maxn],son[maxn],num[max

和去年多校的CSGO一样,用状态压缩来求Manhattan距离的最大值 然后要用线段树维护一下区间最大值 /* k维空间给定n个点,两个操作 1 i b1 b2 .. bk : 修改第i个点的坐标 2 l r:询问[l,r]区间点最大的曼哈顿距离 先考虑不带修: 线段树维护区间2^5种状态的最大值 查询时只要求出相对的两个状态的最大值即可 关于这个贪心的证明: 首先因为绝对值,所以aij前面带的符号可能是-也可能是+,总共就是有关2^k种可能 那么考虑每种状态 S 的最大值,加上相对这种状态 (

Given a registry of all houses in your state or province, you would like to know the minimum size of an axis-aligned square zone such that every house in a range of addresses lies in the zone or on its border. The zoning is a bit lenient and you can

901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 7025  Solved: 2925[Submit][Status][Discuss] 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]

Just h-index Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 438    Accepted Submission(s): 203 Problem Description The h-index of an author is the largest h where he has at least h papers wit

[BZOJ 3110] [luogu 3332] [ZJOI 2013]k大数查询(权值线段树套线段树) 题面 原题面有点歧义,不过从样例可以看出来真正的意思 有n个位置,每个位置可以看做一个集合. 1 a b c :在a-b的每个集合中插入一个数c 2 a b c :2:询问将a-b的每个集合合并到一起后所有元素的第c大 分析 外层用权值线段树维护值,内层用普通线段树维护位置 我们先考虑全局询问第k大的情况,显然只需要权值线段树维护全局值的出现情况,区间[L,R]存储值落在[L,R]内的元素数

主席树基本操作:静态区间第k大 #include<bits/stdc++.h> using namespace std; typedef long long LL; ,MAXN=2e5+,SIZE=MAXN*; int N,M,K; int tmp[MAXN],A[MAXN],rt[MAXN],order[MAXN]; int sz,lson[SIZE],rson[SIZE],sum[SIZE]; int init(int l,int r){ int cur=++sz; if(l<r){

“队列进出图上的方向 线段树区间修改求出总量 可持久留下的迹象 我们 俯身欣赏” ----<膜你抄>     线段树很早就会写了,但一直没有总结,所以偶尔重写又会懵逼,所以还是要总结一下. 引言 在生活和竞赛中,我们总是会遇上一些问题,比如说令人厌恶的统计成绩,老师会想询问几个人中成绩最低的是谁...... 于是问题出现了.   e.g.1(暴力膜不可取) 已知班上有50个学生,学号分别为1-50,老师想问学号为a-b之间的最低分是多少 比如 2 5 3 4 1中 2-4 之间的最小值为 3

然而过不去你谷的模板 思路: 值域线段树\([l,r]\)代表一棵值域在\([l,r]\)范围内的点构成的一颗平衡树 平衡树的\(BST\)权值为点在序列中的位置 查询区间第\(k\)大值时 左区间在\([l,r]\)范围内的树的大小与\(k\)比较 大了进去,小了减掉换一边 关于建树 递归建估计是\(O(nlog^2n)\)的 Code: #include <cstdio> #include <cstdlib> #include <algorithm> #includ

题目描述 小时候的雨荨非常听话,是父母眼中的好孩子.在学校是老师的左右手,同学的好榜样.后来她成为艾利斯顿第二代考神,这和小时候培养的良好素质是分不开的.雨荨的妈妈也为有这么一个懂事的女儿感到高兴.一次期末考试,雨荨不知道第多少次,再次考了全年级第一名.雨荨的妈妈看到女儿100分的成绩单时,脸上又泛起了幸福的笑容,作为奖励,她给雨荨买了n个布娃娃.细心的雨荨发现,第i个布娃娃有一个耐心值P[i]以及一个魅力值C[i],并且还有能够忍受的耐心值的上限R[i]以及下限L[i].当一个布娃娃j满足L[

layout: post title: HDU-6704 K-th occurrence (后缀自动机father树上倍增建权值线段树合并) author: "luowentaoaa" catalog: true tags: mathjax: true - kuangbin - 字符串 " target="_blank" style="font-size:24px;">传送门 题意 给出一个长度为\(n\)字符串\(s\), \(

题目大意:有一些位置.这些位置上能够放若干个数字. 如今有两种操作. 1.在区间l到r上加入一个数字x 2.求出l到r上的第k大的数字是什么 思路:这样的题一看就是树套树,关键是怎么套,怎么写.(话说我也不会来着..)最easy想到的方法就是区间线段树套一个权值线段树.可是区间线段树上的标记就会变得异常复杂.所以我们就反过来套,用权值线段树套区间线段树. 这样改动操作在外线段树上就变成了单点改动.外线段树就不用维护标记了.在里面的区间线段树上维护标记就easy多了.详细实现见代码. CODE:

题目描述 有N个位置,M个操作.操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c.如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少. 输入 第一行N,M接下来M行,每行形如1 a b c或2 a b c 输出 输出每个询问的结果 样例输入 2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 样例输出 1 2 1 题解 本蒟蒻并不会写整体二分,所以写了树套树 17.12.23 UPD:比