首页 > 其他分享 >[CF1827F]Copium Permutation

[CF1827F]Copium Permutation

时间:2023-06-29 20:47:40浏览次数:40  
标签:lmx good int Copium lmn Permutation mx CF1827F op

吓人题。

一个显然的想法是对于 \(k\), 将贡献分为 \(3\) 类 :\([1,k]\) 子区间的贡献,\([k+1,n]\) 子区间的贡献和跨过 \(k\) 的贡献。

首先 \([1,k]\) 的贡献我们可以沿用 Pudding Monsters 的做法,从左往右枚举 \(r\),统计 \(r\) 作为右端点的贡献。发现一个区间是 Copium 的当且仅当 \(\max-\min-len=-1\),而区间内数互不相同,也就是 \(\max-\min-len\ge-1\),且左端点在 \(r\) 时一定可以取到。于是我们用线段树维护每个左端点到 \(r\) 的 \(\max-\min-len\) 的值,贡献即为最小值的个数。维护两个单调栈,在退栈的时候更新即可。

其它的贡献要涉及到重排的问题。对于 \([k+1,n]\) 位置的数,它们一定能被分成值域上的若干连续段。显然重排过后一个连续段递增/递减的放在一起会更优。\([k+1,n]\) 只与连续段有关,是容易算出的,我们只需要考虑跨过 \(k\) 的贡献。

我们称位置在 \([k+1,n]\) 中的数是特殊的。定义一个 \(good\) 数组,它内部的元素单调递增。\(i\) 在 \(good\) 数组中当且仅当 \(i \le k\) 且 \([i,k]\) 位置的数在去掉所有特殊的数之后的值域上形成了一个连续段。比如当前 \([1,k]\) 中的数为:\([1,9,2,6,8,7,5,10]\),那么 \(good=[1,2,8]\)。

考虑对于一个 \(k\) 怎么重排。我们从右往左扫描一遍当前的 \(good\) 数组。如果 \([good_i,k]\) 还不是 Copium 的,就把 \([good_i,k]\) 中缺失的数先放在前面,跨过 \(k\) 的贡献增加 \(1\)。比如 \(n=10\) 时,\([1,k]\) 的序列为 \([1,10,4,5,7,6]\),我们肯定是把序列放成 \([1,10,4,5,7,6][8,9][3,2]\) 更优秀,使得跨过 \(k\) 的贡献增加了 \(4\)。在这个例子中,我们发现,三个好的位置 \(3,4,5\) 在加入 \([8,9]\) 后都产生了贡献。我们设 \(mn_i\) 和 \(mx_i\) 表示 \([good_i,k]\) 的最大/最小值,那么如果对于 \(good\) 上的一个子段有 \(mx_i=mx_{i+1}=\dots=mx_j\) 且 \(\forall i\le x <j, [good_x, good_{x+1}-1]\) 是 Copium 的,那么它们会在同一个子段加入后产生贡献。\(mn\) 也是同理的。于是对于每个 \(mn\) 和 \(mx\) 的值,维护满足上述条件的极长段,乘上相应的连续段的长度并加入答案。

那么我们让 \(k\) 从左往右扫一遍,对于 \(mn/mx\) 相等的每个前缀存储最长的串。对于 \(good\) 数组,每次它只会弹出一个后缀,直接从后往前弹即可。我们只需要考虑新加入两个位置:\(k\) 和最后一个满足 \(a_j<a_k\) 或 \(a_j>a_k\) 的 \(j\) 之后第一个 \(good\) 且必须满足它是 \(mn/mx\) 连续段中最后一个位置。

#include <bits/stdc++.h>
#include <functional>

using namespace std; 

typedef long long ll;

const int N = 1e6 + 5;

inline int read() {
	register int s = 0;
	register char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch & 15), ch = getchar();
	return s;
}

int n, a[N], pos[N], pre[N], nxt[N], mn[N], mx[N], tpn = 0, tpx = 0;
set<int> st;
vector<int> good;
long long res[N], mid = 0, suf = 0;

#define SIT set<int>::iterator
#define VIT vector<int>::iterator

struct node {
	int cur, mx, op;
	inline node() { }
	inline node(int C, int M, int O) : cur(C), mx(max(C, M)), op(O) { }
} lmn[N], lmx[N];

