整体二分解法
调了 n 久！！！
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 220000
#define inf 1000000000
using namespace std;
struct query
{
int x, y, k, s;
}q[maxn<<1], q1[maxn<<1], q2[maxn<<1];
int a[maxn], ans[maxn];
int n, m;
struct BIT {
long long bit[maxn];
inline void init() {
memset(bit, 0, sizeof(bit));
}
inline int lowbit(int x) {
return x&-x;
}
inline int sum(int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= lowbit(i);
}
return res;
}
inline void add(int i, int x) {
while (i <= n) {
bit[i] += x;
i += lowbit(i);
}
}
}T;
void divide(int head, int tail, int l, int r) {
int mid = (l + r) >> 1;
int tmp = 0;
if (head > tail)
return;
if ( l == r) {
for (int i = head; i <= tail; i++) {
ans[q[i].s] = l;
}
return;
}
T.init();
for (int i = 1; i <= n; i++){
if (a[i] <= mid)
T.add(i, 1);
}
int L1 = 0, L2 = 0;
for (int i = head; i <= tail; i++) {
tmp = T.sum(q[i].y) - T.sum(q[i].x-1) - q[i].k;
if (tmp < 0) {
q2[++L2] = q[i];
}
else {
q1[++L1] = q[i];
}
}
for (int i = 1; i <= L1; i++) {
q[head+i-1] = q1[i];
}
for (int i = 1; i <= L2; i++) {
q[head + L1-1+i] = q2[i];
}
divide(head, head+L1 -1, l, mid);
divide(head+L1, tail, mid+1, r);
return ;
}
int main()
{
memset(q, 0, sizeof(q));
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++) {
scanf("%d", &a[i]);
}
int x, y, k;
for (int i=1; i<=m; i++) {
scanf("\n%d%d%d", &x, &y, &k);
q[i].x = x; q[i].y = y;
q[i].k = k; q[i].s = i;
}
//divide(1, m, 0, inf);
divide(1, m, -inf, inf);
for (int i = 1; i<=m; i++)
printf("%lld\n", ans[i]);
return 0;
}
我的不成熟算法
之前自己写了个整体快排算法（自定义的名词～～，和快排有一定的相似性，但并非是个排序算法～～～），求单个区间的 Kth 大可以用快排。这种方法用在本题上肯定会 TLE ！。
首先第一步计算每个 [L, R] 区间内的小于 mid 的数，这样就可以知道 mid 在 [L， R] 区间的排名。如果某个 [L, R] 区间有 求第 101 大的数，且已知在该区间有 100 个数大于 mid。我们将遍历该区间，保存第一个碰到的大于 mid 的数。后面的就是冒泡算法！ 这个算法的缺点就是需要完全地遍历 [L, R] 区间！！ 如果 [L, R]区间中的大于 mid 的数要远远小于 kth， 那就增大 mid 后，再比较！！至于其它的情况，聪明的你肯定是懂的。 因为 n 个query 的结果肯定是 分散在 [-n, n] 空间内，可以通过比较 mid 数的方式将 n 个query 按结果分区。最终肯定能得出答案 [-n, -n+100] 有 m1 个 query， 在 [-n+101, -n +200] 有 m2 个query ......。因为采用的是树状数组，可以很快地求出每个 [L, R] 区间内大于某个数的数！可以根据这个来遍历一次获取到相应的 kth num。 这里使用的二分思想和划分树的很像！
CDQ 分治
莫队
感觉像是 DP 算法 + 分块算法的结合体， 因为莫队算法用存储中间结果用于下次计算（DP 中的存储中间结果进行状态转移）. 中间也碰到一次踩内存的问题， 而且我的算法需要 1735 ms，这个有点长啊莫队就是 “有条理的暴力”， 如果数据量再大量就需要莫队套莫队
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
const int maxn = 1e5+10;
const int maxq = 1e4+5;
const int inf = 1e9+5;
using namespace std;
int ans[maxq];
int n, m, qbsize, vbsize; // bsize means bulk size 一开始没有区分 qbsize, vbsize 导致程序后面踩内存，都写到 sumv[344] 时，即将数据写到 b[0] 上
int uniq_n[maxn], sumv[340], b[maxn], uniq_c = 0; // 340 ~= sqrt(1e5+10)
struct Num {
int val, pos, rank, bulk_rank;
bool operator <(const Num &a)const {
return val < a.val;
}
} sorted_num[maxn], num[maxn]; // 这样比较占用内存，有没有其它的方法？求解？
struct Query {
int l, r, k, s;
int lbulk, rbulk; // 用于莫队排序
bool operator <(const Query &a)const {
return lbulk == a.lbulk? rbulk < a.rbulk: lbulk < a.lbulk;
}
} q[maxq];
void init() {
memset(b, 0, sizeof(b));
memset(uniq_n, 0, sizeof(uniq_n));
memset(sumv, 0, sizeof(sumv));
memset(q, 0, sizeof(q));
memset(ans, 0, sizeof(ans));
memset(num, 0, sizeof(num));
memset(sorted_num, 0, sizeof(sorted_num));
}
void insert(struct Num &x) {++b[x.rank]; ++sumv[x.bulk_rank]; }
void eraser(struct Num &x) {--b[x.rank]; --sumv[x.bulk_rank]; }
int Kth(int k) {
int cnt = 0;
for (int i = 1; i<= uniq_c/vbsize+1; i++) {
cnt += sumv[i];
if (cnt >= k) {
cnt -= sumv[i];
for (int j = (i-1)*vbsize; ; j++) {
cnt += b[j];
if (cnt >= k) return uniq_n[j];
}
}
}
}
int main(int argc, char *argv[]) {
int x, y, k;
init();
scanf("%d%d", &n, &m);
qbsize = (int) sqrt(m*1.0); vbsize = (int) sqrt(n*1.0);
// 获取输入数据并排序
for (int i=1; i<=n; i++) {
scanf("%d", &sorted_num[i].val);
sorted_num[i].pos = i;
}
sort(sorted_num+1, sorted_num+n+1);
sorted_num[0].val = 0 - sorted_num[1].val;
for (int i=1; i<=n; i++) {
if (sorted_num[i].val != sorted_num[i-1].val) uniq_c++;
uniq_n[uniq_c] = sorted_num[i].val;
sorted_num[i].rank = uniq_c; sorted_num[i].bulk_rank = uniq_c/vbsize + 1;
num[sorted_num[i].pos] = sorted_num[i];
}
// 获取查询语句
for (int i=1; i<=m; i++) {
scanf("%d%d%d", &x, &y, &k);
q[i].l = x; q[i].r = y;
q[i].k = k; q[i].s = i;
q[i].lbulk = x/qbsize; q[i].rbulk = y/qbsize;
}
sort(q+1, q+1+m);
// 开始查询，并将结果存入数组中
for (int i = q[1].l; i<=q[1].r; i++) insert(num[i]);
ans[q[1].s] = Kth(q[1].k);
for (int i=2; i<=m; i++) {
if(q[i].l<q[i-1].l) for(int j=q[i-1].l-1;j>=q[i].l;--j) insert(num[j]);
else for(int j=q[i-1].l;j<q[i].l;++j) eraser(num[j]);
if(q[i].r<q[i-1].r) for(int j=q[i-1].r;j>q[i].r;--j) eraser(num[j]);
else for(int j=q[i-1].r+1;j<=q[i].r;++j) insert(num[j]);
ans[q[i].s] = Kth(q[i].k);
}
for (int i = 1; i<=m; i++)
printf("%d\n", ans[i]);
return 0;
}
主席树
这题有神坑，将 input 数组放到结构体 Segment 内部，用 sort 函数排序就会各种踩内存。我只输入 10000 个数字，结果程序每次都会 coredump（sort 函数踩内存，将记录数字数字的 input pos 的值都修改改到 40000+～～～）。我的代码写的太长了，有 50 多行的版本 http://blog.csdn.net/su20145104009/article/details/51439339 （不过她的代码，在好多的地方没有换行。那份代码很难理解，我一眼没看懂就不看了～）。还有 http://www.cnblogs.com/zyf0163/p/4749042.html 的代码（只有61 行，而且比较好理解）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
const int maxn = 1e5+10;
const int inf = 1e9+5;
const int maxq = 1e4+5;
using namespace std;
struct query
{
int x, y, k;
}q[maxq];
int ans[maxn];
int n, m;
struct InputD{
int val;
int input_pos;
int rank;
int index;
bool operator <(const InputD &a)const {
return val < a.val;
}
} input[maxn]; //之前将 input 放到Segment 内，结果 sort 函数各种错误！内存踩的飞起!
struct Segment {
// 因为不需要修改
struct _nod{
int sums;
int l, r;
int leftson, rightson;
} TreeNode[maxn * 20]; //之前只开到 maxn<<2, 结果爆内存
int _lazy_add_seq[maxn]; //这个数据结构只可用于 lazy_add 和 force_add 这两个函数
int cnt; // cnt = 0 用于空白树
void init() {
cnt = 0;
memset(TreeNode, 0, sizeof(TreeNode));
memset(input, 0, sizeof(input));
memset(_lazy_add_seq, 0, sizeof(_lazy_add_seq));
}
int cnt_increment() {
return ++cnt;
}
void build_blank_tree (int index, int l, int r) {
int mid = (l+r) >> 1, leftson, rightson;
if (l == r) {
TreeNode[index].l = TreeNode[index].r = l;
return;
}
leftson = ++cnt; rightson = ++cnt;
TreeNode[index].l = l; TreeNode[index].r = r;
TreeNode[index].leftson = leftson; TreeNode[index].rightson = rightson;
/*
if (l == r)
return; 如果这里退出，会造成大量的 cnt 没被使用而导致内存溢出
*/
build_blank_tree(leftson, l, mid); build_blank_tree(rightson, mid+1, r);
return;
}
void force_add() {
int tindex, mid, preindex;
int son;
for (int i=1; i<=n; i++) {
tindex = input[_lazy_add_seq[i]].index;
preindex = tindex - 1;
while (true){
TreeNode[tindex] = TreeNode[preindex];
TreeNode[tindex].sums += 1;
mid = (TreeNode[tindex].l + TreeNode[tindex].r) >> 1;
if (TreeNode[tindex].l == TreeNode[tindex].r)
break;
if (mid >= input[_lazy_add_seq[i]].rank) {
son = cnt_increment();
TreeNode[tindex].leftson = son;
tindex = son; preindex = TreeNode[preindex].leftson;
}
else {
son = cnt_increment();
TreeNode[tindex].rightson = son;
tindex = son; preindex = TreeNode[preindex].rightson;
}
}
}
return ;
}
void lazy_add(int i, int pos) {
_lazy_add_seq[pos] = i;
}
int query(int l, int r, int k) {
int t1 = l-1, t2 = r;
int leftdiff, rightdiff;
while (true) {
if (TreeNode[t2].l == TreeNode[t2].r)
return input[TreeNode[t2].l].val;
leftdiff = TreeNode[TreeNode[t2].leftson].sums - TreeNode[TreeNode[t1].leftson].sums;
rightdiff = TreeNode[TreeNode[t2].rightson].sums - TreeNode[TreeNode[t1].rightson].sums;
if (leftdiff >= k) {
t1 = TreeNode[t1].leftson; t2 = TreeNode[t2].leftson;
}
else {
t1 = TreeNode[t1].rightson; t2 = TreeNode[t2].rightson;
k -= leftdiff;
}
}
}
}T;
int main(int argc, char *argv[]) {
int x, y, k;
T.init();
memset(q, 0, sizeof(q));
scanf("%d%d", &n, &m);
// get input data
for (int i=1; i<=n; i++) {
scanf("%d", &input[i].val);
input[i].index = T.cnt_increment();
input[i].input_pos = i;
}
// get input query
for (int i=1; i<=m; i++) {
scanf("%d%d%d", &x, &y, &k);
q[i].x = x; q[i].y = y; q[i].k = k;
}
// build blank tree
T.build_blank_tree(0, 1, n);
sort(input+1, input+n+1); //应该是踩内存了
// add data
do {
for (int i=1; i<=n; i++) {
input[i].rank = i;
T.lazy_add(i, input[i].input_pos);
}
T.force_add();
} while (0);
// query!
for (int i = 1; i<=m; i++)
printf("%d\n", T.query(q[i].x, q[i].y, q[i].k));
return 0;
}
划分树
/*
* 参考资料 url: https://www.cnblogs.com/hchlqlz-oj-mrj/p/5744308.html
*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
const int maxn = 1e5+10;
const int inf = 1e9+5;
using namespace std;
int ans[maxn], a[maxn+1];
int n, m, num = 0;
struct HuafengTree {
struct data {
int val;
int sums; // little than mid !
} data[20][maxn+1];
void init(){
memset(data, 0, sizeof(data));
}
void build(int l, int r, int level) { //似乎还不能解决有重复数字的题目！
int p1 = 0, p2 = 0;
int mid = (l+r) >> 1;
if (l == r)
return ;
for (int i = l; i <= r; i++) {
if (data[level][i].val <= a[mid]) {
data[level][i].sums = get_sum(l, i-1, level) + 1;
data[level+1][++p1+l-1].val = data[level][i].val;
}
else {
data[level][i].sums = get_sum(l, i-1, level);
data[level+1][++p2+mid].val = data[level][i].val;
}
}
if (p1 > 0)
build(l, mid, level+1);
if (p2 > 0)
build(mid+1, r, level+1);
return;
}
int get_sum(int l, int t, int level) {
if (t >= l )
return data[level][t].sums;
else
return 0;
}
int look(int ceng,int sl,int sr,int l,int r,int k)
{
if(sl==sr) return data[ceng][sl].val;
int ly; //ly 表示l 前面有多少元素进入左孩子
if(l==sl) ly=0; //和左端点重合时
else ly=data[ceng][l-1].sums;
int tolef=data[ceng][r].sums-ly; //这一层l到r之间进入左子树的有tolef个
if(tolef>=k)
{
return look(ceng+1,sl,(sl+sr)/2,sl+ly,sl+data[ceng][r].sums-1,k);
}
else
{
// l-sl 表示l前面有多少数，再减ly 表示这些数中去右子树的有多少个
int lr = (sl+sr)/2 + 1 + (l-sl-ly); //l-r 去右边的开头位置
// r-l+1 表示l到r有多少数，减去去左边的，剩下是去右边的，去右边1个，下标就是lr，所以减1
return look(ceng+1,(sl+sr)/2+1,sr,lr,lr+r-l+1-tolef-1,k-tolef);
}
}
}T;
int main(int argc, char *argv[]) {
int x, y, k;
T.init();
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++) {
scanf("%d", &a[i]);
T.data[0][i].val = a[i];
}
sort(a+1, a+1+n);
T.build(1, n, 0);
for (int i=1; i<=m; i++) {
scanf("%d%d%d", &x, &y, &k);
printf("%d\n", T.look(0, 1, n, x, y, k));
}
/*
for (int i = 1; i<=m; i++)
printf("%d\n", ans[i]);
*/
return 0;
}
在写查询功能时，一直没写对边界值判断。 最后只好 copy 网上资料～～谁让我在这么大的高龄学习 acm 算法～～。上面的代码不能很好地处理有重复数字的数据（ https://www.cnblogs.com/hchlqlz-oj-mrj/p/5744308.html 上的代码能处理处理重复数据，
为什么我没有想到呢？ 主要是自己刚接触相关算法，觉得对于某类问题。必然能被某个高级数据结构秒掉。所以不会往暴力的方向想！）
树套树
只要内存大，区间问题都可以用树套树。树套树真毒瘤
转载于:https://www.cnblogs.com/tmortred/p/7992399.html
相关资源：数据结构—成绩单生成器
