60分fhq求调
查看原帖
60分fhq求调
326254
LonginusMonkey楼主2024/7/23 23:10

没有数据,问一下能不能给个一组小的数据

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define mod 1000000
const int maxn = 1e6+100;
using namespace std;

struct fhqtreap{
	int Total;
	int Rt;
	struct node{
		int key;
		int ls, rs, sz, priority;
	}Tree[maxn];
	void pushup(int idx) {
		if(idx != 0) {
			Tree[idx].sz = Tree[Tree[idx].ls].sz+Tree[Tree[idx].rs].sz+1; 
		}
	}
	int creat(int key) {
		int Rt = ++Total;
		Tree[Rt].key = key;
		Tree[Rt].sz = 1;
		Tree[Rt].ls = Tree[Rt].rs = 0;
		Tree[Rt].priority = rand();
		return Rt;
	}
	void split(int Rt, int key, int &x, int &y) {
		if (Rt == 0) {
			x = y = 0; return;
		}
		if (Tree[Rt].key <= key) {
			x = Rt;
			split(Tree[Rt].rs, key, Tree[Rt].rs, y);
		} else {
			y = Rt;
			split(Tree[Rt].ls, key, x, Tree[Rt].ls);
		}
		pushup(Rt);
	}
	int merge(int x, int y) {
		if(x==0 or y==0) return x|y;
		if(Tree[x].priority > Tree[y].priority) {
			Tree[x].rs = merge(Tree[x].rs, y);
			pushup(x);
			return x;
		} else {
			Tree[y].ls = merge(x, Tree[y].ls);
			pushup(y);
			return y;
		}
	}
	void insert(int key) {
		int x, y;
		split(Rt, key-1, x, y);
		Rt = merge(merge(x, creat(key)),y);
	}
	int findmax(int idx) {
		if(Tree[idx].rs) {
			return findmax(Tree[idx].rs);
		}
		return Tree[idx].key;
	}
	int findmin(int idx) {
		if(Tree[idx].ls) {
			return findmax(Tree[idx].ls);
		}
		return Tree[idx].key;
	}
	int Lowerbound(int idx, int key) {
		if(Tree[idx].key >= key) {
			if(!Tree[idx].ls) return Tree[idx].key;
			return min(Lowerbound(Tree[idx].ls, key), Tree[idx].key);
		} else {
			if(!Tree[idx].rs) return inf;
			return Lowerbound(Tree[idx].rs, key);
		}
	}
	int lowerbound(int key) {
		return Lowerbound(Rt, key);
	}
	void del(int key) {
		int T1, T2, T3;
		split(Rt, key, T1, T2);
		split(T1, key-1, T1, T3);
		Rt = merge(T1, T2);
	}
	int rk(int key) {
		int T1, T2;
		split(Rt, key, T1, T2);
		int k = Tree[T1].sz;
		Rt = merge(T1, T2);
		return k+1;
	}
};

fhqtreap fhq;

int n, now, big;

int ans = 0;

void work(int x) {
	if(x >= fhq.findmax(fhq.Rt)) {
		ans += x - fhq.findmax(fhq.Rt);
		fhq.del(fhq.findmax(fhq.Rt));
	} else if(x <= fhq.findmin(fhq.Rt)){
		ans += fhq.findmin(fhq.Rt) - x;
		fhq.del(fhq.findmin(fhq.Rt));
	} else {
		int a = fhq.lowerbound(x);
		int b = x - (a - x);
		int c = fhq.lowerbound(b);
		if(c >= x) {
			ans += c - x;
			fhq.del(c);
		} else {
			if(x - c <= a - x) {
				ans += x-c;
				fhq.del(c);
			} else {
				ans += a-x;
				fhq.del(a);
			}
		}
	}
}

signed main() {
	srand(time(0));
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; ++i) {
		int bl, x; cin >> bl >> x;
		if(big == 0) {
			now = bl; fhq.insert(x); ++ big; 
		} else {
			if(now == bl) {
				fhq.insert(x); ++ big;
			} else {
				work(x); -- big;
			}
		}
	}
	cout << ans % mod;
	return 0;
} 
2024/7/23 23:10
加载中...