当前位置: 首页 > news >正文

划分树 K-th Number POJ - 2104

划分树,类似线段树,主要用于求解某个区间的第k 大元素(时间复杂度log(n))

讲解:https://www.cnblogs.com/hchlqlz-oj-mrj/p/5744308.html

大致就是分治递归的思想:

int tree[22][N]; //对应每层每个位置的数
int num[22][N]; //对应每层每个位置前面进入左孩子个数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int tree[22][N];
int num[22][N]; //进入左孩子个数
int n, m;
void build(int l, int r, int cur) {if(l == r) return;int mid = (l + r) >> 1;int lson = mid - l + 1;for(int i = l; i <= r; i++)if(tree[cur][i] < b[mid])lson--;int ln = l, rn = mid + 1;for(int i = l; i <= r; i++) {if(i == l) num[cur][i] = 0;else num[cur][i] = num[cur][i - 1];if(tree[cur][i] < b[mid] || (tree[cur][i] == b[mid] && lson > 0)) {tree[cur + 1][ln++] = tree[cur][i];num[cur][i]++;if(tree[cur][i] == b[mid]) lson--;} else {tree[cur + 1][rn++] = tree[cur][i];}}build(l, mid, cur + 1);build(mid + 1, r, cur + 1);
}
int query(int pl, int pr, int l, int r, int cur, int k) {if(l == r) return tree[cur][l];int lson;int mid = (l + r) >> 1;if(pl == l) lson = 0;else lson = num[cur][pl - 1];int cnt = num[cur][pr] - lson;if(cnt >= k) {return query(l + lson, l + num[cur][pr] - 1, l, mid, cur + 1, k);} else {int posr = mid + 1 + (pl - l - lson); // 右子树中第一个位置 return query(posr, posr + (pr - pl + 1 - cnt) - 1, mid + 1, r, cur + 1, k - cnt); }
}
int main() {int l, r, k;while(~scanf("%d %d", &n, &m)) {for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);b[i] = a[i];tree[0][i] = a[i];}sort(b + 1, b + 1 + n);build(1, n, 0);while(m--) {scanf("%d %d %d", &l, &r, &k);printf("%d\n", query(l, r, 1, n, 0, k));}}return 0;
} 

 

相关文章:

HDU - 3473 Minimum Sum 划分树

题目链接&#xff1a;https://cn.vjudge.net/problem/HDU-3473 题意&#xff1a;find a number x to make as small as possible! 题解&#xff1a;本来想三分x感觉会T&#xff0c;想了一下&#xff0c;当然x就是[l, r] 所有数的中位数了&#xff0c;至于为什么&#xff0c;可…...

问题 F: The King’s Ups and Downs dp

问题 F: The King’s Ups and Downs 时间限制: 1 Sec 内存限制: 128 MB 题目描述 The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than t…...

计算几何模板

二维几何&#xff1a; // 计算几何模板 //二维平面 using namespace std; const double eps 1e-8; const double inf 1e20; const double pi acos(-1.0); const int maxp 1010; //Compares a double to zero int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)…...

问题 E: Fruit Slicer n个圆求一条直线经过圆的数目最多

问题 E: Fruit Slicer 时间限制: 1 Sec 内存限制: 128 MB 提交: 25 解决: 4 [提交] [状态] [命题人:admin] 题目描述 John, a student who is taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the gam…...

问题 I: Monitoring Ski Paths 树链剖分+LCA+树状数组+贪心

问题 I: Monitoring Ski Paths 时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] [命题人:admin] 题目描述 Fresh powder on a sunny day: it is a great time to ski! Hardcore skiers flock to a large mountain in the Rockies to enjoy these perfect conditions. The …...

POJ - 3580 SuperMemo 伸展树

题目链接&#xff1a;https://cn.vjudge.net/problem/POJ-3580#author0 伸展树学习&#xff1a; 很全&#xff1a;https://blog.csdn.net/qq_33184171/article/details/73549164 图&#xff1a;https://blog.csdn.net/wr132/article/details/50599747 效率&#xff1a;http…...

3224: Tyvj 1728 普通平衡树 伸展树

题目链接&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id3224 题解&#xff1a;灵活运用&#xff0c;像这种不对区间操作的&#xff0c;相同的数放到一块就可以了 #include <bits/stdc.h> using namespace std; #define INF 2e9 10 const int N 1e5 …...

