CF1725K

lowbit · 2023-11-07 22:38:42 · 题解

发现每次操作 3 至多会增加两种数值，故总的数值不会超过 O(n+q) 个。所以考虑暴力合并，合并的总次数不会超过 O(n+q) 次。

使用并查集模拟合并即可，实现时用 set 维护现有的数的集合，每次二分出要修改的数，时空复杂度 O((n+q)\log (n+q))。（trick：可以在初始时插入一个极大值方便操作。）

Code：

#include <bits/stdc++.h>

typedef long long ll;
typedef double db;
#define ull unsigned long long
#define ldb long double
#define pii pair<int, int>
#define mkp make_pair
#define pb push_back
#define pc putchar
#define sp pc(' ')
#define et puts("")
#define debug cerr<<"--ERROR--"<<endl
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define mem(a, x) memset(a, x, sizeof(a))
#define in(a, n) rep(i, 1, n) a[i]=rd()
#define all(x) x.begin(), x.end()

using namespace std;
inline ll rd(){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*10+c-48; c=getchar();} return x*f;}
inline void wr(ll x){if(x<0) putchar('-'), x=-x; if(x>9) wr(x/10); putchar(x%10+48);}

const ldb eps = 1e-9;
const ll INF = 0x3f3f3f3f;
const int mo = 1e9+7;
const int N = 1.6e6+3;

int n, q, f[N], val[N], tot;
map <int, int> pos;
set <int> s;

void clear() {  }

int find(int k) {
    return f[k]==k ? k : f[k]=find(f[k]);
}
int newnode(int x) {
    s.insert(x);
    val[++tot]=x, f[tot]=tot;
    return tot;
}
void modify(int i, int x) {
    if(!pos[x]) pos[x] = newnode(x);
    f[i] = pos[x];
}
signed main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);

int TT = 1;
//TT = rd();
while(TT--)
{
    cin >> n;
    rep(i, 1, n) f[i]=i;
    tot=n;
    rep(i, 1, n) {
        int x=rd();
        modify(i, x);
    }
    s.insert(INF);
    cin >> q;
    while(q--) {
        int op, k, v, l, r;
        op=rd();
        if(op == 1) {
            k=rd(), v=rd();
            modify(k, v);
        }
        if(op == 2) {
            k=rd();
            wr(val[find(k)]), et;
        }
        if(op == 3) {
            l=rd(), r=rd();
            for(auto it = s.lower_bound(l); (v=*it) <= r; it = s.lower_bound(l)) {
                modify(pos[v], v-l < r-v ? l-1 : r+1);
                pos[v]=0, s.erase(it);
            }
        }
    }
    et;
    if(TT) clear();
}
    return 0;
}

/*

*/

并查集数组记得要开两倍。