专栏文章

题解：P10764 [BalticOI 2024] Wall

FFelix72
P10764题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqa1jq2
此快照首次捕获于
2025/12/04 01:24
3 个月前
此快照最后确认于
2025/12/04 01:24
3 个月前
查看原文
硬拆 22 的次幂的做法很不友好，我来个好想好写的做法。
对于 hh 序列固定的情况，答案是 ∑i=1nmin⁡(pri,sui)−hi=pri+sui−global−hi\sum_{i = 1}^{n} \min(pr_i, su_i) - h_i = pr_i + su_i - global - h_i。其中 pr,supr, su 是前缀、后缀最大值，globalglobal 是全局最大值。
思考直接求出所有情况的 ∑pr,∑su,∑global,∑h\sum pr, \sum su, \sum global, \sum h。
思考一个 DP 状态 fi,xf_{i, x} 表示考虑前 ii 个元素，其 max⁡h=x\max h = x 的方案数。∑i=1n2n−i∑xfi,x\sum_{i = 1}^{n}2^{n - i}\sum xf_{i, x} 就是 ∑pr\sum pr。枚举 ii，把 ff 挂在线段树上维护；∑su\sum su 同理；∑global\sum global 考虑 xfn,xxf_{n, x} 的和；∑h\sum h 等于 ∑h2n−1\sum h2^{n - 1}。
因此写一个线段树优化 DP，把系数放进线段树里算就可以了。
CPP
/* Good Game, Well Play. */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 500010, mod = 1e9 + 7;
inline void Plus(long long &now, long long add)
{now += add; while(now >= mod) now -= mod;}
int n, h[2][N]; long long pw[N];

struct Disc {int id, pos; long long val;} disc[N * 2]; int dn;
inline bool cmp_disc(Disc u, Disc v) {return u.val < v.val;}

int rt, idx;
struct SGT
{
	int ls, rs;
	long long cnt, sum, tmp, mul;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define cnt(x) tree[x].cnt
	#define sum(x) tree[x].sum
	#define tmp(x) tree[x].tmp
	#define mul(x) tree[x].mul
} tree[N * 4];
inline void pushup(int now)
{
	cnt(now) = (cnt(ls(now)) + cnt(rs(now))) % mod;
	sum(now) = (sum(ls(now)) + sum(rs(now))) % mod;
}
inline void push_mul(int now, long long tg)
{
	cnt(now) = cnt(now) * tg % mod;
	sum(now) = sum(now) * tg % mod;
	mul(now) = mul(now) * tg % mod;
}
inline void pushdown(int now)
{
	if(mul(now) != 1)
	{
		push_mul(ls(now), mul(now));
		push_mul(rs(now), mul(now));
		mul(now) = 1;
	}
}
inline void build(int &now, int l, int r)
{
	now = ++idx; mul(now) = 1;
	if(l == r) {tmp(now) = disc[l].val; return ;}
	int mid = (l + r) >> 1;
	build(ls(now), l, mid), build(rs(now), mid + 1, r);
	tmp(now) = (tmp(ls(now)) + tmp(rs(now))) % mod;
}
inline void range_mul(int now, int l, int r, int L, int R, long long num)
{
	if(L > R) return ;
	if(L <= l && r <= R) {push_mul(now, num); return ;}
	pushdown(now); int mid = (l + r) >> 1;
	if(L <= mid) range_mul(ls(now), l, mid, L, R, num);
	if(mid < R) range_mul(rs(now), mid + 1, r, L, R, num);
	pushup(now);
}
inline void single_add(int now, int l, int r, int pos, int num)
{
	if(l == r)
	{
		cnt(now) = (cnt(now) + num) % mod;
		sum(now) = (sum(now) + tmp(now) * num) % mod;
		return ;
	}
	pushdown(now); int mid = (l + r) >> 1;
	if(pos <= mid) single_add(ls(now), l, mid, pos, num);
	else single_add(rs(now), mid + 1, r, pos, num);
	pushup(now);
}
inline int query_cnt(int now, int l, int r, int L, int R)
{
	if(L > R) return 0;
	if(L <= l && r <= R) return cnt(now);
	pushdown(now); int mid = (l + r) >> 1;
	if(R <= mid) return query_cnt(ls(now), l, mid, L, R);
	else if(mid < L) return query_cnt(rs(now), mid + 1, r, L, R);
	else return (query_cnt(ls(now), l, mid, L, R) + query_cnt(rs(now), mid + 1, r, L, R)) % mod;
}

long long LN, RN, GLOBAL, SELF;

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 0; i <= 1; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> h[i][j], disc[++dn] = {i, j, h[i][j]};
	sort(disc + 1, disc + dn + 1, cmp_disc);
	for(int i = 1; i <= dn; ++i) h[disc[i].id][disc[i].pos] = i;
	pw[0] = 1; for(int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2 % mod;
	
	build(rt, 1, 2 * n);
	single_add(rt, 1, 2 * n, h[0][1], 1);
	single_add(rt, 1, 2 * n, h[1][1], 1);
	Plus(LN, sum(rt) * pw[n - 1] % mod);
	for(int i = 2; i <= n; ++i)
	{
		int p_min = min(h[0][i], h[1][i]), p_max = max(h[0][i], h[1][i]);
		single_add(rt, 1, 2 * n, p_max, query_cnt(rt, 1, 2 * n, 1, p_max - 1));
		single_add(rt, 1, 2 * n, p_min, query_cnt(rt, 1, 2 * n, 1, p_min - 1));
		range_mul(rt, 1, 2 * n, 1, p_min - 1, 0);
		range_mul(rt, 1, 2 * n, p_max + 1, 2 * n, 2);
		Plus(LN, sum(rt) * pw[n - i] % mod);
	}
	push_mul(rt, 0);
	single_add(rt, 1, 2 * n, h[0][n], 1);
	single_add(rt, 1, 2 * n, h[1][n], 1);
	Plus(RN, sum(rt) * pw[n - 1] % mod);
	for(int i = n - 1; i >= 1; --i)
	{
		int p_min = min(h[0][i], h[1][i]), p_max = max(h[0][i], h[1][i]);
		single_add(rt, 1, 2 * n, p_max, query_cnt(rt, 1, 2 * n, 1, p_max - 1));
		single_add(rt, 1, 2 * n, p_min, query_cnt(rt, 1, 2 * n, 1, p_min - 1));
		range_mul(rt, 1, 2 * n, 1, p_min - 1, 0);
		range_mul(rt, 1, 2 * n, p_max + 1, 2 * n, 2);
		Plus(RN, sum(rt) * pw[i - 1] % mod);
	}
	
	for(int i = 0; i <= 1; ++i)
		for(int j = 1; j <= n; ++j)
			Plus(SELF, disc[h[i][j]].val * pw[n - 1] % mod);
	
	long long left = pw[n]; bool vis[N] = {0};
	for(int i = 2 * n, iv = (mod + 1) / 2; i >= 1; --i)
	{
		if(!vis[disc[i].pos])
		{
			left = left * iv % mod;
			Plus(GLOBAL, left * disc[i].val % mod);
			vis[disc[i].pos] = true;
		}
		else
		{
			Plus(GLOBAL, left * disc[i].val % mod);
			break;
		}
	}
	
	cout << (LN + RN - GLOBAL * n % mod - SELF + mod * 2) % mod << '\n';
	return 0;
}
/*

*/

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...