首页 > 代码库 > 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 树状数组套主席树