基础数据结构学习笔记
树状数组
最近突然发现树状数组不会打了。
作为立志成为小常数选手的我，怎么能忘记这个数据结构呢？
复习一下：
【模板】树状数组 1
纯手打(一边写博客，一边打的)：
#include
using namespace std;
int n , m , t[500010];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x , int y)
{
while(x <= n)
{
t[x] += y;
x += lowbit(x);
}
}
int ask(int x)
{
int ans = 0;
while(x)
{
ans += t[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
n = read() , m = read();
for(int i = 1;i <= n;i++) update(i , read());
for(int i = 1;i <= m;i++)
{
int opt = read() , x = read() , k = read();
if(opt == 1) update(x , k);
else cout << ask(k) - ask(x - 1) << endl;
}
return 0;
}
打了七八分钟，速度好像慢了。
下一个：
【模板】树状数组 2
#include
using namespace std;
int n , m , a[500010] , t[500010];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x , int y)
{
while(x <= n)
{
t[x] += y;
x += lowbit(x);
}
}
int ask(int x)
{
int ans = 0;
while(x)
{
ans += t[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
n = read() , m = read();
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= n;i++) update(i , a[i] - a[i - 1]);
for(int i = 1;i <= m;i++)
{
int opt = read() , x = read();
if(opt == 1)
{
int y = read() , k = read();
update(x , k) , update(y + 1 , -k);
}
else cout << ask(x) << endl;
}
return 0;
}
在上一个的基础上改的，花了四分零四秒。
有图为证：
一些拓展的小知识
树状数组套主席树
如果不知道主席树可以移步。
例题。
这道题花了我一个上午两个半小时，十二遍评测，才卡过去了。
实测我的常数还是比较大(跑了将近两秒)。
我们考虑用经典的树状数组套主席树。
0. 一些基础的概念
- 为什么树状数组能套主席树。
每一颗主席树的结构相同，可以用树状数组来统计前缀和。
- 为什么要用树状数组套主席树。
树状数组常数小！！！
1. 初始化
要注意，树状数组套主席树的方式非常炸空间，所以数组一定要开准一点(随随便便就会\(MLE\)和\(RE\))。
const int maxn = 5e4 + 5;
//注意+10有可能会MLE
int n, m, a[maxn], b[maxn << 1], id[maxn];
int q, cnt, tot1, tot2, tmp1[maxn], tmp2[maxn];
struct edge
{
int l, r, sum;
} t[maxn * 101];
//我也不知道为什么开100倍会RE最后一个点
struct question
{
int opt, l, r, k;
} ql[maxn];
//离线存问题
2. 读入
我们需要进行离线，在线应该不行(也可能是我太菜了)。
n = read(), m = read(), q = n;
for (int i = 1; i <= n; i++)
a[i] = b[i] = read();
for (int i = 1; i <= m; i++)
{
ql[i].opt = read(), ql[i].l = read(), ql[i].r = read();
if (ql[i].opt != 3)
ql[i].k = read();
else
b[++q] = ql[i].r;
if (ql[i].opt == 4 || ql[i].opt == 5)
b[++q] = ql[i].k;
}
其中\(~b~\)数组就和主席树中的一样，统计权值，进行离散化。
3. 离散化
sort(b + 1, b + q + 1);
q = unique(b + 1, b + q + 1) - b - 1;
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
change(i, 1);
}
标准的离散化。
4. 修改
由于我们运用的是树状数组来统计主席树的前缀和，所以就有必不可少的 \(lowbit\) 操作。
int lowbit(int x)
{
return x & (-x);
}
第一个修改当然是用树状数组求出需要修改的主席树啦。
void change(int p, int k)
{
for (int i = p; i <= n; i += lowbit(i))
{
update(id[i], a[p], k, 1, q);
}
}
至于主席树内部的修改就比较无脑直接暴力用板子修就可以了。
void update(int &p, int x, int k, int l, int r)
{
if (!p)
p = ++cnt;
if (l == r)
{
t[p].sum += k;
return;
}
int mid = (l + r) / 2;
if (x <= mid)
update(t[p].l, x, k, l, mid);
else
update(t[p].r, x, k, mid + 1, r);
t[p].sum = t[t[p].l].sum + t[t[p].r].sum;
}
5. 五个操作前的二分
我们发现，现在的\(~b~\)数组还存了修改后的值，所以为了保证离散化，在每一个询问的值，都要进行二分离散化。
6. 求区间第K大
这里和主席树板子差不多，只是变成了树状数组来统计前缀和。
int ask(int l, int r, int k)
{
tot1 = 0, tot2 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++tot1] = id[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++tot2] = id[i];
return query(1, q, k);
}
两个\(~tmp~\)数组存的是需要统计的主席树编号，和树状数组求和操作相同。
int query(int l, int r, int k)
{
if (l == r)
return l;
int mid = (l + r) >> 1, ans = 0;
for (int i = 1; i <= tot1; i++)
ans += t[t[tmp1[i]].l].sum;
for (int i = 1; i <= tot2; i++)
ans -= t[t[tmp2[i]].l].sum;
if (k <= ans)
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].l;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].l;
return query(l, mid, k);
}
else
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].r;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].r;
return query(mid + 1, r, k - ans);
//注意减ans
}
}
主席树内部操作和板子也差不多。
一边求出左子树有多少个数，在不断转移需要求的主席树编号。
应该还算好理解。
7. 求区间K的排名
这个和上一个操作相差无几，只需要改几个地方就可以了。
int query_rank(int l, int r, int k)
{
if (l == r)
return 0;
//这里返回的是0；
//因为不需要将自己统计进去
int mid = (l + r) >> 1, ans = 0;
if (k <= mid)
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].l;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].l;
return query_rank(l, mid, k);
}
else
{
for (int i = 1; i <= tot1; i++)
ans += t[t[tmp1[i]].l].sum;
for (int i = 1; i <= tot2; i++)
ans -= t[t[tmp2[i]].l].sum;
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].r;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].r;
return ans + query_rank(mid + 1, r, k);
//这里不用减ans;
}
}
int ask_rank(int l, int r, int k)
{
tot1 = 0, tot2 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++tot1] = id[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++tot2] = id[i];
return query_rank(1, q, k) + 1;
//注意排名要加一
}
8. 求区间前驱后继
既然已经有了上面两个操作。
那么这个操作只需要上面两个操作和一些特判就可以了。
读者不妨自己思考一下。
int ask_qian(int l, int r, int k)
{
int x = ask_rank(l, r, k) - 1;
if (x == 0)
return 0;
return ask(l, r, x);
}
int ask_hou(int l, int r, int k)
{
if (k == q)
return q + 1;
int x = ask_rank(l, r, k + 1);
if (x == r - l + 2)
return q + 1;
return ask(l, r, x);
}
这样，这个题你就切掉了。
Code
\(~vscode~\)格式化后\(~4.56KB~\)
格式化前\(~3.6KB~\)
不算特别长。
#include
#define int long long
using namespace std;
const int maxn = 5e4 + 5;
int n, m, a[maxn], b[maxn << 1], id[maxn];
int q, cnt, tot1, tot2, tmp1[maxn], tmp2[maxn];
struct edge
{
int l, r, sum;
} t[maxn * 101];
struct question
{
int opt, l, r, k;
} ql[maxn];
int read()
{
int asd = 0, qwe = 1;
char zxc;
while (!isdigit(zxc = getchar()))
if (zxc == '-')
qwe = -1;
while (isdigit(zxc))
asd = asd * 10 + zxc - '0', zxc = getchar();
return asd * qwe;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int &p, int x, int k, int l, int r)
{
if (!p)
p = ++cnt;
if (l == r)
{
t[p].sum += k;
return;
}
int mid = (l + r) / 2;
if (x <= mid)
update(t[p].l, x, k, l, mid);
else
update(t[p].r, x, k, mid + 1, r);
t[p].sum = t[t[p].l].sum + t[t[p].r].sum;
}
void change(int p, int k)
{
for (int i = p; i <= n; i += lowbit(i))
{
update(id[i], a[p], k, 1, q);
}
}
int query(int l, int r, int k)
{
if (l == r)
return l;
int mid = (l + r) >> 1, ans = 0;
for (int i = 1; i <= tot1; i++)
ans += t[t[tmp1[i]].l].sum;
for (int i = 1; i <= tot2; i++)
ans -= t[t[tmp2[i]].l].sum;
if (k <= ans)
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].l;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].l;
return query(l, mid, k);
}
else
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].r;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].r;
return query(mid + 1, r, k - ans);
}
}
int ask(int l, int r, int k)
{
tot1 = 0, tot2 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++tot1] = id[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++tot2] = id[i];
return query(1, q, k);
}
int query_rank(int l, int r, int k)
{
if (l == r)
return 0;
int mid = (l + r) >> 1, ans = 0;
if (k <= mid)
{
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].l;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].l;
return query_rank(l, mid, k);
}
else
{
for (int i = 1; i <= tot1; i++)
ans += t[t[tmp1[i]].l].sum;
for (int i = 1; i <= tot2; i++)
ans -= t[t[tmp2[i]].l].sum;
for (int i = 1; i <= tot1; i++)
tmp1[i] = t[tmp1[i]].r;
for (int i = 1; i <= tot2; i++)
tmp2[i] = t[tmp2[i]].r;
return ans + query_rank(mid + 1, r, k);
}
}
int ask_rank(int l, int r, int k)
{
tot1 = 0, tot2 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++tot1] = id[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++tot2] = id[i];
return query_rank(1, q, k) + 1;
}
int ask_qian(int l, int r, int k)
{
int x = ask_rank(l, r, k) - 1;
if (x == 0)
return 0;
return ask(l, r, x);
}
int ask_hou(int l, int r, int k)
{
if (k == q)
return q + 1;
int x = ask_rank(l, r, k + 1);
if (x == r - l + 2)
return q + 1;
return ask(l, r, x);
}
signed main()
{
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
n = read(), m = read(), q = n;
for (int i = 1; i <= n; i++)
a[i] = b[i] = read();
for (int i = 1; i <= m; i++)
{
ql[i].opt = read(), ql[i].l = read(), ql[i].r = read();
if (ql[i].opt != 3)
ql[i].k = read();
else
b[++q] = ql[i].r;
if (ql[i].opt == 4 || ql[i].opt == 5)
b[++q] = ql[i].k;
}
sort(b + 1, b + q + 1);
q = unique(b + 1, b + q + 1) - b - 1;
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
change(i, 1);
}
b[0] = -2147483647, b[q + 1] = 2147483647;
for (int i = 1; i <= m; i++)
{
if (ql[i].opt == 1)
ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", ask_rank(ql[i].l, ql[i].r, ql[i].k));
if (ql[i].opt == 2)
printf("%lld\n", b[ask(ql[i].l, ql[i].r, ql[i].k)]);
if (ql[i].opt == 3)
change(ql[i].l, -1), a[ql[i].l] = lower_bound(b + 1, b + q + 1, ql[i].r) - b, change(ql[i].l, 1);
if (ql[i].opt == 4)
ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", b[ask_qian(ql[i].l, ql[i].r, ql[i].k)]);
if (ql[i].opt == 5)
ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", b[ask_hou(ql[i].l, ql[i].r, ql[i].k)]);
}
return 0;
}
权值线段树
权值线段树，一个可以动态维护区间的第\(~k~\)小（反之同理）的数据结构。
在线段树的基础上优化而来，代码实现比较简单。
支持单点修改。
时间复杂度:修改和查询均为\(O(\log_{n})\)
大致思路
将每一个节点维护原序列的权值。
记录每个区间每个数的出现次数。
因此建树是可以只需要维护左右区间。
void build(int p , int l , int r)
{
t[p].l = l , t[p].r = r;
if(l == r) return;
build(p * 2 , l , (l + r) / 2);
build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}
注意调用入口的范围是你题目序列里的最大值和最小值。
例如题目规定：
\(a_{i} \leqslant 1e5\)
那么调用入口为：
build(1 , 1 , 100000);
将序列放入线段树内需要修改操作。
这里呈现的代码是要维护区间的第\(~k~\)小和区间的前\(~k~\)小之和。
void update(int p , int k)
{
t[p].sum += k , t[p].num++;
if(t[p].l == t[p].r) return;
if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k);
else update(p * 2 , k);
}
那么，区间求值也很好写。
求区间的前\(~k~\)小之和：
int ask(int p , int k)
{
if(t[p].l == t[p].r) return t[p].sum / t[p].num * k;
if(k > t[p * 2].num) return t[p * 2].sum + ask(p * 2 + 1 , k - t[p * 2].num);
else return ask(p * 2 , k);
}
求区间的第\(~k~\)小：
int ask(int p , int k)
{
if(t[p].l == t[p].r) return t[p].sum / t[p].num;
if(k > t[p * 2].num) return ask(p * 2 + 1 , k - t[p * 2].num);
else return ask(p * 2 , k);
}
例题：稳定桌（区间的前\(~k~\)小之和的运用）。
code
#include
#define int long long
using namespace std;
int n , top , ans , l[100110] , d[100110] , sum[100110] , num[100110];
vector ton[100110];
struct edge
{
int l , r , sum , num;
}t[800080];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
void update(int p , int k)
{
t[p].sum += k , t[p].num++;
if(t[p].l == t[p].r) return;
if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k);
else update(p * 2 , k);
}
void build(int p , int l , int r)
{
t[p].l = l , t[p].r = r;
if(l == r) return;
build(p * 2 , l , (l + r) / 2);
build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}
int ask(int p , int k)
{
if(t[p].l == t[p].r) return t[p].sum / t[p].num * k;
if(k > t[p * 2].num) return t[p * 2].sum + ask(p * 2 + 1 , k - t[p * 2].num);
else return ask(p * 2 , k);
}
signed main()
{
n = read() , ans = 1e11;
for(int i = 1;i <= n;i++) l[i] = read();
for(int i = 1;i <= n;i++) d[i] = read() , ton[l[i]].push_back(d[i]);
build(1 , 1 , 100000);
for(int i = 100000;i >= 1;i--)
{
sum[i] = sum[i + 1] , num[i] = num[i + 1];
int len = ton[i].size();
if(len == 0) continue;
for(int j = 0;j < len;j++) sum[i] += ton[i][j] , num[i]++;
}
for(int i = 1;i <= 100000;i++)
{
int len = ton[i].size() , l = 0;
if(len == 0) continue;
int x = n - num[i] , y = x - len + 1;
if(y <= 0) ans = min(ans , sum[i + 1]);
else
{
l = ask(1 , y) + sum[i + 1];
ans = min(l , ans);
}
for(int j = 0;j < len;j++) update(1 , ton[i][j]);
}
cout << ans;
return 0;
}
\(10.30\) 新增：
发现一道模板题：
P3369 【模板】普通平衡树
是的，这道题我们也可以用权值线段树跑过去。
实测:
权值线段树 298ms。
无旋treap 407ms。
常数的优势瞬间体现出来了。
虽然没有红黑树和平板电视跑得快。
但谁会拒绝好写好调代码又短的权值线段树呢。
代码实现比较简单，还不到一百行。
Code
#include
#define int long long
using namespace std;
int n , q , b[100010];
pair a[100010];
struct edge
{
int l , r , num;
}t[800080];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
void update(int p , int k , int x)
{
t[p].num += x;
if(t[p].l == t[p].r) return;
if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k , x);
else update(p * 2 , k , x);
}
void build(int p , int l , int r)
{
t[p].l = l , t[p].r = r;
if(l == r) return;
build(p * 2 , l , (l + r) / 2);
build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}
int ask(int p , int k)
{
if(t[p].l == t[p].r) return t[p].l;
if(k > t[p * 2].num) return ask(p * 2 + 1 , k - t[p * 2].num);
else return ask(p * 2 , k);
}
int ask_rank(int p , int l , int r)
{
if(l <= t[p].l && t[p].r <=r) return t[p].num;
int mid = (t[p].l + t[p].r) >> 1 , ans = 0;
if(l <= mid) ans += ask_rank(p << 1 , l , r);
if(r > mid) ans += ask_rank(p << 1 | 1 , l , r);
return ans;
}
int ask_qian(int x)
{
int a = ask_rank(1 , 1 , x - 1);
return ask(1 , a);
}
int ask_hou(int x)
{
int a = ask_rank(1 , 1 , x) + 1;
return ask(1 , a);
}
signed main()
{
n = read();
for(int i = 1;i <= n;i++)
{
a[i].first = read() , a[i].second = read();
if(a[i].first != 4) b[++q] = a[i].second;
}
sort(b + 1 , b + q + 1);
q = unique(b + 1 , b + q + 1) - b - 1;
build(1 , 1 , q);
for(int i = 1;i <= n;i++)
{
int x = a[i].first , y = a[i].second;
if(x != 4) y = lower_bound(b + 1 , b + q + 1 , y) - b;
if(x == 1) update(1 , y , 1);
if(x == 2) update(1 , y , -1);
if(x == 3)
{
if(y == 1) cout << 1 << endl;
else cout << ask_rank(1 , 1 , y - 1) + 1 << endl;
}
if(x == 4) cout << b[ask(1 , y)] << endl;
if(x == 5) cout << b[ask_qian(y)] << endl;
if(x == 6) cout << b[ask_hou(y)] << endl;
}
return 0;
}
主席树
主席树，即维护任意区间第\(~k~\)大的数据结构。
支持单点修改和区间查询。
大致思路
主席树的思想为对序列的每一个前缀进行构造权值线段树维护。
即可持久化线段树。
0. 初始化
可以发现，由于空间复杂度问题，我们无法直接算出一个节点的左右儿子，所以均须记录。
int id[maxn];
//id为每一个前缀的线段树标号。
struct ST
{
int l , r , sum;
//l为左儿子标号，r为右儿子标号。
//sum即权值线段树的num。
}t[maxn << 5];
//注意三十二倍空间
考虑到空间复杂度，以及每一道主席树题目的毒瘤程度。
我们需要离散化。
//基本的离散化。
sort(b + 1 , b + n + 1);
q = unique(b + 1 , b + n + 1) - b - 1;
build(id[0] , 1 , q);
for(int i = 1;i <= n;i++)
{
int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
id[i] = update(id[i - 1] , 1 , q , x);
}
1. 建树
由于我们无法直接得出左右儿子的标号，所以建树可以只统计\(~id~\)数组。
void build(int &p , int l , int r)
{
p = ++cnt;
if(l == r) return;
build(t[p].l , l , (l + r) / 2);
build(t[p].r , (l + r) / 2 + 1 , r);
}
其中，\(~cnt~\)为线段树标号记录。
调用入口：
build(id[0] , 1 , q);
\(~q~\)为离散化后的总数。
2. 单点修改
与权值线段树相差无几，唯一区别是要在开一颗线段树。
int update(int p , int l ,int r , int k)
{
int o = ++cnt; t[o] = t[p] , t[o].sum++;
//开了一颗新的线段树。
if(l == r) return o; int mid = (l + r) / 2;
if(k <= mid) t[o].l = update(t[p].l , l , mid , k);
else t[o].r = update(t[p].r , mid + 1 , r , k);
return o;
}
3. 区间查询
思考一下，我们为什么维护的是前缀的线段树。
是不是跟前缀和有一点像。
它就是一个前缀和的作用。
因为每一个线段树的结构相同，所以具有可加可减性。
那么区间查询也和权值线段树很像了。
int ask(int u , int v , int l , int r , int k)
{
int ans = 0 , mid = (l + r) / 2;
int x = s[s[v].l].sum - s[s[u].l].sum;
//和前缀和一样的操作。
if(l == r) return l;
if(x >= k) ans = ask(s[u].l , s[v].l , l , mid , k);
else ans = ask(s[u].r , s[v].r , mid + 1 , r , k - x);
return ans;
}
讲到现在，板子题就已经可以过了。
题目传送门
Code
#include
using namespace std;
const int maxn = 200010;
int n , m , q , cnt;
int a[maxn] , t[maxn] , b[maxn];
struct ST
{
int l , r , sum;
}s[maxn << 5];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
void build(int &p , int l , int r)
{
p = ++cnt;
if(l == r) return;
build(s[p].l , l , (l + r) / 2);
build(s[p].r , (l + r) / 2 + 1 , r);
}
int update(int p , int l , int r , int x)
{
int o = ++cnt; s[o] = s[p] , s[o].sum++;
if(l == r) return o; int mid = (l + r) / 2;
if(x <= mid) s[o].l = update(s[o].l , l , mid , x);
else s[o].r = update(s[o].r , mid + 1 , r , x);
return o;
}
int ask(int u , int v , int l , int r , int k)
{
int ans = 0 , mid = (l + r) / 2 , x = s[s[v].l].sum - s[s[u].l].sum;
if(l == r) return l;
if(x >= k) ans = ask(s[u].l , s[v].l , l , mid , k);
else ans = ask(s[u].r , s[v].r , mid + 1 , r , k - x);
return ans;
}
int main()
{
n = read() , m = read();
for(int i = 1;i <= n;i++) a[i] = b[i] = read();
sort(b + 1 , b + n + 1);
q = unique(b + 1, b + n + 1) - b - 1;
build(t[0] , 1 , q);
for(int i = 1;i<= n;i++)
{
int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
t[i] = update(t[i - 1] , 1 , q , x);
}
for(int i = 1;i <= m;i++)
{
int l = read() , r = read() , k = read();
cout << b[ask(t[l - 1] , t[r] , 1 , q , k)] << endl;
}
return 0;
}
同样的还有一道板子题。
题目传送门
这一道题是不是很好想。
只要该一下区间查询就可以了。
Code
#include
using namespace std;
const int maxn = 500010;
int n , m , q , cnt;
int a[maxn] , id[maxn] , b[maxn];
struct ST
{
int l , r , sum;
}t[maxn << 5];
int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
void build(int &p , int l , int r)
{
p = ++cnt;
if(l == r) return;
build(t[p].l , l , (l + r) / 2);
build(t[p].r , (l + r) / 2 + 1 , r);
}
int update(int p , int l ,int r , int k)
{
int o = ++cnt; t[o] = t[p] , t[o].sum++;
if(l == r) return o; int mid = (l + r) / 2;
if(k <= mid) t[o].l = update(t[p].l , l , mid , k);
else t[o].r = update(t[p].r , mid + 1 , r , k);
return o;
}
int ask(int u , int v , int l , int r , int k)
{
int mid = (l + r) / 2;
if(l == r) return l;
int x = t[t[v].l].sum - t[t[u].l].sum , y = t[t[v].r].sum - t[t[u].r].sum;
if(x > k) return ask(t[u].l , t[v].l , l , mid , k);
if(y > k) return ask(t[u].r , t[v].r , mid + 1 , r , k);
return 0;
}
int main()
{
n = read() , m = read();
for(int i = 1;i <= n;i++) a[i] = b[i] = read();
sort(b + 1 , b + n + 1);
q = unique(b + 1 , b + n + 1) - b - 1;
build(id[0] , 1 , q);
for(int i = 1;i <= n;i++)
{
int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
id[i] = update(id[i - 1] , 1 , q , x);
}
for(int i = 1;i <= m;i++)
{
int l = read() , r = read();
cout << b[ask(id[l - 1] , id[r] , 1 , q , (r - l + 1) / 2)] << endl;
}
return 0;
}