首页 > 其他分享 >D. Cyclic MEX

D. Cyclic MEX

时间:2023-12-18 20:00:36浏览次数:30  
标签:Cyclic int back color cost test MEX Red

D. Cyclic MEX

For an array $a$, define its cost as $\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$.

You are given a permutation$^\ddagger$ $p$ of the set $\{0,1,2,\ldots,n-1\}$. Find the maximum cost across all cyclic shifts of $p$.

$^\dagger\operatorname{mex}([b_1,b_2,\ldots,b_m])$ is the smallest non-negative integer $x$ such that $x$ does not occur among $b_1,b_2,\ldots,b_m$.

$^\ddagger$A permutation of the set $\{0,1,2,...,n-1\}$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ($1$ appears twice in the array), and $[0,2,3]$ is also not a permutation ($n=3$ but there is $3$ in the array).

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the permutation $p$.

The second line of each test case contain $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($0 \le p_i < n$) — the elements of the permutation $p$.

It is guaranteed that sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the maximum cost across all cyclic shifts of $p$.

Example

input

4
6
5 4 3 2 1 0
3
2 1 0
8
2 3 6 7 0 1 4 5
1
0

output

15
5
31
1

Note

In the first test case, the cyclic shift that yields the maximum cost is $[2,1,0,5,4,3]$ with cost $0+0+3+3+3+6=15$.

In the second test case, the cyclic shift that yields the maximum cost is $[0,2,1]$ with cost $1+1+3=5$.

 

解题思路

  定义 $f_i$ 表示前缀 $[1, i]$ 的 $\operatorname{mex}$ 值,容易知道 $f_i$ 是单调递增的。现在考虑循环左移一次,即把原序列的 $p_1$ 移到最后,看看每个原本的 $f_i$ 会有什么变化。

  首先原本的 $f_1$ 会被删除。再考虑 $f_2 \sim f_n$,如果 $f_i < p_1$,那么不会改变;如果 $f_i > p_1$,那么就会变成 $p_1$。将变化后的 $f_i$ 左移一个单位,并在最后添加 $n$,那么就会得到 $p$ 序列循环左移一个单位后的前缀 $\operatorname{mex}$ 值。

  下表是以 $p = [3 \; 1 \; 0 \; 2]$ 按照上述过程模拟的表格:

\begin{array}{|c|c|c|c|}
\hline 
p & p' & f & f'  \\
\hline
3 \; 1 \; 0 \; 2 & 1 \; 0 \; 2 \; 3 & 0 \; {\color{Red} {0 \; 2 \; 4}} & {\color{Red} {0 \; 2 \; 3}} \; 4 \\
\hline
1 \; 0 \; 2 \; 3 & 0 \; 2 \; 3 \; 1 & 0 \; {\color{Red} {2 \; 3 \; 4}} & {\color{Red} {1 \; 1 \; 1}} \; 4 \\
\hline
0 \; 2 \; 3 \; 1 & 2 \; 3 \; 1 \; 0 & 1 \; {\color{Red} {1 \; 1 \; 4}} & {\color{Red} {0 \; 0 \; 0}} \; 4 \\
\hline
2 \; 3 \; 1 \; 0 & 3 \; 1 \; 0 \; 2 & 0 \; {\color{Red} {0 \; 0 \; 4}} & {\color{Red} {0 \; 0 \; 2}} \; 4 \\
\hline
\end{array}

  代码实现只需用依次枚举 $p_i$ 然后用 std::deque 去模拟这个过程,对每种情况取 $\sum\limits_{i=1}^{n}{f_i}$ 的最大值即可。不过如果每次都从队尾开始枚举,把大于 $p_i$ 的值都改成 $p_i$,那么整个模拟的时间复杂度就会达到 $O(n^2)$。

  改进的方法是用队列存储每个值以及对应的个数,由于 $f_i$ 递增因此相同的值必然是连续的一段。每次从队尾开始枚举时,只需统计比 $p_i$ 大的值的总数 $c$,并将这些值从队列中删除,最后再把 $(p_i, c)$ 压入队尾,同时还要把 $(n, 1)$ 压入队尾。另外还要用一个变量来维护队列中的 $f_i$ 的总和。

  由于在模拟的过程中一共往队列中插入 $O(n)$ 个元素,因此删除操作执行的次数也是 $O(n)$ 级别的。

  AC 代码如下,时间复杂度为 $O(n)$:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

int a[N];
bool vis[N];

