Two Teams

标签：思维 线段树

---

题目描述

There are nstudents standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.

The i-th student has integer programming skill ai. All programming skills are distinct and between 1 and n, inclusive.

Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and kclosest students to the left of him and k closest students to the right of him (if there are less than k students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).

Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.

Input

The first line of the input contains two integers n
and k (1≤k≤n≤2⋅10^5) — the number of students and the value determining the range of chosen students during each move, respectively.

The second line of the input contains n
integers a1,a2,…,an (1≤ai≤n), where ai is the programming skill of the i-th student. It is guaranteed that all programming skills are distinct.

Output

Print a string of n characters; i-th character should be 1 if i-th student joins the first team, or 2 otherwise.

Examples

Input
5 2
2 4 5 3 1
Output
11111

Input
5 1
2 1 3 5 4
Output
22111

Input
7 1
7 2 1 3 5 4 6
Output
1121122

Input
5 1
2 4 5 3 1
Output
21112

题解

题目大意:每次从全部人中选一个最大的人，并向左向右扩展至k位（若遇到边界则停下），然后标号并删去这些人，重复操作直至所有人都被标号。
一个简单的想法，每次线段树查到1-n里最大的值的地址pos，然后区间修改[pos - k, pos + k]为0，顺便标号。但是会发现一个问题，就是我们每次向左向右扩展的时候可能是O（n）的（这里扩展k为是指的有效人数，那些已经被标记过的人就不会算进去了）,因此我们要处理出一个Left[N]和Right[N]，Left[i]i表示从i开始向左到Left[i]这之间所有人都被标记过，Right[i]同理。所以到时候遍历时每次跳Left[i]和Right[i]就可以了
说道这里，这道题也就被解决了。不过题目中还有一个性质我们没用：所有人的值是一个n的全排列的一种。所以考虑这个性质我们完全不用线段树。
第一次最大值肯定为n，进行标号操作时我们可以把每个人的所对应权值全部标记为false，然后从n-1到1找到第一个值为true的人，这个人的权值肯定为当前区间最大的，重复上述操作即可。不用线段树可以大大降低代码量

代码

//线段树版
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define N 200010
using namespace std;

int n,m,p,x,y,k,tl[N], tr[N], a[N],b[N];
struct node{int sum,l,r,p,res;} t[N*4];

void rd(int &ans)
{
    int f=1;ans=0;char x=getchar();
    while(x>'9' || x<'0') {if(x=='-') f=-1;x=getchar();}
    while(x>='0' && x<='9') ans=ans*10+x-'0',x=getchar();
    ans*=f;
}

void built(int l,int r,int x)
{
    t[x].l=l,t[x].r=r,t[x].p=0;
    if(l==r){t[x].sum=a[l];t[x].res=l;return;}
    int mid=(l+r)>>1;
    built(l,mid,2*x);built(mid+1,r,2*x+1);
    if(t[2*x].sum>t[2*x+1].sum) t[x].sum = t[2 * x].sum, t[x].res = t[2 * x].res;
    else t[x].sum = t[2 * x + 1].sum, t[x].res = t[2 * x + 1].res;
}

void put(int x,int num)
{
    t[2*x].sum=0;
    t[2*x+1].sum=0;
    t[2*x].p=1;t[2*x+1].p=1;t[x].p=0; 
}

void change(int x,int l,int r)
{
    if(t[x].l>r || t[x].r<l) return;
    if(t[x].l>=l && t[x].r<=r){
        t[x].sum=0;
        t[x].p=1;return;
    }
    if(t[x].l!=t[x].r && t[x].p) put(x,t[x].p);
    change(2*x,l,r);change(2*x+1,l,r);
    if(t[2*x].sum>t[2*x+1].sum) t[x].sum = t[2 * x].sum, t[x].res = t[2 * x].res;
    else t[x].sum = t[2 * x + 1].sum, t[x].res = t[2 * x + 1].res;
}
node query(int x,int l,int r)
{
    node mm; mm.sum = -1;
    if(t[x].l>r || t[x].r<l) return mm;
    if(t[x].l>=l && t[x].r<=r) return t[x];
    if(t[x].l!=t[x].r && t[x].p) put(x,t[x].p);
    node t1 = query(2*x,l,r);
    node t2 = query(2*x+1,l,r);
    if(t1.sum > t2.sum) return t1;
    else return t2;
}

node work(int x, int t)
{
    int sum = 1, l, r;
    int tot = 0; node cas;
    for(l = x - 1; l >= 1 && tot < k; l --)
    {
        if(!b[l]) b[l] = t, tot ++;
        if(tr[l]) l = tr[l];
    }
    sum += tot; tot = 0;
    for(r = x + 1; r <= n && tot < k; r ++)
    {
        if(!b[r]) b[r] = t, tot ++;
        if(tl[r]) r = tl[r];
    }

    sum += tot; b[x] = t;
    //printf("%d %d %d %d %d", x, t, l, r, k); system("pause");
    cas.l = max(l + 1, 1), cas.r = min(r - 1, n), cas.sum = sum;
    tl[cas.l] = cas.r; tr[cas.r] = cas.l;
    return cas;
}

int main()
{
    rd(n);rd(k);
    for(int i=1;i<=n;i++) rd(a[i]);
    built(1,n,1);
    int tot = 0; int sss = 1;
    while(tot < n)
    {
        int p = query(1, 1, n).res;
        node s;
        if(sss % 2) s = work(p, 1);
        else s = work(p, 2);
        change(1, s.l, s.r);
        sss ++;
        tot += s.sum;
    }
    for(int i = 1; i <= n; i ++) printf("%d", b[i]);
    return 0; 
} 

//不用线段树版
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define N 200010
using namespace std;

int n, k;
int a[N], b[N], to[N], tl[N], tr[N];
bool vis[N];

void work(int x, int j)
{
    int l, r;
    int tot = 0;
    int t = (j % 2) ? 1 : 2;
    for(l = x - 1; l >= 1 && tot < k; l --)
    {
        if(!b[l]) b[l] = t, tot ++, vis[a[l]] = true;
        if(tr[l]) l = tr[l];
    }
    tot = 0;
    for(r = x + 1; r <= n && tot < k; r ++)
    {
        if(!b[r]) b[r] = t, tot ++, vis[a[r]] = true;
        if(tl[r]) r = tl[r];
    } 
    vis[a[x]] = true; b[x] = t;
    tl[l + 1] = r - 1; tr[r - 1] = l + 1;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++) 
        scanf("%d", &a[i]), to[a[i]] = i;
    for(int i = n, j = 0; i; i --)
       if(!vis[i]) j ++, work(to[i], j);
    for(int i = 1; i <= n; i ++) printf("%d", b[i]);
    return 0;
}

心得

这道题考场没调出来，主要是选择了一种繁琐的（线段树）方法，所以我们看问题到多方面思考，最大化利用题目中的性质，往往可以得到出其不意的效果.