[BZOJ 5155][Tjoi2014]电源插排

网上大部分题解都写得是动态开点线段树,然而像\(MiEcoku\)这么懒惰的显然不会去写线段树...

\(\color{green}{solution}\)

我们考虑来点骚操作. 线段树维护的是区间最长连续空段,那么我们能不能单独把空的区间提出来呢?这样就可以
不用线段树了.

对于连续的一段空区间,我们可以用一个\(set\)去维护. 那么空区间的问题解决了,现在怎么求区间内有多少个插排被使用呢?
这...如果没有同学离开,那么随便用一个数据结构就可以维护. 但因为我们需要支持删除操作,所以我用平衡树维护.

具体的删除操作：
在一位同学离开后,假设他的位置是\(p\), 他前面第一个被使用的位置是\(p_l\), 他后面第一个
被使用的位置是\(p_r\), 那么我们只需要再\(set\)中删除区间 \([p_l+1, p-1]\) 和区间 \([p+1, p_r-1]\)(如果区间存在)
再将区间 \([p_l+1, p_r-1]\) 加入\(set\)即可

具体实现详见代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;

struct line {
    int l, r;
    bool operator < (const line &a) const {
        return r-l == a.r-a.l ? r > a.r : r-l > a.r-a.l;
    }
    line (int l, int r) : l(l), r(r) {}
    line () {}
};
set<line> tc; map<int, int> id;
struct node {int v, ky, sz; node *ls, *rs;};
node *nul, pool[maxn], *pis = pool, *rt;
inline void init() {
    nul=pis; nul->ls=nul->rs=nul; nul->sz=0; rt=nul; srand(19260817);
}
node *newnode(int val) {
    node *k = ++ pis; k->ls = k->rs = nul;
    k->v=val; k->sz = 1; k->ky = rand(); return k;
}
inline void up(node *&x) { x->sz = x->ls->sz + x->rs->sz + 1;}
inline void spl(node *c, node *&x, node *&y, int val) {
    if( c == nul) { x = y = nul; return;}
    if( c->v <= val) x = c, spl(c->rs, x->rs, y, val);
    else y = c, spl(c->ls, x, y->ls, val); up(c);
}
inline void mrg(node *&c, node *x, node *y) {
    if( x==nul || y==nul) {c = x==nul ? y : x; return;}
    if( x->ky < y->ky) c = x, mrg(c->rs, x->rs, y);
    else c = y, mrg(c->ls, x, y->ls); up(c);
}
int insert() {
    line c = *tc.begin(); tc.erase(tc.begin());
    int pos = c.r + c.l + 1 >> 1;
    tc.insert(line(c.l,pos-1)); tc.insert(line(pos+1,c.r));
//  printf("%d -\n", pos); // de bug
    node *x, *y;
    spl(rt, x, y, pos); mrg(x, x, newnode(pos)); mrg(rt, x, y);
    return pos;
}
inline void erase(int opt) {
    node *x, *y, *z, *c; spl(rt, x, y, opt); spl(x, x, z, opt-1);
    int l, r;
    c=x; while( c->rs!=nul) c = c->rs; l = c->v;
    c=y; while( c->ls!=nul) c = c->ls; r = c->v;
    mrg(rt, x, y);
    tc.erase(line(l+1, opt-1)); tc.erase(line(opt+1, r-1));
    tc.insert(line(l+1, r-1));
}
inline void modify(int opt) {
    if( id[opt]) erase(id[opt]), id[opt] = 0;
    else id[opt] = insert();
}
inline void qry(int l, int r) {
    node *x, *y, *z; spl(rt, x, y, r); spl(x, x, z, l-1);
    printf("%d\n", z->sz); mrg(x, x, z); mrg(rt, x, y);
}
int n, Q;
int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("b.out","w",stdout);
#endif
    init();
    scanf("%d%d", &n, &Q); tc.insert(line(1, n));
    mrg(rt, rt, newnode(0)); mrg(rt, rt, newnode(n+1));
    for ( register int i = 1, opt, l, r; i <= Q; ++ i) {
        scanf("%d", &opt);
        if( opt) modify(opt);
        else scanf("%d%d", &l, &r), qry(l, r);
    }
    return 0;
}

巴特西

[BZOJ 5155][Tjoi2014]电源插排

最新文章

热门文章