void solve() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    memset(vis, 0, n + 10);
    LL s = 0;
    deque<PII> q;
    for (int i = 0, j = 0; i < n; i++) {
        vis[a[i]] = true;
        while (vis[j]) {
            j++;
        }
        q.push_back({j, 1});
        s += j;
    }
    LL ret = 0;
    for (int i = 0; i < n; i++) {
        s -= q.front().first;    // 把第一个元素删除
        if (--q.front().second == 0) q.pop_front();    // 这个值没有了
        int cnt = 0;    // 统计比a[i]大的数的个数
        while (!q.empty() && q.back().first > a[i]) {
            s -= 1ll * q.back().first * q.back().second;    // 将这些数从队列中删掉
            cnt += q.back().second;
            q.pop_back();
        }
        s += 1ll * a[i] * cnt + n;    // 这些数全部变成a[i]
        q.push_back({a[i], cnt});    // 并把a[i]及其个数插到队尾
        q.push_back({n, 1});    // 最后n插到队尾
        ret = max(ret, s);
    }
    printf("%lld\n", ret);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  Codeforces Round 915 (Div. 2) Editorial:https://codeforces.com/blog/entry/123384

标签:Cyclic,int,back,color,cost,test,MEX,Red
From: https://www.cnblogs.com/onlyblues/p/17912095.html

相关文章

  • abc 330E mex
    题意:对单个固定序列多次操作,输出每次操作后的mex函数值。E-MexandUpdate(atcoder.jp)不能用博弈论求sg函数那种直接枚举(TLE),因为最差可能达到O(n2),就算每次基于上一次的mex来剪枝也会被卡到这个复杂度,因为每次都只能线性枚举,所以这个方法不合适。因为mex可能取值的情况最......
  • 手动部署 chemex
    手动部署先决条件git:用于管理版本,部署和升级必要工具。PHP:仅支持PHP8.1。composer:PHP的包管理工具,用于安装必要的依赖包。MySQL5.7:数据库引擎,理论上MariaDB10.2+兼容支持。ext-zip:扩展。ext-json:扩展。ext-fileinfo:扩展。ext-ldap:扩展。ext-bcmath:扩展。ext-mysqli:扩展。ext......
  • 未出现的最小非负整数(MEX)
    典题合集前置芝士[Set做法]structMex{//自定义N的大小 intcnt[N];//cnt(i)表示数字i出现的次数 set<int>st;//记录未出现的数字 multiset<int>mulst;//记录出现过的数字 Mex(){ for(inti=0;i<N;++i)cnt[i]=0; for(inti=0;i<N;++i)st.insert(......
  • ABC330 E Mex and Update 题解
    LinkABC330EMexandUpdateQuestion给一个数组\(a\),有\(Q\)次修改每次把\(a_i\)改成\(x\)问每次修改后,不在\(a\)数组中的最小非负数时多少Solution记录每个\(a_i\)出现的次数\(num\)每个修改操作可以看成时先删除,后添加用set维护为\(num_x=0\)的\(x\)......
  • Caused by: io.debezium.DebeziumException: java.sql.SQLSyntaxErrorException: Acce
    1.情景展示如上图所示:在使用debezium读取mysql数据操作日志时(io.debezium.connector.mysql.MySqlConnector),报错:Causedby:io.debezium.DebeziumException:java.sql.SQLSyntaxErrorException:Accessdenied;youneed(atleastoneof)theRELOADprivilege(s)forthis......
  • 带修区间mex
    1xy把x改成y.2xy询问区间[x,y]的mex.part0polylog做法考虑整体二分,那就转换成了.保留权值[vl,vr)的数,带修区间数颜色数(是否全部出现过<=>颜色数=vr-vl).这个问题可以直接cdq.复杂度O(nlog^3n).part1考虑分块不难做到.O(1)单点修改(只往小了改).O(sqrtn)寻......
  • 1-1875D - Jellyfish and Mex
    题意:有一个长度为\(n\)的数组,每次删除一个数直到删完,求每次删除后数组的mex的和的最小值。(\(\sumn\leq5000,a_i\leq10^9\))思路:排序后,只有从0开始连续的数在会有贡献,对于连续的数,如果要消去他的对答案的贡献,只有全部去掉才行,考虑n的范围小于5000,n^2做法被允许。//因为排......
  • AND-MEX Walk
    这个题解不错。首先,10万组询问,10万的点和边,能且仅能用并查集判断图的连通性。看到&就要想到非严格单调递减,看到|就要想到非严格单调递增。不难发现样例中答案只有0,1,2,仔细想想,就会发现不可能存在210的序列,因为一旦有了2,末尾就一定是0,和任何数&都不可能是1。换......
  • cf1834E. MEX of LCM(维护右端点计算区间lcm)
    cf1834E首先可以估计一下答案的量级,因为小于答案的质数都要必须要出现,5e6以内的质数大概就是3e5,所以答案不超过5e6。我们维护以i右端点的lcm的值,这些值的数量不会太多,因为每次增长都至少×2,所以是log级别。每次新加的时候记得更新和去重即可。#include<cstdio>#include<algor......
  • 《面试1v1》CountDownLatch 和 CyclicBarrier
    我是javapub,一名Markdown程序员从......