原题链接：http://acdream.info/problem?pid=1738
树套树裸题，如下：
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define lc root<<1
#define rc root<<1|1
using std::sort;
using std::lower_bound;
using std::upper_bound;
const int Max_N = ;
const int INF = ~0u >> ;
struct Node {
int v, s, c;
Node *ch[];
inline void set(int _v, int _s, Node *p) {
v = _v, s = c = _s;
ch[] = ch[] = p;
}
inline void push_up() {
s = ch[]->s + ch[]->s + c;
}
inline int cmp(int x) const {
return x == v ? - : x > v;
}
};
struct SizeBalanceTree {
int top, ans, tot, sum, arr[Max_N];
Node *null, *tail, stack[Max_N * ];
Node *store[Max_N << ], *ptr[Max_N << ];
inline void init(int n) {
top = ;
tail = &stack[];
null = tail++;
null->set(, , NULL);
for (int i = ; i <= n; i++) scanf("%d", &arr[i]);
seg_built(, , n);
}
inline Node *newNode(int v) {
Node *p = null;
if (!top) p = tail++;
else p = store[--top];
p->set(v, , null);
return p;
}
inline void rotate(Node *&x, int d) {
Node *k = x->ch[!d];
x->ch[!d] = k->ch[d];
k->ch[d] = x;
k->s = x->s;
x->push_up();
x = k;
}
inline void Maintain(Node *&x, int d) {
if (!x->ch[d]->s) return;
if (x->ch[d]->ch[d]->s > x->ch[!d]->s) {
rotate(x, !d);
} else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) {
rotate(x->ch[d], d), rotate(x, !d);
} else {
return;
}
Maintain(x, ), Maintain(x, );
}
inline void insert(Node *&x, int v) {
if (x == null) {
x = newNode(v);
return;
} else {
x->s++;
int d = x->cmp(v);
if (- == d) {
x->c++;
return;
}
insert(x->ch[d], v);
x->push_up();
Maintain(x, d);
}
}
inline void del(Node *&x, int v) {
if (!x->s) return;
x->s--;
int d = x->cmp(v);
if (- == d) {
if (x->c > ) {
x->c--;
return;
} else if (!x->ch[]->s || !x->ch[]->s) {
store[top++] = x;
x = x->ch[]->s ? x->ch[] : x->ch[];
} else {
Node *ret = x->ch[];
for (; ret->ch[]->s; ret = ret->ch[]);
del(x->ch[], x->v = ret->v);
}
} else {
del(x->ch[d], v);
}
if (x->s) x->push_up();
}
inline Node *get_min(Node *x) {
for (; x->ch[]->s; x = x->ch[]);
return x;
}
inline int find(Node *x, int v) {
while (x->s && x->v != v) x = x->ch[v > x->v];
return x->c;
}
inline int count(Node *x, int v) {
int res = , t = ;
for (; x->s;) {
t = x->ch[]->s;
if (v < x->v) x = x->ch[];
else res += t + x->c, x = x->ch[];
}
return res;
}
inline void seg_built(int root, int l, int r) {
ptr[root] = null;
for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
if (l == r) return;
int mid = (l + r) >> ;
seg_built(lc, l, mid);
seg_built(rc, mid + , r);
}
inline void seg_modify(int root, int l, int r, int pos, int v){
if (pos > r || pos < l) return;
del(ptr[root], arr[pos]);
insert(ptr[root], v);
if (l == r) return;
int mid = (l + r) >> ;
seg_modify(lc, l, mid, pos, v);
seg_modify(rc, mid + , r, pos, v);
}
inline void seg_query_min(int root, int l, int r, int x, int y) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
Node *ret = get_min(ptr[root]);
if (ret->v < ans) ans = ret->v;
return;
}
int mid = (l + r) >> ;
seg_query_min(lc, l, mid, x, y);
seg_query_min(rc, mid + , r, x, y);
}
inline void seg_query_tot(int root, int l, int r, int x, int y, int val) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
tot += find(ptr[root], val);
return;
}
int mid = (l + r) >> ;
seg_query_tot(lc, l, mid, x, y, val);
seg_query_tot(rc, mid + , r, x, y, val);
}
inline void seg_query_count(int root, int l, int r, int x, int y, int val) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
sum += count(ptr[root], val);
return;
}
int mid = (l + r) >> ;
seg_query_count(lc, l, mid, x, y, val);
seg_query_count(rc, mid + , r, x, y, val);
}
inline void gogo(int n) {
int a, b, c, d;
scanf("%d", &a);
if ( == a) {
scanf("%d %d", &b, &c);
seg_modify(, , n, b, c), arr[b] = c;
} else if ( == a) {
ans = INF, tot = ;
scanf("%d %d", &b, &c);
seg_query_min(, , n, b, c);
seg_query_tot(, , n, b, c, ans);
printf("%d %d\n", ans, tot);
} else {
sum = ;
scanf("%d %d %d", &b, &c, &d);
seg_query_count(, , n, b, c, d);
printf("%d\n", sum);
}
}
}sbt;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif;
int n, m;
while (~scanf("%d %d", &n, &m)) {
sbt.init(n);
while (m--) sbt.gogo(n);
}
return ;
}
如果觉得sb树跑的慢，再写个红黑树吧。。。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define lc root<<1
#define rc root<<1|1
const int Max_N = ;
const int INF = ~0u >> ;
struct Node {
int data, s, c;
bool color;
Node *fa, *ch[];
inline void set(int _v, bool _color, int i, Node *p) {
data = _v, color = _color, s = c = i;
fa = ch[] = ch[] = p;
}
inline void push_up() {
s = ch[]->s + ch[]->s + c;
}
inline void push_down() {
for (Node *x = this; x->s; x = x->fa) x->s--;
}
inline int cmp(int v) const {
return data == v ? - : v > data;
}
};
struct RedBlackTree {
int top, ans, tot, sum, arr[Max_N];
Node *null, *tail;
Node stack[Max_N * ], *store[Max_N << ], *ptr[Max_N << ];
inline void init(int n) {
top = ;
tail = &stack[];
null = tail++;
null->set(, , , NULL);
for (int i = ; i <= n; i++) scanf("%d", &arr[i]);
seg_built(, , n);
}
inline Node *newNode(int v) {
Node *p = null;
if (!top) p = tail++;
else p = store[--top];
p->set(v, , , null);
return p;
}
inline void rotate(int root, Node* &x, bool d) {
Node *y = x->ch[!d];
x->ch[!d] = y->ch[d];
if (y->ch[d]->s) y->ch[d]->fa = x;
y->fa = x->fa;
if (!x->fa->s) ptr[root] = y;
else x->fa->ch[x->fa->ch[] != x] = y;
y->ch[d] = x;
x->fa = y;
y->s = x->s;
x->push_up();
}
inline void insert(int root, int v) {
Node *x = ptr[root], *y = null;
while (x->s) {
x->s++, y = x;
int d = x->cmp(v);
if (- == d) {
x->c++;
return;
}
x = x->ch[d];
}
x = newNode(v);
if (y->s) y->ch[v > y->data] = x;
else ptr[root] = x;
x->fa = y;
insert_fix(root, x);
}
inline void insert_fix(int root, Node* &x) {
while (x->fa->color) {
Node *par = x->fa, *Gp = par->fa;
bool d = par == Gp->ch[];
Node *uncle = Gp->ch[d];
if (uncle->color) {
par->color = uncle->color = ;
Gp->color = ;
x = Gp;
} else if (x == par->ch[d]) {
rotate(root, x = par, !d);
} else {
Gp->color = ;
par->color = ;
rotate(root, Gp, d);
}
}
ptr[root]->color = ;
}
inline Node *find(Node *x, int data) {
while (x->s && x->data != data) x = x->ch[x->data < data];
return x;
}
inline void del_fix(int root, Node* &x) {
while (x != ptr[root] && !x->color) {
bool d = x == x->fa->ch[];
Node *par = x->fa, *sibling = par->ch[d];
if (sibling->color) {
sibling->color = ;
par->color = ;
rotate(root, x->fa, !d);
sibling = par->ch[d];
} else if (!sibling->ch[]->color && !sibling->ch[]->color) {
sibling->color = , x = par;
} else {
if (!sibling->ch[d]->color) {
sibling->ch[!d]->color = ;
sibling->color = ;
rotate(root, sibling, d);
sibling = par->ch[d];
}
sibling->color = par->color;
sibling->ch[d]->color = par->color = ;
rotate(root, par, !d);
break;
}
}
x->color = ;
}
inline void del(int root, int data) {
Node *z = find(ptr[root], data);
if (!z->s) return;
if (z->c > ) {
z->c--;
z->push_down();
return;
}
Node *y = z, *x = null;
if (z->ch[]->s && z->ch[]->s) {
y = z->ch[];
while (y->ch[]->s) y = y->ch[];
}
x = y->ch[!y->ch[]->s];
x->fa = y->fa;
if (!y->fa->s) ptr[root] = x;
else y->fa->ch[y->fa->ch[] == y] = x;
if (z != y) z->data = y->data, z->c = y->c;
y->fa->push_down();
for (Node *k = y->fa; y->c > && k->s && k != z; k = k->fa) k->s -= y->c - ;
if (!y->color) del_fix(root, x);
store[top++] = y;
}
inline Node* get_min(Node *x) {
for (; x->ch[]->s; x = x->ch[]);
return x;
}
inline int count(Node *x, int v) {
int res = , t = ;
for (; x->s;) {
t = x->ch[]->s;
if (v < x->data) x = x->ch[];
else res += t + x->c, x = x->ch[];
}
return res;
}
inline void seg_built(int root, int l, int r) {
ptr[root] = null;
for (int i = l; i <= r; i++) insert(root, arr[i]);
if (l == r) return;
int mid = (l + r) >> ;
seg_built(lc, l, mid);
seg_built(rc, mid + , r);
}
inline void seg_modify(int root, int l, int r, int pos, int v){
if (pos > r || pos < l) return;
del(root, arr[pos]);
insert(root, v);
if (l == r) return;
int mid = (l + r) >> ;
seg_modify(lc, l, mid, pos, v);
seg_modify(rc, mid + , r, pos, v);
}
inline void seg_query_min(int root, int l, int r, int x, int y) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
Node *ret = get_min(ptr[root]);
if (ret->data < ans) ans = ret->data;
return;
}
int mid = (l + r) >> ;
seg_query_min(lc, l, mid, x, y);
seg_query_min(rc, mid + , r, x, y);
}
inline void seg_query_tot(int root, int l, int r, int x, int y, int val) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
tot += find(ptr[root], val)->c;
return;
}
int mid = (l + r) >> ;
seg_query_tot(lc, l, mid, x, y, val);
seg_query_tot(rc, mid + , r, x, y, val);
}
inline void seg_query_count(int root, int l, int r, int x, int y, int val) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
sum += count(ptr[root], val);
return;
}
int mid = (l + r) >> ;
seg_query_count(lc, l, mid, x, y, val);
seg_query_count(rc, mid + , r, x, y, val);
}
inline void gogo(int n) {
int a, b, c, d;
scanf("%d", &a);
if ( == a) {
scanf("%d %d", &b, &c);
seg_modify(, , n, b, c), arr[b] = c;
} else if ( == a) {
ans = INF, tot = ;
scanf("%d %d", &b, &c);
seg_query_min(, , n, b, c);
seg_query_tot(, , n, b, c, ans);
printf("%d %d\n", ans, tot);
} else {
sum = ;
scanf("%d %d %d", &b, &c, &d);
seg_query_count(, , n, b, c, d);
printf("%d\n", sum);
}
}
}rbt;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int n, m;
while (~scanf("%d %d", &n, &m)) {
rbt.init(n);
while (m--) rbt.gogo(n);
}
return ;
}