线段树区间合并一下， 求当前要占的位置， 不包括两端点的写起来方便一点。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long longusing namespace std;const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-);int n, m, tot, pos[];
PII gg[];#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
struct info {
PII mx;
int cnt, L, R;
} a[N << ];
info operator + (const info& a, const info& b) {
info c;
c.cnt = a.cnt + b.cnt;
c.mx = max(a.mx, b.mx);
c.L = min(a.L, b.L); c.R = max(a.R, b.R);
if(a.cnt && b.cnt && a.R + < b.L) {
int p = (b.L + a.R) / ;
c.mx = max(c.mx, mk(min(b.L - p, p - a.R), -p));
}
return c;
}void build(int l, int r, int rt) {
if(l == r) {
a[rt].cnt = ;
a[rt].L = inf;
a[rt].R = -inf;
a[rt].mx = mk(, );
return;
}
int mid = l + r >> ;
build(lson); build(rson);
a[rt] = a[rt << ] + a[rt << | ];
}void update(int p, int op, int l, int r, int rt) {
if(l == r) {
if(op == ) {
a[rt].cnt = ;
a[rt].L = a[rt].R = p;
a[rt].mx = mk(, );
} else {
a[rt].cnt = ;
a[rt].L = inf;
a[rt].R = -inf;
a[rt].mx = mk(, );
}
return;
}
int mid = l + r >> ;
if(p <= mid) update(p, op, lson);
else update(p, op, rson);
a[rt] = a[rt << ] + a[rt << | ];
}int main() {
scanf("%d%d", &n, &m);
build(, n, );
while(m--) {
int op, x;
scanf("%d%d", &op, &x);
if(op == ) {
tot = ;
if(a[].mx.se) gg[tot++] = a[].mx;
if(a[].L != && a[].cnt) gg[tot++] = mk(a[].L - , -);
if(a[].R != n && a[].cnt) gg[tot++] = mk(n - a[].R, -n);
if(!tot) gg[tot++] = mk(inf, -);
sort(gg, gg + tot);
reverse(gg, gg + tot);
pos[x] = -gg[].se;
update(-gg[].se, , , n, );
printf("%d\n", -gg[].se); } else {
update(pos[x], -, , n, );
}
}
return ;
}/*
*/