HDU - 1890 Robotic Sort 伸展树

题目链接&#xff1a;https://cn.vjudge.net/problem/HDU-1890 题意&#xff1a;每次将第i个位置到第i大的数所在位置 之间的数进行翻转&#xff0c;输出的是第i大的数所在的位置 题解&#xff1a;按照1-n建树&#xff0c;原序列排序&#xff0c;每次把节点 a[i].id 放到顶部…...

2019百度之星 - 复赛 HDU-6725 Diversity 树形dp

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6725 题解&#xff1a;每个节点要么取l[i]&#xff0c;要么取r[i]&#xff0c;对于每个节点维护下取最小最大值时的结果即可 #include <bits/stdc.h> using namespace std; typedef long long ll; cons…...

2019百度之星 - 复赛 HDU-6726 Transformation 搜索剪枝

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6726 题解&#xff1a;我们倒着往前找&#xff0c;对于&#xff08;a&#xff0c;2b-a&#xff09;->&#xff08;x&#xff0c;y&#xff09;那么xy为偶数&#xff0c;(x, y) 往前的话就是(x, (xy)/2)&…...

2019百度之星 - 复赛 HDU-6727 Quasi Binary Search Tree 构造 二叉树

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6727 题解&#xff1a;对于当前节点&#xff0c;肯定分为两个区间一个在左一个在右&#xff0c;就把小区间分到最小编号在的那个分支中&#xff0c;如果当前节点最小&#xff0c;那就尽可能让当前节点的标号小…...

2019 南京网络赛 A.The beautiful values of the palace 构造螺旋矩阵 + CDQ / 离线 + 树状数组

题目链接&#xff1a;https://nanti.jisuanke.com/t/41298 题解&#xff1a;首先我们要把每个坐标的val求出来&#xff0c;很明显每一圈的个数是一个等差数列&#xff0c;第x圈 a[x] -8x4n4&#xff0c;然后就是先等差前n项和求出之前每一圈的总个数&#xff0c;然后对于x 与…...

2018北京网络赛 HihoCoder - 1835 K-Dimensional Foil II 计算几何 贪心 二分

题目链接&#xff1a;https://vjudge.net/problem/HihoCoder-1835 题解&#xff1a;首先我们应该能想到到达图形的距离最近那肯定是垂直过去&#xff0c;也就是坐标变为(x1 - k, x2 - k, x3 - k...)&#xff0c;假设图形原点的坐标为(x10, x20, x30 ...)&#xff0c;如果某个x…...

2019南京网络赛 D.Robots 树上期望dp

题目链接&#xff1a;https://nanti.jisuanke.com/t/41301 题意&#xff1a;N个点M条边的有向无环图&#xff0c;1为唯一入度为0的点&#xff0c;N为唯一出度为0的点&#xff0c;现在你从1号点出发&#xff0c;每单位时间&#xff0c;你有相同的概率&#xff0c;走向下一节点或…...

bzoj1568: [JSOI2008]Blue Mary开公司 李超线段树

题目链接&#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id1568 李超线段树&#xff1a; 问题&#xff1a; 现在要求你在线动态维护一个二维平面直角坐标系&#xff0c;支持插入一条线段&#xff0c;询问与直线xx0相交的所有线段中交点y的最大/最小值 更新&a…...

牛客练习赛51 C、勾股定理 只一边求另外两边 结论

链接&#xff1a;https://ac.nowcoder.com/acm/contest/1083/C 来源&#xff1a;牛客网 勾股定理 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 32768K&#xff0c;其他语言65536K Special Judge, 64bit IO Format: %lld 题目描述 给出直…...

2019徐州网络赛 G Colorful String 马拉车+后缀

题目链接&#xff1a;https://nanti.jisuanke.com/t/41389 题解&#xff1a;马拉车处理回文串&#xff0c;每个位置记录后面每个字符出现的第一个位置&#xff0c;然后把每种字符额贡献加起来即可 #include<bits/stdc.h> using namespace std; typedef long long ll; c…...

2019徐州网络赛 I query 线段树 离线

