http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3154
题意是，要求求出区间中小于某个值的数有多少个，然后利用这个个数来更新某个点的值。
直接树套树解决问题，不过这题时间卡的比较紧。留心观察可以发现，询问的数目其实是比较小的，可是总的个数多大30W。如果是O(n*logn*logn)的复杂度建树就会超时，估计这里就是卡这一个了。其余的都不难，不过就是开始的时候没有看出可以卡时间卡这么紧，没有建树的经验，所以直接暴力插点，一直TLE。中间的时候sbt又写错了，为了debug个RE又搞了半天。
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <set>
#include <cctype>
#include <cmath> using namespace std; #define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, n, 1 const int N = ;
typedef long long LL; struct Node {
Node *c[];
int ky, sz;
void init(int k = ) {
ky = k;
sz = ;
c[] = c[] = NULL;
}
} node[N * ];
int ttnd; void init() { ttnd = ;} struct Treap {
Node *RT;
void init() { RT = NULL;}
int size() { return RT->sz;}
void make(int *arr, int l, int r, Node *&rt) {
if (l > r) return ;
if (l == r) {
rt = node + ttnd++;
rt->init(arr[l]);
return ;
}
int m = l + r >> ;
rt = node + ttnd++;
rt->init(arr[m]);
make(arr, l, m - , rt->c[]);
make(arr, m + , r, rt->c[]);
rt->sz = (rt->c[] ? rt->c[]->sz : ) + (rt->c[] ? rt->c[]->sz : ) + ;
}
void make(int *arr, int l, int r) {
init();
make(arr, l, r, RT);
}
void rotate(Node *&rt, bool l) {
bool r = !l;
Node *p = rt->c[l];
rt->c[l] = p->c[r];
p->c[r] = rt;
p->sz = rt->sz;
rt->sz = (rt->c[] ? rt->c[]->sz : ) + (rt->c[] ? rt->c[]->sz : ) + ;
rt = p;
}
void maintain(Node *&rt, bool r) {
if (!rt || !rt->c[r]) return ;
bool l = !r;
int ls = rt->c[l] ? rt->c[l]->sz : ;
if (rt->c[r]->c[r] && rt->c[r]->c[r]->sz > ls) {
rotate(rt, r);
} else if (rt->c[r]->c[l] && rt->c[r]->c[l]->sz > ls) {
rotate(rt->c[r], l), rotate(rt, r);
} else return ;
maintain(rt->c[], false);
maintain(rt->c[], true);
maintain(rt, false);
maintain(rt, true);
}
void insert(Node *&rt, Node *x) {
if (!rt) {
rt = x;
return ;
}
rt->sz++;
if (x->ky < rt->ky) insert(rt->c[], x);
else insert(rt->c[], x);
maintain(rt, x->ky >= rt->ky);
}
void insert(int k) {
Node *tmp = node + ttnd++;
tmp->init(k);
insert(RT, tmp);
}
void erase(Node *&rt, int k) {
if (!rt) return ;
rt->sz--;
if (k < rt->ky) erase(rt->c[], k);
else if (k > rt->ky) erase(rt->c[], k);
else {
if (!rt->c[] && !rt->c[]) rt = NULL;
else if (!rt->c[]) rt = rt->c[];
else if (!rt->c[]) rt = rt->c[];
else {
Node *t = rt->c[];
while (t->c[]) t = t->c[];
rt->ky = t->ky;
erase(rt->c[], t->ky);
}
}
if (rt) rt->sz = (rt->c[] ? rt->c[]->sz : ) + (rt->c[] ? rt->c[]->sz : ) + ;
}
void pre(Node *x) {
if (!x) return ;
cout << x << ' ' << x->c[] << ' ' << x->c[] << ' ' << x->ky << ' ' << x->sz << endl;
pre(x->c[]);
pre(x->c[]);
}
void erase(int k) { erase(RT, k);}
int find(Node *rt, int k) {
if (!rt) return ;
int ret = ;
if (k > rt->ky) ret = (rt->c[] ? rt->c[]->sz : ) + find(rt->c[], k) + ;
else ret = find(rt->c[], k);
return ret;
}
int lower_bound(int k) { return find(RT, k);}
} trp[N << ]; int pos[N], rec[N], ori[N];
void build(int l, int r, int rt) {
if (l == r) {
trp[rt].make(rec, l, r);
pos[l] = rt;
return ;
}
int m = l + r >> ;
build(lson);
build(rson);
sort(rec + l, rec + r + );
trp[rt].make(rec, l, r);
} void insert(int p, int x, int d) {
if (p <= ) return ;
trp[p].erase(d);
trp[p].insert(x);
insert(p >> , x, d);
} int query(int L, int R, int x, int l, int r, int rt) {
if (L <= l && r <= R) return trp[rt].lower_bound(x);
int m = l + r >> , ret = ;
if (L <= m) ret += query(L, R, x, lson);
if (m < R) ret += query(L, R, x, rson);
return ret;
} void scan(int &x) {
char ch;
while (!isdigit(ch = getchar())) ;
x = ch - '';
while (isdigit(ch = getchar())) x = x * + ch - '';
} int main() {
//freopen("in", "r", stdin);
int n, m, u;
while (~scanf("%d%d%d", &n, &m, &u)) {
init();
for (int i = ; i <= n; i++) {
scan(rec[i]);
ori[i] = rec[i];
}
build(root);
int L, R, v, p;
while (m--) {
scan(L), scan(R), scan(v), scan(p);
int k = query(L, R, v, root);
k = (LL) u * k / (R - L + );
insert(pos[p], k, ori[p]);
ori[p] = k;
}
for (int i = ; i <= n; i++) printf("%d\n", ori[i]);
}
return ;
}
——written by Lyon