1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
const int MAXN = 800005;
6
struct Query
7
{
8
    int x, y, op, val, id, pos;
9
    bool operator < (const Query &a) const
10
    {
11
        return x == a.x ? op < a.op : x < a.x;
12
    }
13
} Ask[MAXN], tmp[MAXN];
14
int n, m, Ans[MAXN];
15
#define lowbit(_) ((_)&(-_))
16
struct BIT
17
{
18
    int Sum[2000005];
19
    void add(int x, int c)
20
    {
21
        for (int i = x; i <= n; i += lowbit(i))
22
            Sum[i] += c;
23
    }
24
    int Query(int x)
25
    {
26
        int ans = 0;
27
        for (int i = x; i > 0; i -= lowbit(i))
28
            ans += Sum[i];
29
        return ans;
30
    }
31
}bit;
32
void add()
33
{
34
    int x1, y1, x2, y2;
35
    scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
36
    ++Ans[0];
37
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].op = 1;
38
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y2    , Ask[m].val = 1, Ask[m].op = 1;
39
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2    , Ask[m].val =-1, Ask[m].op = 1;
40
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y1 - 1, Ask[m].val =-1, Ask[m].op = 1;
41
}
42
void CDQ(int l, int r)
43
{
44
    if (l == r)
45
        return;
46
    int mid = l + r >> 1, l1 = l, l2 = mid + 1;
47
    for (int i = l; i <= r; i++)
48
    {
49
        if (Ask[i].id <= mid && !Ask[i].op)
50
            bit.add(Ask[i].y, Ask[i].val);
51
        if (Ask[i].id > mid && Ask[i].op)
52
            Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
53
    }
54
    for (int i = l; i <= r; i++)
55
        if (Ask[i].id <= mid && !Ask[i].op)
56
            bit.add(Ask[i].y, -Ask[i].val);
57
    for (int i = l; i <= r; i++)
58
    {
59
        if (Ask[i].id <= mid)
60
            tmp[l1++] = Ask[i];
61
        else tmp[l2++] = Ask[i];
62
    }
63
    for (int i = l; i <= r; i++)
64
        Ask[i] = tmp[i];
65
    CDQ(l, mid);
66
    CDQ(mid + 1, r);
67
    return;
68
}
69
int main()
70
{
71
    freopen("mokia.in", "r", stdin);
72
    freopen("mokia.out", "w", stdout);
73
    int op;
74
    scanf ("%d%d", &op, &n);
75
    while (1)
76
    {
77
        scanf ("%d", &op);
78
        if (op == 1)
79
        {
80
            m++;
81
            scanf ("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
82
        }
83
        else if (op == 2)
84
            add();
85
        else break;
86
    }
87
    for (int i = 1; i <= m; i++)
88
        Ask[i].id = i;
89
    sort(Ask + 1, Ask + m + 1);
90
    CDQ(1 ,m);
91
    for (int i = 1; i <= Ans[0]; i++)
92
        printf ("%d\n", Ans[i]);
93
}

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4

5
using namespace std;
6

7
inline int read()
8
{
9
  int x=0,f=1;char ch=getchar();
10
  while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11
  while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12
  return x*f;
13
}
14

15
const int MAXN = 20005;
16

17
struct edge
18
{
19
  int END, next;
20
  int v;
21
}v[MAXN << 1];
22
int first[MAXN], p;
23
void add(int a, int b, int c)
24
{
25
  v[p].END = b;
26
  v[p].next = first[a];
27
  v[p].v = c;
28
  first[a] = p++;
29
}
30
int size[MAXN], Max[MAXN], ans, sum, t[3], d[MAXN];
31
bool vis[MAXN];
32
int root;
33
void Get_root(int rt, int fa)
34
{
35
  size[rt] = 1, Max[rt] = 0;
36
  for (int i = first[rt]; i != -1; i = v[i].next)
37
  {
38
    if (!vis[v[i].END] && v[i].END != fa)
39
    {
40
      Get_root(v[i].END, rt);
41
      size[rt] += size[v[i].END];
42
      Max[rt] = max(Max[rt], size[v[i].END]);
43
    }
44
  }
45
  Max[rt] = max(Max[rt], sum - size[rt]);
46
  if (Max[rt] < Max[root]) root = rt;
47
}
48

49
void dfs(int rt, int fa)
50
{
51
  t[d[rt]]++;
52
  for (int i = first[rt]; i != -1; i = v[i].next)
53
  {
54
    if (!vis[v[i].END] && v[i].END != fa)
55
    {
56
      d[v[i].END] = (d[rt] + v[i].v) % 3;
57
      dfs(v[i].END, rt);
58
    }
59
  }
60
}
61

62
int Calc(int rt, int x)
63
{
64
  t[0] = t[1] = t[2] = 0;
65
  d[rt] = x;
66
  dfs(rt, 0);
67
  return t[1] * t[2] * 2 + t[0] * t[0];
68
}
69

70
void Solve(int rt)
71
{
72
  ans += Calc(rt, 0);
73
  vis[rt] = 1;
74
  for (int i = first[rt]; i != -1; i = v[i].next)
75
  {
76
    if (!vis[v[i].END])
77
    {
78
      ans -= Calc(v[i].END, v[i].v);
79
      root = 0, sum = size[v[i].END];
80
      Get_root(v[i].END, 0);
81
      Solve(root);
82
    }
83
  }
84
}
85

86
int gcd(int a, int b)
87
{
88
  return b == 0 ? a : gcd(b, a % b);
89
}
90

91
int main()
92
{
93
  memset (first, -1, sizeof (first));
94
  int n = read();
95
  int a, b, c;
96
  for (int i = 1; i < n; i++)
97
  {
98
    a = read(), b = read(), c = read() % 3;
99
    add(a, b, c);
100
    add(b, a, c);
101
  }
102
  Max[0] = sum = n;
103
  Get_root(1, 0);
104
  Solve(root);
105
  int G = gcd(ans, n * n);
106
  printf ("%d/%d\n", ans / G, n * n / G);
107
}

1
#include <cstdio>
2
#include <cstring>
3
#include <iostream>
4
#include <queue>
5
using namespace std;
6
struct edge {
7
  int END, v, next;
8
} ZHENG[10005], FAN[10005];
9
struct A {
10
  int END, f, g;
11
  bool operator<(const A &a) const {
12
    if (f == a.f) return a.g < g;
13
    return a.f < f;
14
  }
15
};
16
int first_zheng[1005], first_fan[1005], p;
17
int dis[1005];
18
int n;
19
int s;
20
void add(int a, int b, int c);
21
void spfa(int a);
22
int Astar(int k);
23
int main() {
24
  freopen("cowjog.in", "r", stdin);
25
  freopen("cowjog.out", "w", stdout);
26
  // cin>>n>>m;
27
  memset(first_fan, -1, sizeof(first_fan));
28
  memset(first_zheng, -1, sizeof(first_zheng));
29
  p = 1;
30
  int m, a, b, c, K;
31
  scanf("%d%d%d", &n, &m, &K);
32
  for (int i = 1; i <= m; i++) {
33
    scanf("%d%d%d", &a, &b, &c);
34
    if (a > b)
35
      add(a, b, c);
36
    else
37
      add(b, a, c);
38
  }
39
  spfa(1);
40
  for (int k = 1; k <= K; k++) {
41
    s = 0;
42
    cout << Astar(k) << endl;
43
  }
44
  // while(1);
45
}
46
void add(int a, int b, int c) {
47
  ZHENG[p].END = b;
48
  ZHENG[p].v = c;
49
  ZHENG[p].next = first_zheng[a];
50
  FAN[p].END = a;
51
  FAN[p].v = c;
52
  FAN[p].next = first_fan[b];
53
  first_zheng[a] = p;
54
  first_fan[b] = p++;
55
}
56
void spfa(int a) {
57
  memset(dis, 0x3f, sizeof(dis));
58
  dis[a] = 0;
59
  bool flag[1005] = {0};
60
  queue<int> p;
61
  p.push(a);
62
  flag[a] = 1;
63
  while (!p.empty()) {
64
    int tmp = p.front();
65
    flag[tmp] = 0;
66
    p.pop();
67
    for (int i = first_fan[tmp]; i != -1; i = FAN[i].next) {
68
      if (dis[FAN[i].END] > dis[tmp] + FAN[i].v) {
69
        dis[FAN[i].END] = dis[tmp] + FAN[i].v;
70
        if (!flag[FAN[i].END]) {
71
          flag[FAN[i].END] = 1;
72
          p.push(FAN[i].END);
73
        }
74
      }
75
    }
76
  }
77
}
78
int Astar(int k) {
79
  priority_queue<A> p;
80
  A s1, s2;
81
  s1.END = n;
82
  s1.g = 0;
83
  s1.f = s1.g + dis[n];
84
  p.push(s1);
85
  while (!p.empty()) {
86
    s2 = p.top();
87
    p.pop();
88
    if (s2.END == 1) {
89
      s++;
90
      if (s == k) return s2.g;
91
    }
92
    for (int i = first_zheng[s2.END]; i != -1; i = ZHENG[i].next) {
93
      s1.END = ZHENG[i].END;
94
      s1.g = s2.g + ZHENG[i].v;
95
      s1.f = s1.g + dis[ZHENG[i].END];
96
      p.push(s1);
97
    }
98
  }
99
  return -1;
100
}

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <cmath>
5
#include <climits>
6
#include <ctime>
7
using namespace std;
8
const double pi = acos(-1.);
9
const double eps = 1e-10;
10
const int seed = time(0);
11
inline int read()
12
{
13
    int x=0,f=1;char ch=getchar();
14
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16
    return x*f;
17
}
18
double Rand()
19
{
20
    return 1.0 * rand() / RAND_MAX;
21
}
22
struct Point
23
{
24
    double x, y, k;
25
    Point(double _x = 0, double _y = 0): x(_x), y(_y) {
26
        k = atan2(y, x);
27
    }
28
    Point operator - (const Point &_x)
29
    {
30
        return Point(x - _x.x, y - _x.y);
31
    }
32
    double operator * (const Point &_x)
33
    {
34
        return x * _x.y - y * _x.x;
35
    }
36
    bool operator < (const Point &_x) const
37
    {
38
        return k > _x.k;
39
    }
40
}a[10], tmp[10];
41
int cnt = 0;
42
double area(Point *x, int n)
43
{
44
    double ans = 0;
45
    cnt++;
46
    sort(x + 1, x + n + 1);
47
    Point t(0, 0);
48
    for (int i = 1; i <= n - 1; i++)
49
        ans += (x[i] - t) * (x[i + 1] - t);
50
    ans += (x[n] - t) * (x[1] - t);
51
    return fabs(ans);
52
}
53
int r[10];
54
bool cmp(const int &a, const int &b)
55
{
56
    return a > b;
57
}
58
double dis(Point &x, Point &y)
59
{
60
    return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
61
}
62
bool cmp1(Point x, Point y)
63
{
64
    double s = (x - tmp[1]) * (y - tmp[1]);
65
    if (fabs(s) <= eps) return dis(x, tmp[1]) < dis(y, tmp[1]);
66
    return s > 0;
67
}
68
int st[10], top;
69
double Calc(Point *x, int n)
70
{
71
  memcpy(tmp, x, sizeof (tmp));
72
    int k = 0;
73
    for (int i = 1; i <= n; i++)
74
        if (tmp[i].x < tmp[k].x && tmp[i].y < tmp[k].y || !k)
75
            k = i;
76
    swap(tmp[1], tmp[k]);
77
    sort(tmp + 2, tmp + n + 1, cmp1);
78
    top = 0;
79
    st[++top] = 1;
80
    for (int i = 2; i <= n; i++)
81
    {
82
        while (top > 1 && (tmp[st[top]] - tmp[st[top - 1]]) * (tmp[i] - tmp[st[top]]) < 0) top--;
83
        st[++top] = i;
84
    }
85
    for (int i = 1; i <= top; i++)
86
        tmp[i] = tmp[st[i]];
87
    return area(tmp, top);
88
}
89
double T = 1e9, mint = 1e-9, delta = 1 - 1e-2;
90
int loop = 50;
91
double w[10];
92
int main()
93
{
94
    // freopen ("1.out", "w", stdout);
95
    srand(seed);
96
    int n = read();
97
    for (int i = 1; i <= n; i++) r[i] = read();
98
    for (int i = 1; i <= n; i++) w[i] = Rand() * 2 * pi;
99
    for (int i = 1; i <= n; i++) a[i].x = cos(w[i]) * r[i], a[i].y = sin(w[i]) * r[i];
100
    double ans = Calc(a, n);
101
    while (T > mint)
102
    {
103
        for (int i = 1; i <= loop; i++)
104
        {
105
            int t = rand() % n + 1;
106
            double tmp_w = w[t];
107
            w[t] = w[t] + Rand() * 2 * pi * T;
108
            // if (w[t] > 2 * pi) w[t] -= 2 * pi;
109
            a[t].x = cos(w[t]) * r[t], a[t].y = sin(w[t]) * r[t];
110
            double tmp = Calc(a, n);
111
            // printf ("%.2f\n", (tmp - ans) / T);
112
            // printf ("%.2f\n", exp((tmp - ans) / T));
113
            if (tmp > ans || exp((tmp - ans) / T) > Rand())
114
                ans = tmp;
115
            else
116
            {
117
                w[t] = tmp_w;
118
                a[t].x = cos(w[t]) * r[t], a[t].y = sin(w[t]) * r[t];
119
            }
120
        }
121
        T *= delta;
122
    }
123
    printf ("%.10f\n", ans / 2);
124
    // while (1);
125
}

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
int a[50005], in[50005];
6
int block = 500;
7
struct Query
8
{
9
  int l, r, ID;
10
  bool operator < (const Query &b) const
11
  {
12
    return in[l] == in[b.l] ? r > b.r : l < b.l;
13
  }
14
}Q[200005];
15
int cnt[1000005];
16
int out[200005];
17
int main()
18
{
19
  int n, m, ans = 0;
20
  scanf("%d", &n);
21
  for (int i = 1; i <= n; i++)
22
  {
23
    scanf("%d", &a[i]);
24
    in[i] = (i - 1) / block + 1;
25
    cnt[a[i]]++;
26
    if(cnt[a[i]] == 1)
27
      ans++;
28
  }
29
  scanf("%d", &m);
30
  for (int i = 1; i <= m; i++)
31
    scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].ID = i;
32
  sort(Q + 1, Q + m + 1);
33
  int l = 1, r = n + 1;
34
  for (int i = 1; i <= m; i++)
35
  {
36
    while(l < Q[i].l) {cnt[a[l]]--; if(cnt[a[l]] == 0) ans--; l++;}
37
    while(l > Q[i].l) {l--; cnt[a[l]]++; if(cnt[a[l]] == 1) ans++;}
38
    while(r > Q[i].r) {cnt[a[r]]--; if(cnt[a[r]] == 0) ans--; r--;}
39
    while(r < Q[i].r) {r++; cnt[a[r]]++; if(cnt[a[r]] == 1) ans++;}
40
    out[Q[i].ID] = ans;
41
  }
42
  for (int i = 1; i <= m; i++)
43
    printf("%d\n", out[i]);
44
}

1
cnt = 0;
2
for (int i = 1; i <= n; i++) {
3
  a[i] = read();
4
  Hash[++cnt] = a[i];
5
}
6
sort(Hash + 1, Hash + cnt + 1);
7
cnt = unique(Hash + 1, Hash + cnt + 1) - Hash - 1;
8
for (int i = 1; i <= n; i++) {
9
  a[i] = lower_bound(Hash + 1, Hash + cnt + 1, a[i]) - Hash;
10
}

1
const int MAXN = 200000, BASE = 76543;
2
struct Hash_Table
3
{
4
    struct edge
5
    {
6
        int Id, next;
7
        long long Max;
8
    }v[MAXN];
9
    int first[BASE + 2], p;
10
    Hash_Table()
11
    {
12
        memset (first, -1, sizeof (first));
13
        p = 0;
14
    }
15
    void clear()
16
    {
17
        memset (first, -1, sizeof (first));
18
        p = 0;
19
    }
20
    long long &operator[](int x)
21
    {
22
        int H = x % BASE;
23
        for (int i = first[H]; i != -1; i = v[i].next)
24
            if (v[i].Id == x)
25
                return v[i].Max;
26
        v[p].Id = x;
27
        v[p].next = first[H];
28
        first[H] = p++;
29
        return v[p - 1].Max = -INF;
30
    }
31
}Hash;

