526互联

2023 年 CCPC 网络预选赛 L.Partially Free Meal （主席树）

发布时间 2023-10-27 09:15:12作者: qdhys

传送门

先插个图玩云顶之弈。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
#define ll long long
#define fs first
#define se second

const long double eps = 1e-9;
const int N = 2e5 + 10, M = 2e5 + 10;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n , m, _;

std::vector<int> nums;

struct node{
	int l, r, cnt;
	ll sum;
}tr[N * 21];
/
struct Historical_Segment_Tree{
	int idx;
	int root[N];
	
	inline int build(int l, int r){
		int q = ++ idx;
		if(l == r)	return q;
		int mid = l + r >> 1;
		tr[q].l = build(l, mid);//存的是左儿子的编号并非边界
		tr[q].r = build(mid + 1, r);
		return q;
	}

	inline int insert(int p, int l, int r, int x, int sum){//需要用到的上一个版本root[i - 1](返回的值是当前版本的root)
		int q = ++ idx;
		tr[q] = tr[p];//复制上一个节点的信息
		if(l == r){
			tr[q].cnt += sum;//新版本的信息加1
			tr[q].sum += nums[x];
			return q;
		}
		int mid = l + r >> 1;
		if(x <= mid)	tr[q].l = insert(tr[p].l, l, mid, x, sum);//在左子树则需要更新信息，否则保留原本信息就可以
		else tr[q].r = insert(tr[p].r, mid + 1, r, x, sum);
		tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
		tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
		return q;
	}

	inline int query(int p, int q, int L, int R, int l, int r){
		if(L >= l && R <= r)	return tr[q].cnt - tr[p].cnt;
		int mid = L + R >> 1;
		int cnt = 0;
		if(l <= mid)	cnt += query(tr[p].l, tr[q].l, L, mid, l, r);
		if(r > mid)		cnt += query(tr[p].r, tr[q].r, mid + 1, R, l, r);
		return cnt;
	}

	inline ll query(int p, int q, int l, int r, int k){//区间k小
		if(l == r)		return 1ll * nums[l] * k;
		int mid = l + r >> 1;
		int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
		if(cnt >= k)	return query(tr[p].l, tr[q].l, l, mid, k);
		return tr[tr[q].l].sum + query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
	}
}HST;

struct NODE {
	int a, b;
	
	bool operator < (const NODE &x) const {
		return this->b < x.b;
	}
}t[N];

ll ans[N];
auto &root = HST.root;
inline void Solution(int xl, int xr, int yl,int yr) {
	if (xl > xr) return ;
	int mid = xl + xr >> 1;
	int tmp = 0;
	ll tans = INF;
	for (int i = std::max(mid, yl); i <= yr; i ++) {
		ll now = HST.query(root[0], root[i], 0, nums.size() - 1, mid);
		now += t[i].b;
		if (now < tans) {
			tans = now;
			tmp = i;
		}
	}
	ans[mid] = tans;
	Solution(xl, mid - 1, yl, tmp), Solution(mid + 1, xr, tmp, yr);
}


inline void solve(){
	std::cin >> n;
	

	for (int i = 1; i <= n; i ++) {
		std::cin >> t[i].a >> t[i].b;
		nums.push_back(t[i].a);
	}
	
	std::sort(t + 1, t + n + 1);
	std::sort(nums.begin(), nums.end());
	
	nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

	
	root[0] = HST.build(0, nums.size() - 1);
	
	for (int i = 1; i <= n; i ++) {
		int pos = std::lower_bound(nums.begin(), nums.end(), t[i].a) - nums.begin();
		root[i] = HST.insert(root[i - 1], 0, nums.size() - 1, pos, 1);
	}
	
	Solution(1, n, 1, n);
	
	for (int i = 1; i <= n; i ++) std::cout << ans[i] << '\n';
}

signed main(void){
   	

	_ = 1;
   	//std::cin >> _;
	while(_ --)
    	solve();

    return 0;
}