题目链接&#xff1a;https://nanti.jisuanke.com/t/41391 题解&#xff1a;先找出每一对(pi​,pj​)&#xff0c;那么i&#xff0c; j 记录为 区间[l, r]&#xff0c;则查询就变为&#xff0c;在[L,R]内有多少区间&#xff0c;然后我们离线线段树就可以搞定了&#xff0c;按照…...

2019徐州网络赛 J、Random Access Iterator 树上 概率 dp

题目链接&#xff1a;https://nanti.jisuanke.com/t/41392 题解&#xff1a;dp[u] 表示 u这个点向下能到达最深深度的概率&#xff0c;因为对于每个点要找k次&#xff0c;只要其中有一次能到达最深即可&#xff0c;所以我们用容斥的思想&#xff0c;即表示为 1 - 不能到达最深…...

2019银川网络赛A? FZU - 2105 Digits Count 线段树 区间操作 | ^

题目链接&#xff1a;https://vjudge.net/problem/FZU-2105 其实我想放银川网络赛的链接&#xff0c;emmm 题解&#xff1a;首先或和与是能相互掩盖的&#xff0c;因此我们就可以把这两者用一个laz标记&#xff0c;laz1表示区间都变为1&#xff0c;laz-1表示区间都为0&#x…...

2019 徐州网络赛 F. Little M's attack plan 树上倍增+dfs序+二分

题目链接&#xff1a;https://nanti.jisuanke.com/t/41388 题解&#xff1a;这个题比赛最后也没改对&#xff0c;训练时突然想到有个地方写了emmmm 思路&#xff1a;我们先按照dfs序把每个点跑出来&#xff0c;然后vector记录下每个深度的点&#xff0c;很容易就可以想到&…...

HDU - 5489 Removed Interval LIS+枚举技巧

题目链接&#xff1a;https://vjudge.net/problem/HDU-5489 题解&#xff1a;删除m个后的最优的LIS在原序列中肯定存在一段间距大于等于m&#xff0c;那么我们就以这一段作为划分线&#xff0c;以后面第一个数x开始作为后半部分&#xff0c;那么后半部分的LIS我们可以倒着nlo…...

2019 南昌网络赛 C Hello 2019 / CodeForces - 750ENew Year and Old Subsequence 线段树维护矩阵

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-750E 题解&#xff1a;哇&#xff0c;原来这个也四个原题。。。。。。维护矩阵的还真是第一次做&#xff0c;这里就说一下CF那题的思路吧 因为最后要2017&#xff0c;那么我们分为5个子序列 空 2 20 201 2017 每…...

构造螺旋矩阵 n*m

构造n * m的螺旋矩阵 讲解&#xff1a;https://wenku.baidu.com/view/7253dc78a26925c52cc5bff4.htm #include <bits/stdc.h> using namespace std; int getnum(int n, int m, int x, int y) {int lev min(min(x, n - 1 - x), min(y, m - 1 - y));int d x y - lev *…...

2019 上海网络赛 B、 Light bulbs 区间差分 / 线段树点维护区间

题目链接&#xff1a;https://nanti.jisuanke.com/t/41399 题解&#xff1a;看见的第一思路应该都是差分&#xff0c;但是这个用数组肯定就gg了&#xff0c;所以当时的时候就想到动态开点线段树&#xff0c;mlog(n)但是T了&#xff0c;然后我就把点离散了一下&#xff0c;用点…...

2019 上海网络赛 G、Substring 字符串哈希

题目链接&#xff1a;https://nanti.jisuanke.com/t/41415 题解&#xff1a;对于两边的&#xff0c;要哈希出相应的权重&#xff0c;中间的字符顺序无所谓&#xff0c;只关心是什么字符&#xff0c;所以哈希出每个字符的权重即可。 官方题解&#xff1a; • 但是因为询问有2…...

2019 沈阳网络赛 H. Texas hold'em Poker 模拟

题目链接&#xff1a;https://nanti.jisuanke.com/t/41408 细心细心细心 #include <bits/stdc.h> using namespace std; const int N 1e5 10; struct node {char name[15];int id;int b[5]; }p[N]; int n; int a[10]; bool judge1() {for(int i 1; i < 5; i) {if…...

2019 沈阳网络赛 B. Dudu's maze dfs 联通块选取

