[AGC059D] Distinct Elements on Subsegments

· · 题解

或许更好的阅读体验。

这题牛逼完了。

思路：

考虑显然有相邻两个满足 |b_i - b_{i + 1}| \le 1，我们设 l_i 表示 a_{i - 1}, \cdots, a_{i - k + 1} 是否和 a_i 都不同，r_i 表示 a_{i + 1}, \cdots, a_{i + k - 1} 是否和 a_i 都不同，那么显然有 b 的转移：

b_{i + 1} = b_i + l_{i + k} - r_i

那么如果 b_i \ne b_{i + 1}，则 l_{i + k} - r_i = \pm 1，而值域在 [0, 1] 内，是可以唯一确定的；否则 b_i = b_{i + 1} 可以推出 l_{i + k} = r_i。

于是首先你可以得到一些 l, r 的性质，当然还有 \sum_{i = 1}^k l_i = b_1, \sum_{i = n}^{n + k - 1} r_i = b_n，只需要满足这些条件 l, r 就一定存在对应的某个 a 了吗？

具体的，把每个数 v 出现位置单独拿出来 p_1, \cdots, p_k，一定有 l_{p_i} = r_{p_{i - 1}}，且 l_{p_1} = r_{p_k} = 1，于是可以得到 l, r 中 0/1 数量都一样；即里面所有 l_{p_i} = 0 的位置，一定有 r_{p_{i - 1}} = 0，且 p_i - p_{i - 1} < k；扩展开来，对于所有 l_i = 0 的位置，一定存在 r_j = 0 使得 i - j < k。

于是对于一个固定的 l, r 来说，只要存在一个 l 中与 r 中 0 与 0 的匹配，且满足 1 \le x - y < k，那么就一定可以像那样拆成上面那种形式从而构造出解。

显然最优的一定是 l 中第 i 个 0 匹配 r 中第 i 个 0，不然交换了依旧合法；于是设 l, r 中 0 分别是 a_1, \cdots, a_k, b_1, \cdots, b_k，则要满足 1 \le a_i - b_i < k，且满足上面之前的所有限制（形如确定了一些位置的值，钦定两个位置值相同，前面 k 个和后面 k 个的和）。

限制考虑如何构造 l, r 使得满足上面那些限制，我们有钦定 r_i = l_{i + k}：

于是按照上面的分讨把所有 r_i = l_{i + k} 的限制解决掉了，剩下的就是 i \le k 的 l 和 i \ge n 的 r 是不确定的了，要求前面和是 b_1，那么肯定尽量是把 1 全部放前面，这样把 0 尽可能往后面放可以造成的匹配更多一点（因为 i \le k）；对于 r 是一样的，把 1 全部放在最后面即可。

现在得到了满足限制的 l, r，考虑如何构造出满足条件的 a？这是简单的，依次扫过去：

时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) x & (-x)
#define popcnt(x) __builtin_popcountll(x)
typedef long long ll;
using namespace std;
const int N = 4e5 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }  
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, k;
int a[N], b[N], l[N], r[N];
inline void solve(){
    n = read(), k = read();
    for(int i = 1; i <= n; ++i)
      b[i] = read();
    for(int i = 1; i <= n + k - 1; ++i)
      l[i] = r[i] = -1;
    for(int i = 1; i < n; ++i){ // b[i + 1] = b[i] + l[i + k] - r[i]
        if(abs(b[i] - b[i + 1]) > 1){
            puts("NO");
            return ;
        }
        if(b[i] == b[i + 1]){
            if(b[i] == k)
              r[i] = l[i + k] = 1;
            else
              r[i] = l[i + k] = 0;
        }
        else{
            if(b[i + 1] > b[i]){
                l[i + k] = 1;
                r[i] = 0;
            }
            else{
                l[i + k] = 0;
                r[i] = 1;
            }
        }
    }
    for(int i = 1; i <= k; ++i){
        if(l[i] == -1){
            if(b[1])
              l[i] = 1, --b[1];
            else
              l[i] = 0;
        }
        else
          b[1] -= l[i];
    }
    for(int i = n + k - 1; i >= 0; --i){
        if(r[i] == -1){
            if(b[n])
              r[i] = 1, --b[n];
            else
              r[i] = 0;
        }
        else
          b[n] -= r[i];
    }
    // for(int i = 1; i <= n + k - 1; ++i){
    //     cerr << l[i] << ' ';
    // }
    // cerr << '\n';
    //  for(int i = 1; i <= n + k - 1; ++i){
    //     cerr << r[i] << ' ';
    // }
    // cerr << '\n';
    int s0 = 0, s1 = 0;
    for(int i = 1; i <= n + k - 1; ++i)
      s0 += (!l[i]), s1 += (!r[i]);
    if(s0 != s1){
        puts("NO");
        return ;
    }
    int cnt = 0;
    queue<int> q;   
    for(int i = 1; i <= n + k - 1; ++i){
        if(l[i] == 1)
          a[i] = ++cnt;
        else{
            if(q.empty()){
                puts("NO");
                return ;
            }
            a[i] = a[q.front()];
            q.pop();
        }
        if(!r[i])
          q.push(i);
    }
    puts("YES");
    for(int i = 1; i <= n + k - 1; ++i){
        write(a[i]);
        putchar(' ');
    }
    putchar('\n');
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}