inline int qmin(int x) {
	return a[*lower_bound(mn + 1, mn + tpn + 1, x)];
}

inline int qmax(int x) {
	return a[*lower_bound(mx + 1, mx + tpx + 1, x)];
}

class RMQ {
	int mn[N][20];
	
public :
	inline void build() {
		for (int i = 1; i <= n; ++i) mn[i][0] = pos[i];
		for (int i = 1; i < 20; ++i)
			for (int j = 1; j + (1 << i) - 1 <= n; ++j)
				mn[j][i] = min(mn[j][i - 1], mn[j + (1 << i - 1)][i - 1]);
	}
	
	inline int query(int l, int r) {
		int t = __lg(r - l + 1);
		return min(mn[l][t], mn[r - (1 << t) + 1][t]);
	}
} rmq;

namespace PREF { 

int mn[N << 2], tag[N << 2], cnt[N << 2];

inline void update(int now) {
	mn[now] = min(mn[now << 1], mn[now << 1 | 1]);
	cnt[now] = 0;
	if (mn[now] == mn[now << 1]) cnt[now] += cnt[now << 1];
	if (mn[now] == mn[now << 1 | 1]) cnt[now] += cnt[now << 1 | 1];
}

inline void pushdown(int now) {
	if (!tag[now]) return ;
	tag[now << 1] += tag[now]; tag[now << 1 | 1] += tag[now];
	mn[now << 1] += tag[now]; mn[now << 1 | 1] += tag[now];
	tag[now] = 0;
}

inline void modify(int now, int l, int r, int ql, int qr, int k) {
	if (ql <= l && r <= qr) {
		tag[now] += k; mn[now] += k;
		return ;
	} pushdown(now);
	int mid = l + r >> 1;
	if (ql <= mid) modify(now << 1, l, mid, ql, qr, k);
	if (qr > mid) modify(now << 1 | 1, mid + 1, r, ql, qr, k);
	update(now);
}

inline int query(int now, int l, int r, int ql, int qr) {
	pushdown(now);
	if (ql <= l && r <= qr) return mn[now] == 0 ? cnt[now] : 0;
	int mid = l + r >> 1, ret = 0;
	if (ql <= mid) ret += query(now << 1, l, mid, ql, qr);
	if (qr > mid) ret += query(now << 1 | 1, mid + 1, r, ql, qr);
	return ret;
}

inline void build(int now, int l, int r) {
	tag[now] = 0;
	if (l >= r) {
		mn[now] = l; cnt[now] = 1;
		return ;
	} build(now << 1, l, l + r >> 1);
	build(now << 1 | 1, (l + r >> 1) + 1, r);
	mn[now] = mn[now << 1]; cnt[now] = cnt[now << 1];
	return ;
}

int stk1[N], top1 = 0, stk2[N], top2 = 0;

void calc() {
	build(1, 1, n); top1 = top2 = 0;
	for (int i = 1; i <= n; ++i) {
		res[i] = 0;
		modify(1, 1, n, 1, n, -1);
		while (top1 && a[stk1[top1]] < a[i]) {
			modify(1, 1, n, stk1[top1 - 1] + 1, stk1[top1], a[i] - a[stk1[top1]]);
			--top1;
		} stk1[++top1] = i;
		while (top2 && a[stk2[top2]] > a[i]) {
			modify(1, 1, n, stk2[top2 - 1] + 1, stk2[top2], a[stk2[top2]] - a[i]);
			--top2;
		} stk2[++top2] = i;
		res[i] = res[i - 1] + query(1, 1, n, 1, i);
	}
}

}

