以各种方式出现被玩烂的题目,算是小 trick 题?
cp editor 意外地好用
思路
可并堆。
平行时空同位体:CF13C P4331 P4597 CF713C P2893
已知做法:
-
\(O(n ^ 2)\) dp:令 \(f[i][j]\) 为前 \(i\) 个数不超过 \(j\) 的最小代价
-
优化:使用堆维护 dp 产生的折线(P4597 题解区)
-
\(O(n \log n)\):可并堆
结论:\(b\) 序列中的数均为 \(a\) 序列中的数
关于可并堆做法,先考虑 \(b\) 单调不降而非严格递增的弱化版。
注意到两个比较直接的结论:
-
当 \(a\) 单调不降时,\(b = a\).
-
当 \(a\) 单调不增时,\(b\) 均为 \(a\) 的中位数。
又因为 \(a\) 可以分成若干段单调不增的区间,所以可以考虑将这些区间设置为其中位数,然后再调整不满足严格递增的位置。
调整其实就是把两个区间合并成一个区间,然后再用这个区间的中位数填充。
这个过程可以考虑维护增量,动态合并区间 + 求区间最值可以考虑用可并堆实现。
至于单调不降变严格递增是一个小 trick:给每个位置加上 / 减去下标就可以转化限制了。
时间复杂度 \(O(n \log n)\)。
代码
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
struct item
{
int rt, l, r, sz, val;
} seq[maxn];
int n;
int a[maxn];
int ls[maxn], rs[maxn], dis[maxn];
int merge(int x, int y)
{
if ((!x) || (!y)) return x | y;
if (a[x] < a[y]) swap(x, y);
rs[x] = merge(rs[x], y);
if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
dis[x] = dis[rs[x]] + 1;
return x;
}
int del(int x) { return merge(ls[x], rs[x]); }
int main()
{
scanf("%d", &n);
dis[0] = -1;
int len = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]), a[i] -= i;
seq[++len] = (item){i, i, i, 1, a[i]};
while ((len > 1) && (seq[len - 1].val > seq[len].val))
{
len--;
seq[len].rt = merge(seq[len].rt, seq[len + 1].rt);
seq[len].sz += seq[len + 1].sz, seq[len].r = seq[len + 1].r;
while (seq[len].sz > (seq[len].r - seq[len].l + 2) / 2) seq[len].sz--, seq[len].rt = del(seq[len].rt);
seq[len].val = a[seq[len].rt];
}
}
int cur = 1; ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (seq[cur].r < i) cur++;
ans += abs(seq[cur].val - a[i]);
}
printf("%lld\n", ans);
cur = 1;
for (int i = 1; i <= n; i++)
{
if (seq[cur].r < i) cur++;
printf("%d ", seq[cur].val + i);
}
return 0;
}
标签:rt,seq,Sequence,int,题解,rs,len,2004,dis
From: https://www.cnblogs.com/lingspace/p/p4597.html