1
struct Treap
2
{
3
    struct Node
4
    {
5
        int s, key, Max_Num, Max_Size;
6
        data x;
7
        Node *ch[2];
8
        Node(data sa)
9
        {
10
            ch[0] = ch[1] = NULL;
11
            s = 1, x = sa, key = rand();
12
            Max_Num = Max_Size = 0;
13
        }
14
#define size(_) ((_) ? (_)->s : 0)
15
        void Pushup()
16
        {
17
            s = size(ch[0]) + size(ch[1]) + 1;
18
        }
19
        void Pushdown()
20
        {
21
            if (ch[0])
22
            {
23
                ch[0]->Max_Num = max(ch[0]->Max_Num, Max_Num);
24
                ch[0]->Max_Size = max(ch[0]->Max_Size, Max_Size);
25
                Max_Morale[ch[0]->x.ID] = max(Max_Morale[ch[0]->x.ID], ch[0]->Max_Num);
26
                Max_Solidarity[ch[0]->x.ID] = max(Max_Solidarity[ch[0]->x.ID], ch[0]->Max_Size);
27
            }
28
            if (ch[1])
29
            {
30
                ch[1]->Max_Num = max(ch[1]->Max_Num, Max_Num);
31
                ch[1]->Max_Size = max(ch[1]->Max_Size, Max_Size);
32
                Max_Morale[ch[1]->x.ID] = max(Max_Morale[ch[1]->x.ID], ch[1]->Max_Num);
33
                Max_Solidarity[ch[1]->x.ID] = max(Max_Solidarity[ch[1]->x.ID], ch[1]->Max_Size);
34
            }
35
            Max_Num = Max_Size = 0;
36
        }
37
    } * root;
38
    Treap()
39
    {
40
        root = NULL;
41
    }
42
    Node *Merge(Node *A, Node *B)
43
    {
44
        if (!A)
45
            return B;
46
        if (!B)
47
            return A;
48
        if (A->key < B->key)
49
        {
50
            A->Pushdown();
51
            A->ch[1] = Merge(A->ch[1], B);
52
            A->Pushup();
53
            return A;
54
        }
55
        else
56
        {
57
            B->Pushdown();
58
            B->ch[0] = Merge(A, B->ch[0]);
59
            B->Pushup();
60
            return B;
61
        }
62
    }
63
    typedef pair<Node *, Node *> DNode;
64
    DNode Split(Node *rt, int k)
65
    {
66
        if (!rt)
67
            return DNode(NULL, NULL);
68
        DNode o;
69
        rt->Pushdown();
70
        if (size(rt->ch[0]) >= k)
71
        {
72
            o = Split(rt->ch[0], k);
73
            rt->ch[0] = o.second;
74
            rt->Pushup();
75
            o.second = rt;
76
        }
77
        else
78
        {
79
            o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
80
            rt->ch[1] = o.first;
81
            rt->Pushup();
82
            o.first = rt;
83
        }
84
        return o;
85
    }
86
    Node *kth(int k)
87
    {
88
        DNode x = Split(root, k - 1);
89
        DNode y = Split(x.second, 1);
90
        Node *ans = y.first;
91
        root = Merge(Merge(x.first, ans), y.second);
92
        return ans;
93
    }
94
    int Rank(Node *rt, data x)
95
    {
96
        if (!rt)
97
            return 0;
98
        return x <= rt->x ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
99
    }
100
    void Insert(data x)
101
    {
102
        int k = Rank(root, x);
103
        if (root)
104
        {
105
            root->Max_Size = max(root->Max_Size, size(root));
106
            root->Max_Num = max(root->Max_Num, x.x);
107
            Max_Morale[root->x.ID] = max(root->Max_Num, Max_Morale[root->x.ID]);
108
            Max_Solidarity[root->x.ID] = max(root->Max_Size, Max_Solidarity[root->x.ID]);
109
        }
110
        DNode y = Split(root, k);
111
        Node *n = new Node(x);
112
        root = Merge(Merge(y.first, n), y.second);
113
    }
114
    void remove(data x)
115
    {
116
        int k = Rank(root, x);
117
        DNode a = Split(root, k);
118
        DNode b = Split(a.second, 1);
119
        delete b.first;
120
        root = Merge(a.first, b.second);
121
    }
122
};

