bzoj 5155: [Tjoi2014]电源插排

题意：

题解：

好像写复杂了。。。
找最长的区间可以用可删堆来实现，维护它可以用一个set，询问用线段树。因为$n \le 10 ^ 9$，所以要动态开点。

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

int n, Q;
map<int, int> a;
struct th
{
    int l, r;
    th(int l, int r) : l(l), r(r) {}
};
bool operator<(th x, th y) { return x.r - x.l == y.r - y.l ? x.r < y.r : x.r - x.l < y.r - y.l; }
bool operator==(th x, th y) { return x.l == y.l && x.r == y.r; }
struct pq
{
    priority_queue<th> a, b;
    int size() { return a.size() - b.size(); }
    void push(th x)
    {
        while (!b.empty() && a.top() == b.top()) a.pop(), b.pop();
        a.push(x);
    }
    void pop()
    {
        while (!b.empty() && a.top() == b.top()) a.pop(), b.pop();
        a.pop();
    }
    th top()
    {
        while (!b.empty() && a.top() == b.top()) a.pop(), b.pop();
        return a.top();
    }
    void erase(th x)
    {
        b.push(x);
    }
} q;
set<int> s;
struct tree
{
    int l, r, c;
    tree *lc, *rc;
    tree(int l, int r) : l(l), r(r), c(0), lc(NULL), rc(NULL) {}
} *root;

void add(tree *i, int p, int x)
{
    if (i->l == i->r)
    {
        i->c += x;
        return;
    }
    int md = i->l + i->r >> 1;
    if (p <= md)
    {
        if (!i->lc) i->lc = new tree(i->l, md);
        add(i->lc, p, x);
    }
    else
    {
        if (!i->rc) i->rc = new tree(md + 1, i->r);
        add(i->rc, p, x);
    }
    i->c = (i->lc ? i->lc->c : 0) + (i->rc ? i->rc->c : 0);
}
int get(tree *i, int l, int r)
{
    if (!i) return 0;
    if (i->l == l && i->r == r) return i->c;
    int md = i->l + i->r >> 1;
    if (r <= md) return get(i->lc, l, r);
    else if (l > md) return get(i->rc, l, r);
    else return get(i->lc, l, md) + get(i->rc, md + 1, r);
}
int main()
{
    scanf("%d%d", &n, &Q);
    root = new tree(1, n);
    q.push(th(1, n));
    s.insert(0);
    s.insert(n + 1);
    while (Q--)
    {
        int k;
        scanf("%d", &k);
        if (k)
        {
            if (a[k])
            {
                add(root, a[k], -1);
                set<int>::iterator it = s.find(a[k]), itl = it, itr = it;
                itl--;
                itr++;
                if (*itl + 1 <= a[k] - 1) q.erase(th(*itl + 1, a[k] - 1));
                if (a[k] + 1 <= *itr - 1) q.erase(th(a[k] + 1, *itr - 1));
                q.push(th(*itl + 1, *itr - 1));
                s.erase(a[k]);
                a[k] = 0;
            }
            else
            {
                th hh = q.top();
                a[k] = hh.l + hh.r + 1 >> 1;
                s.insert(a[k]);
                q.erase(hh);
                if (hh.l < a[k]) q.push(th(hh.l, a[k] - 1));
                if (a[k] < hh.r) q.push(th(a[k] + 1, hh.r));
                add(root, a[k], 1);
            }
        }
        else
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", get(root, l, r));
        }
    }
}