Input
The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each
description consists of three numbers: i, j, and k (1 <= i <= j
<= n, 1 <= k <= j - i + 1) and represents the question Q(i, j,
k).
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each
description consists of three numbers: i, j, and k (1 <= i <= j
<= n, 1 <= k <= j - i + 1) and represents the question Q(i, j,
k).
Output
For each question output the answer to it --- the k-th number in sorted a[i...j] segment.
刚学了下划分树，写写理解;
如果有线段树与快排 的基础，很容易能理解划分树的；这里讲解得很好
思路:在tree[deep][i]中,下一层是对上一层的一个二叉排序，即左子树中没有大于tree[deep][mid]的，右子树中没有小于tree[deep][mid]的；但是等于的随便在左子树还是在右子树中；在快排中，不需要保存元素之间的前后顺序，所以直接双指针"补空位"，但是在寻找第k小时，在同一颗子树中不能改变元素的顺序，所以在建树时，要预先处理出左子树中与[mid]值相等的数的个数即same值；之后直接从ls,rs;(实现细节详见代码)
在查询时，确实就像是线段树的区间查询，只不过这里通过预处理出来的区间[L,R]中每个数到左边界L,即区间[L,i]中在左子树的个数toleft，来缩小区间[left,right];
坑点:我还是使用输出外挂out()来输出结果，可是里面有负数。。。2333
14796K 813ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
const int N = 1e5+;
int sorted[N];
int tree[][N],toleft[][N];
void build(int l,int r,int deep)
{
if(l == r) return ;
int mid = (l + r) >> ;
int same = mid - l + ;
for(int i = l;i <= r;i++)//左子树中有same个和[mid]相等
if(tree[deep][i] < sorted[mid])
same--;
int ls = l,rs = mid + ;
for(int i = l;i <= r;i++){//按顺序将每一个上一层每一个数插入到下一层的左右子树中
int flag = ;
if(tree[deep][i] < sorted[mid] || (tree[deep][i] == sorted[mid] && same > )){
tree[deep+][ls++] = tree[deep][i];//模拟快排，只是要保持原来的顺序,才设置了ls rs
if(tree[deep][i] == sorted[mid]) same--;
}else{
tree[deep+][rs++] = tree[deep][i];
flag = ;
}
toleft[deep][i] = toleft[deep][i-] + flag; // 递推出[l,i]在左子树中的个数;
}
build(l,mid,deep+);
build(mid+,r,deep+);
}
int query(int left,int right,int k,int L,int R,int deep)
{
if(left == right) return tree[deep][left];
int mid = (L + R) >> ;
int x = toleft[deep][left-] - toleft[deep][L-];//[L,left-1]在左子树中的个数;
int y = toleft[deep][right] - toleft[deep][L-];//[L,right];
int cnt = y - x;//[left,right]
if(cnt >= k){
return query(L+x,L+y-,k,L,mid,deep+);//[L,L+x) 正好x个;
}else{//右孩子起点从mid + 1开始,由于减掉了mid所以
int rx = left - L - x;// [L,left)在右子树中的个数;
int ry = right - L - y;//**里面mid减去了(+1-1)
return query(mid + + rx,mid + + ry,k - cnt,mid + ,R,deep+);
}
}
int main()
{
int n,q;
read2(n,q);
rep1(i,,n){
read1(sorted[i]);
tree[][i] = sorted[i];
}
sort(sorted+,sorted+n+);
build(,n,);
while(q--){
int a,b,k;
read3(a,b,k);
printf("%d\n",query(a,b,k,,n,));
}
return ;
}
主席树还是建立在线段树之上，对于1...i段的数据是建立在第id[i]颗树中；但是直接每个都建完全线段树，空间复杂度为O(n^2);且系数约等于4；那么既然是按照顺序来建树的，为什么不建立在前面的基础之上呢？好，这样就构造出了第0颗树(空树)，后面每个i都建立在id[i-1]之上。建立在前一颗线段树之上的具体含义又指的是什么呢(是什么数据要递推呢)？即只是建立一条从该点排序后应该在的叶子节点到根节点的路径，也就是条"树枝"。其余的分支还是用前一颗树的~~并且里面的递推关系很巧妙，即离散化之后，当当前插入的元素的最终位置是在当前节点的左子树时，生成一个左子树的节点(之后递归到左子树)，并且这个左子树的节点所代表的值num[]确实要在前一个树的基础上加上当前的这个元素，即num[rt] + 1;这里就是实现对区间的处理；
时间和空间复杂度均为O(n*log(n)) 25016K 1407MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define inf 0x3f3f3f3f
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
T x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
const int N = ;
const int M = N * ;
int val[N],sorted[N],m,tot;
int id[M],lson[M],rson[M],num[M];
int build(int l,int r)//第一颗空树根节点id[]标号为0
{
int newroot = tot++;
num[newroot] = ;//建立一颗空树
if(l == r) return newroot;
int mid = l + r >> ;
lson[newroot] = build(l,mid);
rson[newroot] = build(mid+,r);
return newroot;
}
int idx(int x)
{
return lower_bound(sorted+,sorted++m,x)-sorted;
}
int update(int pos,int add,int l,int r,int rt)
{
int newroot = tot++, t = newroot;
num[newroot] += num[rt] + add;//后一颗树是建立在前一颗树的基础之上
while(l < r){
int mid = l + r >> ;
if(pos <= mid){
lson[newroot] = tot++;
rson[newroot] = rson[rt];
newroot = lson[newroot];// 由于要更改左右子节点的num[]，不好利用递归，而写成了循环结构
rt = lson[rt];//***对区间的递推
r = mid;
}else{
rson[newroot] = tot++;
lson[newroot] = lson[rt];
newroot = rson[newroot];
rt = rson[rt];
l = mid + ;
}
num[newroot] += num[rt] + add;
}
return t;
}
int query(int ida,int idb,int k,int L,int R)
{
if(L == R) return L;
int mid = L + R >> ,
cnt = num[lson[idb]] - num[lson[ida]];
if(cnt >= k){
return query(lson[ida],lson[idb],k,L,mid);
}else{
return query(rson[ida],rson[idb],k - cnt,mid + ,R);
}
}
int main()
{
int n,Q;
read2(n,Q);
rep1(i,,n){
read1(val[i]);
sorted[i] = val[i];
}
sort(sorted+,sorted++n);
m = unique(sorted+,sorted++n) - sorted - ;
tot = ;
id[] = build(,m);
rep1(i,,n){
int pos = idx(val[i]);
id[i] = update(pos,,,m,id[i-]);//在前一颗树id[i-1]的基础上建树(枝);
}
while(Q--){
int a,b,k;
read3(a,b,k);
printf("%d\n",sorted[query(id[a-],id[b],k,,m)]);
}
return ;
}
划分树与主席树的总结:
划分树只需要排好序，在后面每层模拟快排中，递推出每一个小区间到左边界在左子树中元素的个数即可；在之后的查询中，直接使用toleft(左区间到该点所在的左子树的个数)递归缩小区间，找到第K小即可；
主席树是线段树的递推，对1..i都建立在前一棵线段树基础之上，查询的时候，只是缩小k值，到只剩一个数时，就是第k小的数了；