可持续化线段树(主席树) 算法模板与图解

2021-02-13互联技术发消息

#include cstdio
#include cmath
#include cstdlib
#include cstring
#include iostream
#include algorithm
#include vector
#include queue
#define lowbit(a) ((a)  (-a))
#define OUT freopen("out.txt", "w", stdout)
#define mem(a, b) memset(a, b, sizeof(a))
#define DEBUG(a) cout  (a)  endl
#define IN freopen("in.txt", "r", stdin)
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxn = 1e4 + 10;
struct node
{
    int ls, rs;
    int sum;
} tree[maxn * 20];

int tot, m;
int root[maxn];
int a[maxn], b[maxn];
string func[maxn];

void disc(int n)
{
    int i;
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - (b + 1);
    for (i = 1; i = n; ++i)
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}
void _insert(int y, int x, int l, int r, int p)
{
    x = ++tot;
    tree[x] = tree[y];
    tree[x].sum++;
    if (l == r)
        return;
    int mid = (l + r)  1;
    if (p = mid)
        _insert(tree[y].ls, tree[x].ls, l, mid, p);
    else
        _insert(tree[y].rs, tree[x].rs, mid + 1, r, p);
}

int query(int x, int y, int l, int r, int k)
{
    if (l == r)
        return l;
    int delta = tree[tree[y].ls].sum - tree[tree[x].ls].sum;
    int mid = (l + r)  1;
    if (k = delta)
        return query(tree[x].ls, tree[y].ls, l, mid, k);
    else
        return query(tree[x].rs, tree[y].rs, mid + 1, r, k - delta);
}

int main()
{
 //   IN;
    IO;
    int t;
    int step = 0;
    while (cin  t)
    {
        for(int i=0;i=tot;i++){
            tree[i] = {0,0,0};
            root[i] = 0;
        }
        tot = 0;
        int tot = 1;
        int buf;
        for (int i = 0; i  t; i++)
        {
            cin  func[i];
            if (func[i] == "in")
            {
                cin  buf;
                a[tot] = buf;
                b[tot] = a[tot];
                tot++;
            }
        }
        disc(tot);
        int now = 0;
        int num = 0;
        int l = 0;
        int r = 0;
        cout "Case #"  ++step ":" endl;
        for (int i = 0; i  t; i++)
        {
            if (func[i] == "in")
            {
                now++;
                _insert(root[now - 1], root[now], 1, m, a[now]);
                num++;
            }
            else if (func[i] == "query")
                DEBUG(b[query(root[l], root[now], 1, m, num / 2 + 1)]);
            else
            {
                l++;
                num--;
            }
        }
    }
    return 0;
}