CF702F T-Shirts(平衡树)

CF702F T-Shirts(平衡树)

题目大意

有 (n) 种T恤，每种有价格 (c_i) 和品质 (q_i)。

有 (m) 个人要买 (T) 恤，第 (i) 个人有 (v_i) 元，每人每次都会买一件能买得起的 (q_i) 最大的T恤。一个人只能买一种T恤一件，所有人之间都是独立的。

问最后每个人买了多少件 (T) 恤？如果有多个 (q_i) 最大的T恤，会从价格低的开始买。

数据范围

$ 1le nle 2·10^{5} $

$ 1le c_{i},q_{i} le 10^{9} $

(1le m le 2·10^{5})

解题思路

思维题

考虑两种暴力

第一种是一个一个人扫一遍，没什么好办法优化

第二种是所有人一起，碰到一个新T恤就把能买的人都买

你思考是否可以用平衡树解决这个问题，在当前这颗树中，将小于价格的保留，大于价格的都减去价格

不妨设价格为 c

但是减去 c 之后相对顺序将被打乱，使用 fhq 的话也要求右边的最小值一定要大于左边的最大值

如果暴力将右边小于左边最大值的数暴力插过去可行吗

答案是肯定的

考虑什么样的数会被暴力插，大于 (2c) 的数减 c 仍然大于左边，而在 (c, 2c) 之间的数才会暴力，不难发现这样的数减 c 之后数值至少缩小一半，也就是说所有的数最多会被暴力插 (log N) 次

总复杂度 (Theta(NlogN))

代码（竟然写完没调一遍过了，且常数较小

#define ls son[x][0]
#define rs son[x][1]
const int N = 200500;
int tag[N], val[N], rnd[N], son[N][2], add[N], ans[N], cnt;
int build(int x) {
	val[++cnt] = x, rnd[cnt] = rand();
	return cnt; 
}

void spread(int x) {
	if (tag[x]) {
		if (ls) tag[ls] += tag[x], ans[ls] += tag[x];
		if (rs) tag[rs] += tag[x], ans[rs] += tag[x];
		tag[x] = 0;
	}
	if (add[x]) {
		if (ls) add[ls] += add[x], val[ls] += add[x];
		if (rs) add[rs] += add[x], val[rs] += add[x];
		add[x] = 0;
	}
}

void split(int nw, int k, int &x, int &y) {
	if (!nw) return x = y = 0, void();
	spread(nw);
	if (val[nw] <= k) x = nw, split(rs, k, rs, y);
	else y = nw, split(son[y][0], k, x, son[y][0]);
}

int getmx(int rt) {
	while (son[rt][1]) 
		spread(rt), rt = son[rt][1];
	return val[rt];
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (rnd[x] < rnd[y]) return spread(x), rs = merge(rs, y), x;
	return spread(y), son[y][0] = merge(x, son[y][0]), y;
}

void insert(int &rt, int k) {
	int x, y;
	split(rt, val[k], x, y);
	rt = merge(merge(x, k), y);
}

struct node {
	int c, q;
	bool operator < (const node &i) const {
		if (q != i.q) return q > i.q;
		return c < i.c;
	}
}t[N];

int f[N], b[N], m, n;
bool cmp(int a, int y) {
	return b[a] < b[y];
}

void rebuild(int nw, int &rt) {
	if (!nw) return;
	spread(nw);
	rebuild(son[nw][0], rt);
	rebuild(son[nw][1], rt);
	son[nw][0] = son[nw][1] = 0;
	insert(rt, nw);
}

void spreadit(int x) {
	if (!x) return;
	spread(x);
	spreadit(ls), spreadit(rs);
}

int rt;
int main() {
	read(m);
	for (int i = 1;i <= m; i++) 
		read(t[i].c), read(t[i].q);
	sort(t + 1, t + m + 1);
	read(n);
	for (int i = 1;i <= n; i++) 
		read(b[f[i] = i]), build(b[i]);
	sort(f + 1, f + n + 1, cmp);
	for (int i = 1;i <= n; i++) 
		rt = merge(rt, f[i]);
	for (int i = 1;i <= m; i++) {
		int x, y, z;
		split(rt, t[i].c - 1, x, y);
		if (!y) { rt = x; continue; }
		val[y] -= t[i].c, ans[y]++;
		add[y] -= t[i].c, tag[y]++;
		int mx = getmx(x);
		split(y, mx - 1, z, y);
		rebuild(z, x), rt = merge(x, y);
	}
	spreadit(rt);
	for (int i = 1;i <= n; i++) write(ans[i]);
	return 0;
}