1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
/*
主席树 20191210
皮:震惊,cin和cout,竟然没有没有TLE???数据竟然没有爆int???!!!
*/
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
int ls[20000000]/*保存节点左儿子*/, rs[20000000]/*保存节点右儿子*/,
root[200010]/*保存第一个元素到第n个数对应权值线段树的根节点*/,
value[20000000]/*保存权值线段树节点的值*/,
ln[20000000]/*保存节点区间左端点*/, rn[20000000]/*保存节点区间右端点*/;
int cnt/*累计节点编号*/, n/*数的个数*/;
int n2/*排序去重后数的个数(离散化巨坑)*/;
int num[200010]/*保存序列*/, tmp[200010]/*便于离散化*/;
void bud(int l, int r, int p)//建立空树(便于线段树相减),同普通线段树,只是没有保存节点权值而已
{
ln[p] = l; rn[p] = r;//显然
if (l != r)//巨坑,否则死循环!!!
{
ls[p] = ++cnt;//累计子节点
bud(l, (l + r >> 1), cnt);//递归建立左子树
rs[p] = ++cnt;//累计子节点
bud((l + r >> 1) + 1, r, cnt);//递归建立右子树
}
}
void updata(int last/*上一棵线段树等位结点编号*/, int p, int v)//建立下一棵线段树,相当于线段树的单点更新,只需保存一条链而已
{
ln[p] = ln[last]; rn[p] = rn[last];//这棵线段树和上一棵一样,直接赋值
value[p] = value[last] + 1;//明显v包含在区间里,直接加一即可
if (ln[p] == rn[p]) return;//叶节点,不用继续更新,直接返回即可
if (v <= (ln[p] + rn[p] >> 1))//包含在左儿子的区间中
{
rs[p] = rs[last];//右子树(即右儿子)和上一棵线段树的一样
ls[p] = ++cnt;//累计节点编号
//本来更新节点的值是写在这里的,但这样根节点就更新不了了,于是写到了前面
updata(ls[last], ls[p], v);//建立左子树
}
else//反之亦然同理
{
ls[p] = ls[last];
rs[p] = ++cnt;
updata(rs[last], rs[p], v);
}
}
void build()//建立主席树
{
root[0] = cnt;//0号根节点为空树,便于相减
bud(0, n2 - 1, cnt);//先建一发空树
for (int i = 0; i < n; i++)//[0,n)和(0,n]皆可,只不过是root[i-1]和root[i+1]的区别
{
root[i + 1] = ++cnt;//累计根节点
updata(root[i], root[i + 1], num[i]);//更新这棵线段树
}
}
//这类宏定义一定要加括号，否则死的很惨！！！！！！
//我才不会告诉你我就是因为这个第一次交爆零了...
//还有,宏定义这种东西作用范围是当前文件...写在哪里都一样...
#define lv (value[ls[r]]-value[ls[l]])//相减后得到的线段树左儿子的值
#define rv (value[rs[r]]-value[rs[l]])//相减后得到的线段树右儿子的值
int ans;//落谷猥琐巨坑,直接返回会MLE!!!被迫改void并使用全局变量保存答案
void query(int k, int l, int r)//这里的l和r指的不是数列的区间,而是l棵线段树和第r棵线段树的根节点
{
//直接写成(其实就是)权值的查询就好
if (ln[l] == rn[l])//叶节点,直接记录答案
{
ans = ln[l];
return;
}
if (k <= lv)//左儿子包含的数的个数大于等于待查询的k
query(k, ls[l], ls[r]);//向左儿子查询第k小即可
else//左儿子包含的数的个数小于待查询的k
query(k - lv, rs[l], rs[r]);//整段区间的第k小即为右区间的第(k-左区间包含数的个数)小
}
map <int, int> po/*由原值映射到离散化后的值*/, re/*由离散化后的值映射到原值*/;
int main()
{
cin >> n;//输入,显然
int m;
cin >> m;
for (int i = 0; i < n; i++)//输入并保存副本用于离散化
{
cin >> num[i];
tmp[i] = num[i];
}
//---------------------------------------离散化--------------------------------------------
sort(tmp, tmp + n);//先来一发排序
//巨坑!!tmp+n是排序区间末区间端点的下一个值的地址!!!
//我也不知道STL为什么要这样反正我就这样爆了两个点
n2 = unique(tmp, tmp + n) - tmp;//去重也一样!!!(STL的东西都是这个尿性)
for (int i = 0; i < n2; i++)//记录离散化后的数值
{
po[tmp[i]] = i;
re[i] = tmp[i];
}
for (int i = 0; i < n; i++)//将原值变为离散化后的值
{
num[i] = po[num[i]];
}
//-----------------------------------------------------------------------------------------
build();//建立主席树
int l, r, k;
while (m--)
{
cin >> l >> r >> k;
l--;
query(k, root[l], root[r]);//一定要传递根节点的编号!!!!!!
cout << re[ans] << '\n';//输出答案,一定要离散化的数值搞回来!!!小心爆零!!!
}
return 0;
}
|
