题目链接
题意：给出一排人，以1~n的一个排列作为他们的权值，2教练和1教练每次从中选择权值最大的一个人和他左边k个人和右边k个人，求最后每个人是被1选还是被2选。每个人的权值是唯一的，且均在1到n之内
思路：用线段树维护树上节点代表的区间中没被选择的总人数，每次选择人时，找到要要选择的人在线段树上的位置，然后向左右分别取k人。
取人过程：
如数据
6 1
2 4 6 5 3 1
对于第一次选人，找到的节点是区间3-3的点，在树上的位置编号为5.
向右取：5号节点没有相邻的右边节点，所以往上走，到2号节点，2节点有相邻的右边节点3号，所以进入3号去取人，一个中序遍历（左中右的顺序）去取人。取走10号。
向左取：5号节点有相邻的左边节点，所以进入4号节点去取人，同样是中序遍历（右中左）去取人，取走9号。
因为线段树储存的是区间内没被取的人的个数，这是用来判断是否要进入相邻节点，也用来判断遍历是是否要遍历下去。
取做人时要维护线段树。
还有几个辅助数组，在代码中会有注释。
#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 200050;
using namespace std;
int sum[maxn<<2];//线段树主体
int mark[maxn<<2];//标记线段树的叶子节点，记录叶子节点在初始数组的位置
int ans[maxn];//答案数组
int a[maxn];//初始数组
int vis[maxn];//因为每次选人，是在剩下的序列里先找到最大的，以最大的点向左右取人
int index[maxn];//每个人的权值的位置
int n, k;
int jiao;
void shang(int rt){
if(rt<<1 < maxn<<2)
sum[rt] = sum[rt<<1];
if(rt<<1 < maxn<<2)
sum[rt] += sum[rt<<1|1];
}
void chuang(int l, int r, int rt){//创建线段树
if(l == r){
scanf("%d", &a[l]);
index[ a[l] ] = l;//
sum[rt] = 1;
mark[rt] = l;//标记这个叶子节点代表的位置
return ;
}
int m = (l+r)>>1;
chuang(l, m, rt<<1);
chuang(m+1, r, rt<<1|1);
shang(rt);//更新
}
int ge;//要取的人数
void rightxia(int rt){
if(mark[rt]){//叶子节点
if(sum[rt]){//叶子节点有人
ge--;
sum[rt] = 0;//取走
vis[ a[ mark[rt] ] ] = 1;//标记这个权值的人已被取走
//mark数组的另一个作用：记录这个叶子节点在初始序列中的值
ans[ mark[rt] ] = jiao;
}
return;//停止往下，mark数组的一个作用
}
else{
if(sum[rt<<1] && ge)//左子节点有人且还需要取人
rightxia(rt<<1);
if(sum[rt<<1|1] && ge)//右子节点有人且还需要取人
rightxia(rt<<1|1);
shang(rt);
}
}
void xright(int rt){//向右边找k人
if(rt == 1)
return ;
if(ge){//还去需要取人
if(rt%2 == 0 && sum[rt+1]){//有相邻节点，并且相邻节点代表的区间还有人
rightxia(rt+1);
shang(rt+1);
}
else
shang(rt);
xright(rt>>1);
}
}
void leftxia(int rt){
if(mark[rt]){
if(sum[rt]){
ge--;
sum[rt] = 0;
vis[ a[mark[rt]] ] = 1;
ans[ mark[rt] ] = jiao;
}
return;
}
else{
if(sum[rt<<1|1] && ge)
leftxia(rt<<1|1);
if(sum[rt<<1] && ge)
leftxia(rt<<1);
shang(rt);
}
}
void xleft(int rt){//左边找k人
if(rt == 1)
return ;
if(ge){
if(rt%2 && sum[rt-1]){
leftxia(rt-1);
shang(rt-1);
}
else
shang(rt);
xleft(rt>>1);
}
}
void cha(int l, int r, int rt, int pos){
if(l==pos && r==pos){
ans[l] = jiao;//选择教练
vis[ a[pos] ] = 1;//标记
sum[rt] = 0;//标记为已被取
ge = k;
xright(rt);//向右取
shang(rt);
ge = k;
xleft(rt);
shang(rt);
return ;
}
int m = (l+r)>>1;
if(m >= pos)
cha(l, m, rt<<1, pos);
else
cha(m+1, r, rt<<1|1, pos);
shang(rt);
}
int main()
{
scanf("%d%d", &n, &k);
chuang(1, n, 1);
int maxnn = n;
while(maxnn){
cha(1, n, 1, index[maxnn]);
jiao = !jiao;
while(vis[maxnn])//找到剩下的人里的最大权值
maxnn--;
}
for(int i=1; i<=n; i++)
printf("%d", ans[i]+1);
return 0;
}
/*
6 1
2 4 6 5 3 1
6 1
2 3 4 6 5 1
100 2
62 70 29 14 12 87 94 78 39 92 84 91 61 49 60 33 69 37 19 82 42 8 45 97 81 43 54 67 1 22 77 58 65 17 18 28
25 57 16 90 40 13 4 21 68 35 15 76 73 93 56 95 79 47 74 75 30 71 66 99 41 24 88 83 5 6 31 96 38 80 27 46
51 53 2 86 32 9 20 100 26 36 63 7 52 55 23 3 50 59 48 89 85 44 34 64 10 72 11 98
2222111112222211111112222211222221211111112221111222221112222211111111221222211111222222122222111111
10 2
1 2 3 4 5 6 7 8 9 10
*/
不用线段树也可以过这个题，但是线段树高大上啊,好吧，就是我不会