首页 > 代码库 > HYSBZ 1901 Dynamic Rankings 树状数组套主席树
HYSBZ 1901 Dynamic Rankings 树状数组套主席树
ZOJ上面这题内存限制太严格,裸的树套树主席树搞法过不去,BZOJ上面这个放的比较松,可以过。
其实就是利用树状数组维护n颗主席树,然后利用前缀和性质求解第k大。
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional> using namespace std; #define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int, int> PII;typedef pair<double, double> PDD;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 5e4 + 10;const int maxm = maxn * 67;const int maxq = 1e4 + 10;struct Query { char cmd; int l, r, k; Query(char cmd = 0, int l = 0, int r = 0, int k = 0): cmd(cmd), l(l), r(r), k(k) {}};int sumv[maxm], lc[maxm], rc[maxm], cnt, C[maxn];int n, m, num[maxn + maxq], numcnt, a[maxn];Query ask[maxq];int lowbit(int x) { return x & (-x);}void init() { cnt = numcnt = 0; memset(C, 0, sizeof(C));}void build(int rt, int l, int r) { sumv[rt] = 0; if(l == r) return; int mid = (l + r) >> 1; lc[rt] = cnt++; rc[rt] = cnt++; build(lc[rt], l, mid); build(rc[rt], mid + 1, r);}int update(int prt, int pos, int Val) { int nrt = cnt++, ret = nrt; sumv[nrt] = sumv[prt] + Val; int l = 0, r = numcnt - 1; while(l < r) { int mid = (l + r) >> 1; if(pos <= mid) { lc[nrt] = cnt++; rc[nrt] = rc[prt]; sumv[lc[nrt]] = sumv[lc[prt]] + Val; nrt = lc[nrt]; prt = lc[prt]; r = mid; } else { rc[nrt] = cnt++; lc[nrt] = lc[prt]; sumv[rc[nrt]] = sumv[rc[prt]] + Val; nrt = rc[nrt]; prt = rc[prt]; l = mid + 1; } } return ret;}void gao(int tid, int pos, int Val) { while(tid <= n) { int ret = update(C[tid], pos, Val); C[tid] = ret; tid += lowbit(tid); }}int lrt[maxn], rrt[maxn];int query(int ql, int qr, int k) { int lcnt = 0, rcnt = 0; ql--; while(ql > 0) { lrt[lcnt++] = C[ql]; ql -= lowbit(ql); } while(qr > 0) { rrt[rcnt++] = C[qr]; qr -= lowbit(qr); } int l = 0, r = numcnt - 1; while(l < r) { int mid = (l + r) >> 1, lsum = 0, rsum = 0; for(int i = 0; i < lcnt; i++) lsum += sumv[lc[lrt[i]]]; for(int i = 0; i < rcnt; i++) rsum += sumv[lc[rrt[i]]]; if(rsum - lsum >= k) { r = mid; for(int i = 0; i < lcnt; i++) lrt[i] = lc[lrt[i]]; for(int i = 0; i < rcnt; i++) rrt[i] = lc[rrt[i]]; } else { l = mid + 1; k -= (rsum - lsum); for(int i = 0; i < lcnt; i++) lrt[i] = rc[lrt[i]]; for(int i = 0; i < rcnt; i++) rrt[i] = rc[rrt[i]]; } } return l;}int getid(int Val) { return lower_bound(num, num + numcnt, Val) - num;}int main() { init(); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); num[numcnt++] = a[i]; } char cmd[5]; int l, r, k; for(int i = 1; i <= m; i++) { scanf("%s", cmd); if(cmd[0] == ‘Q‘) { scanf("%d%d%d", &l, &r, &k); ask[i] = Query(cmd[0], l, r, k); } else { scanf("%d%d", &l, &k); ask[i] = Query(cmd[0], l, 0, k); num[numcnt++] = k; } } sort(num, num + numcnt); numcnt = unique(num, num + numcnt) - num; build(0, 0, numcnt - 1); for(int i = 1; i <= n; i++) { gao(i, getid(a[i]), 1); } for(int i = 1; i <= m; i++) { if(ask[i].cmd == ‘Q‘) printf("%d\n", num[query(ask[i].l, ask[i].r, ask[i].k)]); else { int prev = getid(a[ask[i].l]), now = getid(ask[i].k); a[ask[i].l] = ask[i].k; gao(ask[i].l , prev, -1); gao(ask[i].l, now, 1); } } return 0;}
HYSBZ 1901 Dynamic Rankings 树状数组套主席树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。