http://www.ifrog.cc/acm/problem/1117?contest=1016&no=1
其实我是第一次这样用线段树。
首先把所有出现过的数字全部离散化。那么数字就是从[1, 100000]了。
把他们看成一个个独立的节点。每次插入一个数字，就在那个位置加1.
那么线段树维护区间总和，想知道小于x的数字有多少个，直接区间查询[1, x - 1]即可。
如果把小于x的数，变成x，相当于把[1, x - 1]中出现了多少个数字，贡献 add 到 x这个位置，然后把[1, x - 1]清0即可。
查询第k小，可以二分然后判断。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> #define lson L, mid, cur << 1 #define rson mid + 1, R, cur << 1 | 1 const int maxn = 100000 + 20; struct Node { int op, val; }query[maxn]; vector<int>vc; set<int>ss; int sum[maxn << 2]; int add[maxn << 2]; void pushUp(int cur) { sum[cur] = sum[cur << 1] + sum[cur << 1 | 1]; } void pushDown(int cur, int total) { if (add[cur] != -inf) { add[cur << 1] = add[cur]; add[cur << 1 | 1] = add[cur]; sum[cur << 1] = sum[cur << 1 | 1] = 0; add[cur] = -inf; } } void upDate(int be, int en, int val, int L, int R, int cur) { if (be > en) return; if (L >= be && R <= en) { add[cur] = val; sum[cur] = val; return; } pushDown(cur, R - L + 1); int mid = (L + R) >> 1; if (be <= mid) upDate(be, en, val, lson); if (en > mid) upDate(be, en, val, rson); pushUp(cur); } int ask(int be, int en, int L, int R, int cur) { if (en < be) return 0; if (L >= be && R <= en) return sum[cur]; pushDown(cur, R - L + 1); int ans = 0, mid = (L + R) >> 1; if (be <= mid) ans += ask(be, en, lson); if (en > mid) ans += ask(be, en, rson); return ans; } #define root 1, n, 1 int n; int slove(int x) { //要大于多少个number int be = 1, en = n; while (be <= en) { int mid = (be + en) >> 1; int res = ask(1, mid, root); if (res >= x) en = mid - 1; else be = mid + 1; } return vc[be]; } void work() { int en = maxn << 2; for (int i = 0; i <= en - 1; ++i) add[i] = -inf; vc.push_back(-inf); int q; scanf("%d", &q); for (int i = 1; i <= q; ++i) { scanf("%d%d", &query[i].op, &query[i].val); ss.insert(query[i].val); } for (set<int> :: iterator it = ss.begin(); it != ss.end(); ++it) { vc.push_back(*it); } n = vc.size(); n--; int nowHas = 0; for (int i = 1; i <= q; ++i) { int op = query[i].op, val = query[i].val; int pos = lower_bound(vc.begin(), vc.end(), val) - vc.begin(); if (op == 1) { nowHas++; int has = ask(pos, pos, root); upDate(pos, pos, has + 1, root); } else if (op == 2) { int res = ask(1, pos, root); upDate(pos, pos, res, root); upDate(1, pos - 1, 0, root); } else if (op == 3) { int res = ask(1, n, root) - ask(1, pos, root); upDate(pos, pos, res, root); upDate(pos + 1, n, 0, root); } else if (op == 4) { printf("%d ", slove(val)); } else if (op == 5) { int res = ask(1, pos - 1, root); printf("%d ", res); } } // printf("***************** "); // printf("%d ", ask(1, 3, root)); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }