线段树灵活运用--2018 UESTC Training for Data Structures 一棵像样的线段树

92 阅读 0 评论 61 点赞

我是靠谱客的博主包容鞋垫，这篇文章主要介绍线段树灵活运用--2018 UESTC Training for Data Structures 一棵像样的线段树，现在分享给大家，希望可以做个参考。

设 xem 表示集合中最小的未出现的正整数，如 xem{}=1，xem{1,3,4}=2
定义
bi=xem{bi−ci,bi−ci+1,...,bi−1},i=1,2,...,n
特别的，b0=1
给定 n 和 c1,c2,...,cn，请你计算出 b1,b2,...,bn
Input
第一行一个整数 n (1≤n≤106)n (1≤n≤106).
第二行 n个用空格分隔的整数 c1,c2,...,cn，保证 1≤ci≤i
Output
输出一行 n 个用空格分隔的整数，依次为 b1,b2,...,bn

Sample Input
6
1 2 3 1 3 4
Sample Output

2 3 4 1 2 5

这道题想了好久一开始想着动态维护每个后缀的mex值不过发现好像很难做到无奈看了下别人的做法才知道原来可以这样做：先观察下样例根据题意发现其实b【i】求的实质就是从1数到n 第一个不位于（i-c【i】，i-1）的数就是答案了在转化一下就是在1到n中选一个尽可能小的数若他在【b【0】，b【i-1】】中最后一个出现的位置j假设比i-c【i】小的话那这个x就是答案了那么我们就可以用一棵线段树来维护1-n中每个数最后一次出现的位置的最小值每次查询的时候就那i-c【i】来比较左半区的最小值比i-c【i】小的话就继续查询左半区否则查询右半区（因为左半区是1到n>>1|1肯定比右半区小）然后更新的话就把对应的值改成他当前的位置就好了

这道题关键点是利用线段树的单点操作来实现动态查找功能他可以通过单点操作来动态的改变某个区间的和最大最小值这样如果你要查找某个点的话就和他与左右区间的最值比较就可以在log（n）内实现修改和查找了

AC代码：

复制代码

#include <set>
#include <map>
#include <list>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int maxn=1e6+5;
int mn[maxn<<2];
int c[maxn];
int b[maxn];
void pushup(int rt)
{
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
if(l==1) mn[rt]=0;
else mn[rt]=-1;
return;
}
int m=l+(r-l)/2;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int pos,int be,int l,int r,int rt)
{
if(l==r)
{
mn[rt]=be;
return;
}
int m=l+(r-l)/2;
if(pos<=m) update(pos,be,l,m,rt<<1);
else update(pos,be,m+1,r,rt<<1|1);
pushup(rt);
}
int query(int l,int r,int rt,int tr)
{
if(l==r)
{
return l;
}
int m=l+(r-l)/2;
if(mn[rt<<1]<tr) return query(l,m,rt<<1,tr);
else return query(m+1,r,rt<<1|1,tr);
}
int main()
{
int n;
scanf("%d",&n);
build(1,n,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
int ans=query(1,n,1,i-c[i]);
printf("%d",ans);
if(i!=n) printf(" ");
update(ans,i,1,n,1);
}
return 0;
}

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
#include <set>
#include <map>
#include <list>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int maxn=1e6+5;
int mn[maxn<<2];
int c[maxn];
int b[maxn];
void pushup(int rt)
{
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
if(l==1) mn[rt]=0;
else mn[rt]=-1;
return;
}
int m=l+(r-l)/2;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int pos,int be,int l,int r,int rt)
{
if(l==r)
{
mn[rt]=be;
return;
}
int m=l+(r-l)/2;
if(pos<=m) update(pos,be,l,m,rt<<1);
else update(pos,be,m+1,r,rt<<1|1);
pushup(rt);
}
int query(int l,int r,int rt,int tr)
{
if(l==r)
{
return l;
}
int m=l+(r-l)/2;
if(mn[rt<<1]<tr) return query(l,m,rt<<1,tr);
else return query(m+1,r,rt<<1|1,tr);
}
int main()
{
int n;
scanf("%d",&n);
build(1,n,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
int ans=query(1,n,1,i-c[i]);
printf("%d",ans);
if(i!=n) printf(" ");
update(ans,i,1,n,1);
}
return 0;
}