tree

发表于 |
字数统计: 533 | 阅读时长 ≈ 2
  • Code Level:※※
  • Thinking Level:※

Description

有n个盒子，每个盒子里可以装一个球，起初这些盒子里是没有球的，接下
来有m个操作，操作有2种类型，一种是放球，一种是拿球，放球的话，需要使得
这个放的球离最近的球距离最大，如果有多个符合条件的盒子，选择其编号最小
的盒子。拿球就是直接从某个盒子中将求拿出。求出每次放球放的盒子编号。

Solution

用set维护距离的最大值，每次取出就是合并序列，放入就是分割序列

Code

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
#include<set>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Nn=4000005;
int N,M,Pos[Nn],L[Nn],R[Nn];
struct Alpha{
    int l,r,len,pos;
    friend bool operator<(Alpha a,Alpha b){
        if(a.len==b.len) return a.pos>b.pos;
        return a.len<b.len;
    }
};
set<Alpha>q; set<Alpha>::iterator it;
void Insert(int x){
    it=q.end(); it--;
    int l=it->l,r=it->r,len=it->len,pos=it->pos; Pos[x]=pos; R[l]=pos; L[r]=pos; R[pos]=r; L[pos]=l; q.erase(it);
    if(pos-l>1) q.insert((Alpha){l,pos,(pos-l)/2,(pos+l)/2});
    if(r-pos>1){
        if(r==N+1) q.insert((Alpha){pos,N+1,N-pos,N});
        else q.insert((Alpha){pos,r,(r-pos)/2,(r+pos)/2});
    }
    printf("%d\n",Pos[x]);
}
void Delet(int x){
    int now=Pos[x],l=L[now],r=R[now]; R[l]=r; L[r]=l;
    if(now-l>1){
        if(l==0) q.erase((Alpha){l,now,now-1,1});
        else q.erase((Alpha){l,now,(now-l)/2,(now+l)/2});
    }
    if(r-now>1){
        if(r==N+1) q.erase((Alpha){now,N+1,N-now,N});
        else q.erase((Alpha){now,r,(r-now)/2,(r+now)/2});
    }
    if(l==0) q.insert((Alpha){l,r,r-1,1});
    else if(r==N+1) q.insert((Alpha){l,r,N-l,N});
    else q.insert((Alpha){l,r,(r-l)/2,(r+l)/2});
}
int main(){
    scanf("%d%d",&N,&M);  q.insert((Alpha){0,N+1,1,1});
    for(int i=1,x,y;i<=M;i++){
        scanf("%d%d",&x,&y);
        if(x==1) Insert(y);
        else Delet(y);
    }
    return 0;
}