|
Pro4184 轻重数字 题解前言 由 zlc 和 fhx 提供的思路，orz。 貌似是 COGS 目前的最优解？（可能是其他人的常数太大了） 思路分析 先考虑一个经典的 dp，设 $f_i$ 表示将 $1\sim i$ 划分为若干好数组的方案，则有转移 $f_i=\sum f_{j-1}$，其中满足 $[j,i]$ 是一个好区间。 这样枚举 $i$，枚举 $j$，$O(n)$ 检测，就有 $O(n^3)$ 的 dp 了。注意到 $n\le 5\times 10^5$，考虑优化。 不难发现好的子数组在原数组中，要么是奇数位置为轻元素，偶数位置为重元素；要么是偶数位置为轻元素，奇数位置为重元素，所以我们分两种情况转移：分别是以 $i$ 结尾，奇数位置为轻元素和 $i$ 结尾，偶数位置为轻元素。两者本质没有区别，我们依靠前者讨论。 我们考虑区间左端点 $j$ 可以取到哪些位置，考虑对于任意 $x\in [1,i]$，元素 $x$ 对左端点 $j$ 的约束。 1. 若 $x$ 为奇数位置，作为轻元素约束 $j$。 则 $j$ 必须满足 $[lst_x+1,n]$，即对于任意 $i\in [1,n]$，只要 $j\in [lst_x+1,n]$，区间 $[j,i]$ 就可以满足 $x$ 的限制。 证明不难，当 $j\in [lst_x+1,x]$ 时，区间至多包含一个 $x$。当 $j>x$，区间一个 $x$ 都没有，自然无法约束。 容易发现，对 $j$ 的限制个数是奇数位置所有位置。 2.若 $x$ 为偶数位置，作为重元素约束 $j$ 这种情况较为复杂。 首先可以发现对 $j$ 限制个数是元素种类数，对于同一种元素，我们用这种元素在 $[1,i]$ 中最后一次出现的位置来约束 $j$。 记 $p$ 为上一个在奇数位置出现的 $x$，$q$ 为 $x$ 上一次出现的位置。当 $j\le q$ 时，$[i,j]$ 一定包含了 $q,x$，满足重元素的限制，当 $j\le p$ 时，$p$ 作为重元素出现在奇数位置，$[i,j]$ 不合法，所以 $x$ 的限制是 $j\in [q+1,p]\cup[x+1,n]$。 注意：此时是按照 $x$ 是 $[1,i]$ 最后一次出现的数，随着 $i$ 的右移，如果在偶数位置出现一个和 $x$ 一样的元素 $y$。就要先撤销 $x$ 的限制，然后加入 $y$ 的限制。 考虑如何维护满足限制的端点：维护每个位置满足限制的个数，不难维护出限制的总个数，对于一个位置，如果它足一个限制，就让他的标记数组加一。如果一个位置满足的限制个数为总个数，就说明 $[j,i]$ 是一个合法的端点。 注意一种特殊情况是 $[i,i]$ 是合法区间，我们只统计 $j\in [1,i-1]$ 的合法左端点。 直接用数组模拟是 $O(n^2)$，容易用线段树优化到 $O(n\log n)$，具体的记录每个区间任意位置满足限制个数最大值，满足限制个数达到这个最大值的 $f_{i-1}$ 之和，pushup 分讨一下即可。 然后这个问题就解决了。
题目4184 轻重数字
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 4
评论
2025-10-29 17:16:34
|
|
|
Pro4184 轻重数字 题解【题解】算法一：思路：动态规划，$dp[i]$ 是前 $i$ 个元素的有效划分方案数，则 $f[0]=1$（空数组有 $1$ 种划分方式），$f[i]$ 为所有满足 $[j+1,i]$ 是好数组的 $f[j]$ 的和。 时间复杂度：$O(n^2)$，即 $5000*5000=2.5*10^7$，期望 $15$ 分。 瓶颈：不能快速判断数组是否是好数组，不能快速累加 $f[j]$; 算法二：思路：有几处优化； $1$.对每个元素 $a[i]$，计算 $pre[i]$（上一次出现位置）和 $nxt[i]$（下一次出现位置），所以可以由好数组的性质“对于子数组内的重元素 $a[i]$，其前后出现位置必须在子数组外（否则会影响交替性）”优化判断好数组的条件； $2$.若 $j$ 在 $[L..R]$ 内时 $[j+1..i]$ 是好数组，则 $f[i]$ 需要累加 $f[L]+f[L+1]+...+f[R]$，所以用双线段树。好数组有两种起始类型（轻元素开始或重元素开始），需分别维护。因此使用两个线段树 $seg[0]$ 和 $seg[1]$，分别对应两种起始类型，每个线段树节点存储“区间内最大有效长度”和“对应方案数总和”支持区间增减（通过延迟标记）和单点更新； $3$.预先生成“区间更新事件”：当遍历到位置 $i$ 时，哪些 $j$ 的范围会因 $a[i]$ 的加入而成为有效划分点，事件按生效位置排序，遍历数组时依次触发，动态更新线段树，确保查询到的 $f[j]$ 都是有效的。 同样方式计算 $f[i]$，最终需减去重复计算的 $f[i-1]$，对 $1000003$ 取余后输出。 时间复杂度：$O(n*logn)$，即 $5*10^5*log5*10^5≈10^7$,轻松过 $4$ 秒时限； 期望得分：$100$；
题目4184 轻重数字
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
4
评论
2025-10-29 12:53:24
|
|
|
Pro4184 轻重数字 题解[CCO 2024] Heavy Light Decomposition前置知识分块，DP 简要题意定义“好的数组”为一个数组内交替出现“轻元素”和“重元素”，轻元素即其在这个数组内是唯一的，重元素即其在数组内出现多次。 有 $n$ 个正整数 $a_i$，求其有多少种划分方案能使划分后的子数组均为好的数组。 分析样例我们首先要搞懂一个东西，就是划分后好的数组，是指这个子数组是好的，在这个子数组内的轻重元素与原数组并没有关系，每个子数组是互相独立的。 对于样例一，其划分方案如下： - $[1], [2], [3], [2], [3]$ - $[1], [2, 3, 2], [3]$ - $[1], [2], [3, 2, 3]$ - $[1, 2, 3, 2], [3]$ 对于样例二，其划分方案如下： - $[1], [2], [1], [3], [1]$ - $[1, 2, 1], [3], [1]$ - $[1, 2, 1, 3], [1]$ - $[1], [2], [1, 3, 1]$ - $[1], [2, 1, 3, 1]$ - $[1, 2, 1, 3, 1]$ 不明白的建议手推一下。 思路分析考虑转移我们定义 $dp[i]$ 为前 $i$ 个元素的合法划分的方案数。 那么，转移方程很显然：$dp[i] = \sum dp[j]$，其中 $j < i$ 且 子数组 $[j + 1, i]$ 是好数组。 实际上含义就是在 $j$ 处划分，新增一个子数组 $[j + 1, i]$，方案累加前 $j$ 个元素的方案数。 考虑好数组的约束如果 $[j + 1, i]$ 为好的数组，那么需要满足： 1. 类型交替：即数组内的元素轻重交替。 2. 奇偶性约束：如果重元素第一次出现在奇数位，那么奇数位全是重元素，反之。 因此我们如果直接枚举所有的 $j$ 去验证 $[j + 1, i]$ 是否为好数组，时间复杂度为 $O(n ^ 2)$。
考虑优化对于当前的位置 $i$，我们设其元素大小为 $v$，用 $odd[v]$ 和 $even[v]$ 来记录 $v$ 在奇数和偶数位最近的出现位置，这样的话可以确定 $j$ 的下界。 为了保证子数组 $[j + 1, i]$ 满足类型交替，需要避免 $v$ 元素在数组内出现奇偶性冲突，那么若 $j + 1 < \min(odd[v], even[v])$ 的话，则会使其冲突。 因此我们使 $minL$ 取所有元素 $min(odd[v], even[v]) + 1$ 的最大值，因此 $j > minL - 1$。 然后是最重要的分块，我们将原数组分块，每个块维护两个核心内容，$sum[k][b]$ 表示 $b$ 块满足在奇偶性 $k$ 下的合法的 $dp[j]$ 之和，$kpos[k][b]$ 是在 $k$ 的奇偶性下块 $b$ 是否满足。另外，为了维护分块时的单个元素， 我们维护 $pos[k][i]$ 是单个位置的 $i$ 是否满足奇偶性 $k$。 当我们查询 $[l, r]$ 内符合条件的 $dp[j]$ 之和时，对于整块，只需要判断 $kpos$ 是否有效，然后累加 $sum$ 即可，对于单个的块边缘的元素，则需要满足 $kpos$ 和 $pos$，有效则累加 $dp[j]$。 在区间更新时，只需要标记区间有效和无效，在完整的块上更新 $kpos$，零散的元素更新 $pos$ 和 $sum$。 时间复杂度分块的单次查询和更新的时间复杂度为 $O(\sqrt{n})$，时间复杂度为 $O(n \sqrt n)$。 简单卡常即可，最慢的点才两秒出头，对于四秒的时间限制完全够用。 代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<unordered_map>
#include<cstring>
using namespace std;
const int MOD = 1e6 + 3;
const int MAXN = 5 * 1e5 + 5;
int kpos[2][MAXN], sum[2][MAXN], pos[2][MAXN];
int L[MAXN], R[MAXN], id[MAXN];
int dp[MAXN], even[MAXN], odd[MAXN];
int a[MAXN], pre[MAXN];
pair<int, int> lst[MAXN];
int n, tot = 0, B;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
inline void update(int k, int l, int r, int x){
if(l > r) return;
int kl = id[l], kr = id[r];
if(kl != kr){
for(int i = kl + 1;i < kr;++ i){
kpos[k][i] += x;
}
if(l == L[kl]){
kpos[k][kl] += x;
}
else{
for(int i = l;i <= R[kl];++ i){
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
}
}
}
if(r == R[kr]){
kpos[k][kr] += x;
}
else{
for(int i = L[kr];i <= r;++ i){
if(pos[k][i]){
sum[k][kr] = (sum[k][kr] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kr] = (sum[k][kr] - dp[i - 1] + MOD) % MOD;
}
}
}
}
else{
if(l == L[kl] && r == R[kl]){
kpos[k][kl] += x;
}
else {
for(int i = l;i <= r;++ i){
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] + dp[i - 1]) % MOD;
}
pos[k][i] += x;
if(pos[k][i]){
sum[k][kl] = (sum[k][kl] - dp[i - 1] + MOD) % MOD;
}
}
}
}
}
inline int query(int k, int l, int r){
if(l > r) return 0;
int res = 0;
int kl = id[l], kr = id[r];
if(kl != kr){
for(int i = kl + 1;i < kr;++ i){
if(!kpos[k][i]){
res = (res + sum[k][i]) % MOD;
}
}
if(l == L[kl]){
if(!kpos[k][kl]){
res = (res + sum[k][kl]) % MOD;
}
}
else{
for(int i = l; i <= R[kl]; i++){
if(!pos[k][i] && !kpos[k][kl]){
res = (res + dp[i - 1]) % MOD;
}
}
}
if(r == R[kr]){
if(!kpos[k][kr]){
res = (res + sum[k][kr]) % MOD;
}
}
else{
for(int i = L[kr];i <= r;++ i){
if (!pos[k][i] && !kpos[k][kr]){
res = (res + dp[i - 1]) % MOD;
}
}
}
}
else{
if(l == L[kl] && r == R[kl]){
if(!kpos[k][kl]){
res = (res + sum[k][kl]) % MOD;
}
}
else{
for(int i = l;i <= r;++ i){
if (!pos[k][i] && !kpos[k][kl]){
res = (res + dp[i - 1]) % MOD;
}
}
}
}
return res;
}
int main(){
freopen("digit.in", "r", stdin);
freopen("digit.out", "w", stdout);
n = read();
B = 300;
for(int i = 1; i <= n; i += B){
L[++ tot] = i;
R[tot] = min(n, i + B - 1);
for(int j = i;j <= R[tot];++ j){
id[j] = tot;
}
}
// for(int i = 1;i <= n;++ i){
// cout << i << ' ' << id[i] << '\n;'
// }
dp[0] = 1;
for(int i = 1;i <= n;++ i) a[i] = read();
int leven = 0, lodd = 0, minL = 1;
memset(lst, -1, sizeof(lst));
for(int i = 1;i <= n;++ i){
sum[0][id[i]] = (sum[0][id[i]] + dp[i - 1]) % MOD;
sum[1][id[i]] = (sum[1][id[i]] + dp[i - 1]) % MOD;
dp[i] = dp[i - 1];
int v = a[i];
if(lst[v].second != -1){
update(lst[v].second & 1, lst[v].first + 1, lst[v].second, -1);
}
if(i & 1){
lodd = max(lodd, odd[v]);
odd[v] = i;
}
else{
leven = max(leven, even[v]);
even[v] = i;
}
lst[v] = {pre[v], i};
update(lst[v].second & 1, lst[v].first + 1, lst[v].second, 1);
pre[v] = i;
minL = max(minL, min(odd[v], even[v]) + 1);
if(leven < lodd){
dp[i] = (dp[i] + query(1, max(minL, leven + 1), i - 1)) % MOD;
}
else if (lodd < leven){
dp[i] = (dp[i] + query(0, max(minL, lodd + 1), i - 1)) % MOD;
}
}
printf("%d", dp[n] % MOD);
return 0;
}
题目4184 轻重数字
8
2 条 评论
2026-02-04 20:54:13
|