题目链接&#xff1a;https://nanti.jisuanke.com/t/41402 题解&#xff1a;首先和1联通的糖果屋都能到达&#xff0c;其他不能到达的肯定被恶魔屋挡住了&#xff0c;那就在挡住的所以恶魔屋中选择一个最优的就可以了&#xff0c;怎么算最优呢&#xff0c;因为到达恶魔屋之后&…...

51nod 1571 最近等对 CQD分治

题目链接&#xff1a;https://www.51nod.com/Challenge/Problem.html#problemId1571 现在有一个序列 a1, a2, ..., ana1, a2, ..., an &#xff0c;还有m个查询 lj, rj (1 ≤ lj ≤ rj ≤ n)lj, rj (1 ≤ lj ≤ rj ≤ n) 。对于每一个查询&#xff0c;请找出距离最近的两个元素…...

牛客 Fruit Ninja 随机大法

链接&#xff1a;https://ac.nowcoder.com/acm/contest/163/A 来源&#xff1a;牛客网 题目描述 Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of…...

HDU - 6242 Geometry Problem 随机数

题目链接&#xff1a;https://vjudge.net/problem/HDU-6242 题意&#xff1a;n个点&#xff0c;找到一个圆&#xff0c;满足圆上点的数目大于等于⌈N / 2⌉ 题解&#xff1a;三个不在一条直线上的点确定一个圆&#xff0c;随机到圆上点的概率是1 / 2&#xff0c;那么三次就是…...

HDU - 6393 Traffic Network in Numazu 树上倍增求lca+dfs序+线段树

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6393 题意&#xff1a;n个点n条边的图&#xff0c;求两点间的最小距离 题解&#xff1a;如果是一个树的话&#xff0c;那么我们就可以倍增dfs序&#xff0c;然后用线段树维护下就可以了这样是nlogn的复杂度&a…...

CodeForces - 1220D Alex and Julian 二分图性质

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220D 题意&#xff1a;n个数&#xff0c;如果节点 i 和 j 满足 |i - j | 属于B&#xff0c;则i和j有一条边&#xff0c;问B集合最少删除多少边&#xff0c;使得得到的图是个二分图 题解&#xff1a;根据二分图的…...

CodeForces - 1220E Tourism 无向图缩点+树形dp

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220E 题意&#xff1a;n个点m条边的无向连通图&#xff0c;起点s&#xff0c;每个点有权值&#xff0c;求遍历无向图得到的最大权值和。但是不能走回头路&#xff0c;即如果从U走到V那么下一步不可以从V走到U 题…...

HDU - 6156 Palindrome Function 数位dp

题目链接&#xff1a;https://vjudge.net/problem/HDU-6156 题意&#xff1a;区间[L, R]的数&#xff0c;写成k进制(l<k<r)后&#xff0c;如果是回文串&#xff0c;那么f(x,k)k,否则f(x,k)1&#xff0c;对f求和 题解&#xff1a;一看这种题就是数位dp&#xff0c;当时想…...

HDU - 6153 A Secret 扩展kmp

题目链接&#xff1a;https://vjudge.net/problem/HDU-6153 题意&#xff1a;对于s2的每一个后缀&#xff0c;假设长度为l&#xff0c;在s1出现的次数为k&#xff0c;求l*k的和 题解&#xff1a;我们把两个串都倒过来&#xff0c;变为s1,s2&#xff0c;那么问题就变为&#x…...

Gym - 100589A Queries on the Tree 树状数组+分块

题目链接&#xff1a;https://vjudge.net/problem/Gym-100589A 题意&#xff1a;n个点&#xff0c;根节点为1的树&#xff0c;两种操作&#xff0c;1 L y 与根节点距离为L的节点权值全部加上y&#xff0c;2 x x子树的权值总和 题解&#xff1a;对于更新操作&#xff0c;因为更…...

HDU-6731 Angle Beats 计算几何 直角三角形个数

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6731 题意&#xff1a;n个点&#xff0c;m次查询&#xff0c;每次给你一个点&#xff0c;从n个点挑出两个能组成多少直角三角形 题解&#xff1a;假设询问的是点p&#xff0c;直角可能是p也可能是其他两点的某…...

HDU - 5927 Auxiliary Set dfs序+瞎搞

题目链接&#xff1a;https://vjudge.net/problem/HDU-5927 题意&#xff1a;给一棵树,然后每次询问时给出哪些点是不重要的点,让求这棵树上重要的点以及是两个不同的重要的点的lca一共有多少个 题解&#xff1a;我们只需要看给出的每一个不重要的点是不是重要的点就可以了&a…...