int main() {
	int T = read();
	auto link = [](int x, int y) { nxt[x] = y; pre[y] = x; };
	auto calc = [](int i, int j, bool fl) {
		int xi = qmax(i), xj = qmax(j), ni = qmin(i), nj = qmin(j);
		if (fl) {
			mid -= 1ll * lmx[j].mx * (nxt[xj] - xj - 1);
			mid -= 1ll * lmn[j].mx * (nj - pre[nj] - 1);
		}
		if (xi == xj) {
			if (!fl) mid -= 1ll * lmx[i].mx * (nxt[xi] - xi - 1);
			int op;
			if (nj - ni == j - i) op = 0;
			else if (pre[nj] + 1 - ni == j - i) op = 1;
			else op = 2;
			if (op == 2) lmx[j] = node(1, lmx[i].mx, 2);
			else if (!lmx[i].op) lmx[j] = node(lmx[i].cur + 1, lmx[i].mx, op);
			else lmx[j] = node(2, lmx[i].mx, op);
		} else lmx[j] = node(1, 1, 3);
		if (ni == nj) {
			if (!fl) mid -= 1ll * lmn[i].mx * (ni - pre[ni] - 1);
			int op;
			if (xi - xj == j - i) op = 0;
			else if (xi + 1 - nxt[xj] == j - i) op = 1;
			else op = 2;
			if (op == 2) lmn[j] = node(1, lmn[i].mx, 2);
			else if (!lmn[i].op) lmn[j] = node(lmn[i].cur + 1, lmn[i].mx, op);
			else lmn[j] = node(2, lmn[i].mx, op);
		} else lmn[j] = node(1, 1, 3);
		mid += 1ll * lmx[j].mx * (nxt[xj] - xj - 1);
		mid += 1ll * lmn[j].mx * (nj - pre[nj] - 1);
	};
	while (T--) {
		n = read();
		for (int i = 1; i <= n; ++i) pos[a[i] = read()] = i, pre[i] = nxt[i] = 0, lmx[i] = lmn[i] = node(0, 0, 0);
		PREF :: calc();
		tpn = tpx = 0; good.clear(); st.clear();
		mn[++tpn] = 0; mx[++tpx] = 0; st.insert(0); st.insert(n + 1);
		rmq.build(); pre[n] = 0; nxt[0] = n;
		printf("%lld ", suf = 1ll * n * (n + 1) / 2); mid = 0;
		for (int i = 1; i <= n; ++i) {
			while (!good.empty()) {
				int r = *good.rbegin();
				int np = qmin(r), xp = qmax(r);
				if (rmq.query(min(np, a[i]), max(xp, a[i])) >= r) break;
				mid -= 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
				mid -= 1ll * lmn[r].mx * (np - pre[np] - 1);
				good.pop_back();
				if (!good.empty()) {
					if (lmx[r].op < 3)
						mid += 1ll * lmx[*good.rbegin()].mx * (nxt[xp] - xp - 1);
					if (lmn[r].op < 3)
						mid += 1ll * lmn[*good.rbegin()].mx * (np - pre[np] - 1); 
				}
			}
			if (!good.empty()) {
				int r = *good.rbegin();
				int np = qmin(r), xp = qmax(r);
				mid -= 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
				mid -= 1ll * lmn[r].mx * (np - pre[np] - 1);
			} SIT it = st.upper_bound(a[i]); suf -= 1ll * (*it - a[i]) * (a[i] - *prev(it));
			link(*prev(it), a[i]); link(a[i], *it); st.insert(a[i]);
			while (tpx >= 2 && a[mx[tpx]] < a[i]) --tpx;
			while (tpn >= 2 && a[mn[tpn]] > a[i]) --tpn;
			mx[++tpx] = i; mn[++tpn] = i;
			if (!good.empty()) {
				int r = *good.rbegin();
				int np = qmin(r), xp = qmax(r);
				mid += 1ll * lmx[r].mx * (nxt[xp] - xp - 1);
				mid += 1ll * lmn[r].mx * (np - pre[np] - 1);
				calc(r, i, 0);
			} else {
				lmx[i] = lmn[i] = node(1, 1, 3);
				mid += nxt[a[i]] - pre[a[i]] - 2;
			} good.push_back(i);
			if (tpn >= 2) {
				VIT it = upper_bound(good.begin(), good.end(), mn[tpn - 1]);
				if (it != good.begin() && it != good.end()) {
					int x = *it; int y = *(--it);
					calc(y, x, 1);
				}
			}
			if (tpx >= 2) {
				VIT it = upper_bound(good.begin(), good.end(), mx[tpx - 1]);
				if (it != good.begin() && it != good.end()) {
					int x = *it; int y = *(--it);
					calc(y, x, 1);
				}
			}
			printf("%lld ", res[i - 1] + good.size() + mid + suf);
		} puts(""); 
	} return 0;
} 

标签:lmx,good,int,Copium,lmn,Permutation,mx,CF1827F,op
From: https://www.cnblogs.com/wwlwakioi/p/17515145.html