1
namespace Scapegoat_Tree
2
{
3
    const int MAXN = 1e6 + 10;
4
    const double alpha = 0.756;
5
    struct Node
6
    {
7
        Node *ch[2];
8
        int key, s, cover;
9
        bool exist;
10
        void Pushup()
11
        {
12
            s = ch[0]->s + ch[1]->s + exist;
13
            cover = ch[0]->cover + ch[1]->cover + 1;
14
        }
15
        bool isBad()
16
        {
17
            return ((ch[0]->cover > cover * alpha + 5) || (ch[1]->cover > cover * alpha + 5));
18
        }
19
    };
20
    struct Stree
21
    {
22
        Node mem_poor[MAXN];
23
        Node *tail, *root, *null, *ls[MAXN];
24
        Node *bc[MAXN]; int bc_top, top;
25
        Node *NewNode(int key)
26
        {
27
            Node *o = bc_top ? bc[--bc_top] : tail++;
28
            o->ch[0] = o->ch[1] = null;
29
            o->s = o->cover = o->exist = 1;
30
            o->key = key;
31
            return o;
32
        }
33
        void Travel(Node *rt)
34
        {
35
            if (rt == null) return;
36
            Travel(rt->ch[0]);
37
            if (rt->exist) ls[++top] = rt;
38
            else bc[bc_top++] = rt;
39
            Travel(rt->ch[1]);
40
        }
41
        Node *Divide(int l, int r)
42
        {
43
            if (l > r) return null;
44
            int mid = (l + r) >> 1;
45
            Node *o = ls[mid];
46
            o->ch[0] = Divide(l, mid - 1);
47
            o->ch[1] = Divide(mid + 1, r);
48
            o->Pushup();
49
            return o;
50
        }
51
        void ReBuild(Node *&rt)
52
        {
53
            top = 0;
54
            Travel(rt);
55
            rt = Divide(1, top);
56
        }
57
        Node ** Insert(Node *&rt, int val)
58
        {
59
            if (rt == null)
60
            {
61
                rt = NewNode(val);
62
                return &null;
63
            }
64
            else
65
            {
66
                Node **res = Insert(rt->ch[val >= rt->key], val);
67
                rt->Pushup();
68
                if (rt->isBad()) res = &rt;
69
                return res;
70
            }
71
        }
72
        void erase(Node *rt, int id)
73
        {
74
            rt->s--;
75
            int offset = rt->ch[0]->s + rt->exist;
76
            if (rt->exist && id == offset)
77
            {
78
                rt->exist = false;
79
                return;
80
            }
81
            else
82
            {
83
                if (id <= offset) erase(rt->ch[0], id);
84
                else erase(rt->ch[1], id - offset);
85
            }
86
        }
87
        Stree()
88
        {
89
            tail = mem_poor;
90
            null = tail++;
91
            null->ch[0] = null->ch[1] = null;
92
            null->cover = null->s = null->key = 0;
93
            root = null; bc_top = 0;
94
        }
95
        void Insert(int val)
96
        {
97
            Node **rt = Insert(root, val);
98
            if (*rt != null) ReBuild(*rt);
99
        }
100
        int Rank(int val)
101
        {
102
            Node *rt = root;
103
            int ans = 1;
104
            while (rt != null)
105
            {
106
                if (rt->key >= val) rt = rt->ch[0];
107
                else
108
                {
109
                    ans += rt->ch[0]->s + rt->exist;
110
                    rt = rt->ch[1];
111
                }
112
            }
113
            return ans;
114
        }
115
        int Kth(int k)
116
        {
117
            Node *rt = root;
118
            while (rt != null)
119
            {
120
                if (rt->ch[0]->s + 1 == k && rt->exist) return rt->key;
121
                else if (rt->ch[0]->s >= k) rt = rt->ch[0];
122
                else k -= rt->ch[0]->s + rt->exist, rt = rt->ch[1];
123
            }
124
        }
125
        void erase(int k)
126
        {
127
            erase(root, Rank(k));
128
            if (root->s < alpha * root->cover) ReBuild(root);
129
        }
130
    };
131
}