CodeForces - 689D Friends and Subsequences ST表+二分

题目链接&#xff1a;https://codeforces.com/problemset/problem/689/D 题意&#xff1a;有多少区间[l, r]满足&#xff0c;max(al..ar) min(bl..br) 题解&#xff1a;对于先固定l&#xff0c;那么对于max(a)&#xff0c;是一个递增的序列&#xff0c;对于min(b)是一个递减…...

2017南宁 I. Rake It In dfs博弈

题目链接&#xff1a;https://nanti.jisuanke.com/t/A1538 题解&#xff1a;因为k只有3&#xff0c;所以最多取6次&#xff0c;每次有9种选取可能&#xff0c;所以直接dfs选取即可 #include <bits/stdc.h> using namespace std; typedef long long ll; int b[6][6]; in…...

CodeForces - 369E Valera and Queries 树状数组+离线+容斥思想

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-369E 题意&#xff1a;n条线段&#xff0c;m次询问&#xff0c;给出cnt个点&#xff0c;问这些点在多少线段上 题解&#xff1a;如果每个点对于所在的线段上没有影响的话&#xff0c;那么我们就可以建立权值线段树…...

Gym - 101889I Imperial roads 树链剖分+最小生成树之必选一边

题目链接&#xff1a;https://vjudge.net/problem/Gym-101889I 题意&#xff1a;n个点&#xff0c;m条边&#xff0c;q次询问&#xff0c;每次必须选一边&#xff0c;求最小生成树的权值 题解&#xff1a;我们先跑一边最小生成树&#xff0c;然后按照最小边建树&#xff0c;必…...

CodeForces - 1228C Primes and Multiplication 数贡献

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1228C 题解&#xff1a;把x的每个质因子找出来&#xff0c;计算n&#xff01;对每个因子的贡献 #include <bits/stdc.h> using namespace std; typedef long long ll; const ll mod 1e9 7; const int N …...

CodeForces - 1228D Complete Tripartite 图上的哈希

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1228D 题解&#xff1a;我们把每个点哈希&#xff0c;这样就能计算出和每个点连接的其他点的总哈希值&#xff0c;若只有三种哈希值的和&#xff0c;那么就是符合的&#xff0c;当然还有其他很多种做法。 #includ…...

2017 ICPC Asia Urumqi I. A Possible Tree 带权并查集

题目链接&#xff1a;https://nanti.jisuanke.com/t/40520 题解&#xff1a;因为他们都是联通的且只有唯一路径&#xff0c;所以不用管之前怎么连的&#xff0c;直接按照他给的查询&#xff0c;带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

HDU - 5923 Prediction 多个并查集

题目链接:https://vjudge.net/problem/HDU-5923 题解:因为n只有500个&#xff0c;所以我们可以每个点维护一个并查集&#xff0c;所以判断某些点的时候&#xff0c;这些并查集在合起来即可 #include <bits/stdc.h> using namespace std; const int N 510; struct edge…...

2018徐州 Gym - 102028J Carpets Removal 概率事件+二维差分

题目链接&#xff1a;https://vjudge.net/problem/Gym-102028J 题意&#xff1a;去掉两个矩形&#xff0c;让剩下的矩形覆盖的点最少 题解&#xff1a;使剩下的点少&#xff0c;那么我们就是去掉的两个矩形覆盖的尽可能多&#xff0c;也就是两个矩形各自占据的格子和只有两个…...

Gym - 102307J Jail Destruction 线段树

题目链接&#xff1a;https://vjudge.net/problem/Gym-102307J The semester has just begun at Universidad Nacional (UNAL). As usual, a group of vandals enjoys bringing chaos to all students and damaging the university facilities. Those guys have been planning…...

Gym - 101955L Machining Disc Rotors 计算几何 圆剩余部分直径

题目链接&#xff1a;https://vjudge.net/problem/Gym-101955L 题意&#xff1a;n个圆和 圆(0&#xff0c;0&#xff0c;R) 部分相交&#xff0c;求剩余圆的直径 题解&#xff1a;如果剩余部分存在直径的话&#xff0c;那就是2*R&#xff0c;这个怎么判断呢&#xff0c;对于每…...