相关文章

  • 【每日一题】Problem 359B. Permutation
    原题解决思路虽然题解思路里写着\(dp\),但是还是用最简单的\(math\)方法写了找规律题:如果结果为\(0\),只需要每个\(a_{2i-1}-a_{i}\)同向即可,即都为整数或负数如果结果为\(2k\),则只需要任意一个\(|a_{2i-1}-a_{i}|\)的值为\(k\),且与其他的\(a_{2i-1}-a_{i}\)方向......
  • [ABC299G]MinimumPermutation
    [ABC299G]MinimumPermutation考虑一个必要的性质:如果现在有一个数\(x_1\),它后面有一个数\(y<x_1\),且\(x_1\)又在\(y\)后面出现了若干次(\(x_2,x_3,\dots,x_k\),我们直接考虑最后一个\(x_k\)),那么\(x1\)一定不是答案。(显然前面的\(x_1\)可以不选,然后选择\(y,x_2\simx_......
  • ARC114F Permutation Division
    题意给定一个\(1\simN\)的排列,Alice把它划分成\(k\)段,Bob把这\(k\)段任意排列。Alice想让字典序最小,Bob想让字典序最大。请问最后的排列。数据范围:\(1\lek\leN\le2\times10^5\)。题解首先Bob的排序只取决于每个段第一个数的大小。字典序不会变小,所以考虑......
  • AtCoder Regular Contest 141 C Bracket and Permutation
    洛谷传送门AtCoder传送门考虑给出\(S\),如何求\(P,Q\)。先考虑\(P\),那我们肯定想让\(P\)的每一项都尽量往前靠。设\([1,k]\)为合法括号串,\(S_{k+1}=\texttt{)}\),那\(P\)的前\(k\)项依次为\(1\simk\),第\(k+1\)项不能为\(k+1\)了,那找到\(k+1\)之......
  • Educational Codeforces Round 7-D. Optimal Number Permutation
    原题链接D.OptimalNumberPermutationtimelimitpertestmemorylimitpertestinputoutputYouhavearray a thatcontainsallintegersfrom 1 to n twice.Youcanarbi......
  • AtCoder Beginner Contest 214 G Three Permutations
    洛谷传送门AtCoder传送门比较平凡的一个容斥。考虑把问题转化成,求\(\foralli\in[1,n],r_i\nei\landr_i\nep_i\)的\(r\)方案数。考虑到不弱于错排,所以容斥。设钦定\(i\)个\(r_i\)取了\(i,p_i\)中的一个的方案数为\(f_i\),其余任意,那么:\[ans=\sum\limi......
  • next_permutation函数
    next_permutation的函数声明:#include <algorithm> boolnext_permutation(iteratorstart,iteratorend);next_permutation函数的返回值是布尔类型,在STL中还有perv_permutation()函数 #include<iostream>#include<algorithm>#include<string>usingnamespacest......
  • Permutation Invariant Graph Generation via Score-Based Generative Modeling
    目录概符号说明本文方法代码NiuC.,SongY.,SongJ.,ZhaoS.,GroverA.andErmonS.Permutationinvariantgraphgenerationviascore-basedgenerativemodeling.AISTATS,2020.概本文利用diffusion进行图的生成,很朴素.符号说明\(\mathbf{A}^{\pi}\),邻接......
  • SP15637 Mr Youngs Picture Permutations 题解
    题意给定一个最多有\(5\)排的一个队伍,每一个位置对应一个同学,给定总人数和第\(i\)排要站\(n_i\)个人。要求每行左边的同学身高要大于右边的,每列从上往下要从大到小。问:满足要求的一共有多少种方案。思路DP首先考虑,在这个题目中,有用的状态有每列最后的人的高度,每行......
  • TheForces Round #13 (Boombastic-Forces) G. Permutation Removal
    感觉好久没有写过这样单独一篇题目的博客了的说昨天上大物课的时候ztc问了我这道题,然后我口胡了下感觉还挺有趣的不过其它题目就没啥时间看了,正巧最近在练DP专题,就顺手记录一下吧这题的数据范围和问题一眼区间DP的形式,直接设\(f_{l,r}\)表示区间\([l,r]\)的答案刚开始naive地......