P4647 [IOI2007] sails 船帆

P4647 [IOI2007] sails 船帆

由题意可知，这个就是初始有 \(N\) 个为 \(0\) 的变量，有 \(M\) 次操作，让你在前 \(h\) 个里面选 \(k\) 个各 \(+1\)。求 \(\sum_{i=1}^N \frac {x_i \cdot (x_i-1)} 2\) 最小值。

可以发现，操作顺序对最后答案没有影响。

那么我们贪心得使得这 \(k\) 个变得更小更优秀，那么按照 \(h_i\) 排序，那就不用考虑选高处还是低处的问题。然后可以考虑平衡树，因为还需要分裂交换子树，那么考虑 FHQ-Treap。那么我们就可以线找到最小的 \(k\) 个，然后给他们打上tag，接着考虑，这些中的某些数可能大于后面的一段树，那么我还需要按照值把他们分裂后，再合并回去。假定第 \(k+1\) 个数为 \(x\) 那么就会被分成一下段数。

? 1.前 \(k\) 个加了之后小于等于 \(x\) 的。2.前 \(k\) 个加了之后大于 \(x\) 的（也就是 \(x+1\)）。3.除了前 \(k\) 个以外的值为 \(x+1\) 的。4.除了前 \(k\) 个以外的大于 \(x+1\) 的。

然后按顺序合并一下，最后dfs一下统计答案就好了。

/*
	Name:
	Author: Gensokyo_Alice
	Date:
	Description:
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
const ll MAXN = (1LL << 20) + 10;

ll N, M, root, ans, tot, c[MAXN][2];
struct nod {
	ll val, tag, siz, rd;
	nod () {val = tag = siz = rd = 0;}
	nod (ll _val, ll _tag, ll _siz, ll _rd):val(_val), tag(_tag), siz(_siz), rd(_rd) {}	
} t[MAXN];
struct que {
	ll h, k;
	friend bool operator < (que a, que b) {return a.h < b.h;}	
} q[MAXN];

void pushdown(ll);
ll get();
ll mer(ll, ll);
void split(ll, ll, ll&, ll&);
void split2(ll, ll, ll&, ll&);
void dfs(ll);
void add(ll, ll);
void pushup(ll);

int main() {
	srand(time(0));
	scanf("%lld", &N);
	for (ll i = 1; i <= N; i++) scanf("%lld%lld", &q[i].h, &q[i].k);
	sort(q+1, q+N+1);
	for (ll i = 1; i <= N; i++) {
		for (ll j = 1, k = q[i].h - q[i-1].h; j <= k; j++) {ll tem = get(); root = mer(tem, root);}
		ll x, y, z, tmp;
		split(root, q[i].k, x, y);
		add(x, 1);
		split(x, q[i].k-1, x, z);
		tmp = t[z].val;
		x = mer(x, z);
		split2(x, tmp-1, x, z);
		x = mer(x, y);
		split2(x, tmp, x, y);
		root = mer(mer(x, z), y);
	}
	dfs(root);
	printf("%lld\n", ans);
    return 0;
}

void dfs(ll n) {
	pushdown(n);
	if (c[n][0]) dfs(c[n][0]);
	ans += (t[n].val + 1) * t[n].val / 2;
	if (c[n][1]) dfs(c[n][1]);
}

ll get() {
	t[++tot] = nod(-1, 0, 1, rand());
	return tot;
}

ll mer(ll x, ll y) {
	if (!x || !y) return x | y;
	if (t[x].rd < t[y].rd) {
		pushdown(x);
		c[x][1] = mer(c[x][1], y);
		pushup(x);
		return x;
	} else {
		pushdown(y);
		c[y][0] = mer(x, c[y][0]);
		pushup(y);
		return y;
	}
}

void split(ll rt, ll k, ll &x, ll &y) {
	if (!rt) {
		x = y = 0;
		return;
	}
	pushdown(rt);
	if (t[c[rt][0]].siz < k) {
		x = rt;
		split(c[x][1], k - t[c[x][0]].siz - 1, c[x][1], y);
		pushup(x);
	} else {
		y = rt;
		split(c[y][0], k, x, c[y][0]);
		pushup(y);
	}
}

void split2(ll rt, ll k, ll &x, ll &y) {
	if (!rt) {
		x = y = 0;
		return;
	}
	pushdown(rt);
	if (t[rt].val <= k) {
		x = rt;
		split2(c[x][1], k, c[x][1], y);
		pushup(x);
	} else {
		y = rt;
		split2(c[y][0], k, x, c[y][0]);
		pushup(y);
	}
}

void pushup(ll x) {t[x].siz = t[c[x][0]].siz + t[c[x][1]].siz + 1;}

void pushdown(ll x) {
	if (!x || t[x].tag == 0) return;
	if (c[x][0]) add(c[x][0], t[x].tag);
	if (c[x][1]) add(c[x][1], t[x].tag);
	t[x].tag = 0;
}

void add(ll node, ll v) {
	t[node].tag += v;
	t[node].val += v;	
}
平衡树搜索模拟暴力

相关

Cento7 将每小时SSH暴力破解（登陆失败）超过10次的ip加入系统黑名单----系统安全篇

使用webgl(three.js)搭建一个3D智慧园区、3D建筑，3D消防模拟，web版3D,bim管理系统——第

力扣530题（二叉搜索树的最小绝对差）

noip多校模拟30

2019.11.8模拟赛

[NOIP模拟赛] 2021.11.16

快速排序与随机构建二叉搜索树

20211116 NOIP 模拟赛

项目实战：Qt+C#轨道交通行业高性能高流畅度模拟火车移动图像控件

ASP.NET Core管道深度剖析（2）：创建一个“迷你版”的管道来模拟真实管道请求处理流程

NOIP模拟99(多校31)

20210628模拟赛解题报告

标签