这个应用形象地说是区间跳跃(似乎不注意细节就容易 WA )

能解决的问题大致是 利用并查集快速跳过无用节点地特性 来实现 解决某个问题不重复 (太难说清楚了😭)

最近写到的题目:

1. CF#849 Div4. F. Range Update Point Query

code (q也可以用势能线段树来做q)

2. 蓝桥杯省赛-修改数组

code

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
constexpr int N = 1000010;
typedef long long LL;
int p[N];
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    fastio();
    int n;cin >> n;
    vector<int> a(n + 1);
    iota(p,p + N,0);
    for(int i = 1;i <= n;i ++ ) cin >> a[i];
    p[a[1]] = a[1] + 1; 

    for(int i = 2;i <= n;i ++ )
    {
        int x = find(a[i]);
        p[x] = find(x + 1);
        a[i] = x;
    }
    for(int i = 1;i <= n;i ++ )
        cout << a[i] << " ";
    return 0;
}

细节:

• $p$ 数组要多开几位