loj516 「LibreOJ β Round #2」DP 一般看规律

时间：2021-07-01 12:28:32

传送门：https://loj.ac/problem/516

【题解】

那段代码求的是相同的数中间隔最小的值。

离散后用set维护每个值出现次数，每次操作相当于合并两个set，这步可以启发式合并。

加元素的时候直接找前驱和后继即可。

学了新姿势：set中insert有返回的，可以访问.first来调用新插入元素的iterator

# include <set>

# include <vector>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 1e5 + , M = 3e5 + ;

const int mod = 1e9+, inf = ;

int n, m, a[N];

struct quest {

    int x, y;

}q[N];

vector<int> ps;

set<int> s[M];

set<int>::iterator it, it2;

int ans[M], Ans = inf, id[M];

inline int getid(int x) {

    return lower_bound(ps.begin(), ps.end(), x) - ps.begin() + ;

}

int main() {

    cin >> n >> m;

    for (int i=; i<=n; ++i) {

        scanf("%d", a+i);

        ps.push_back(a[i]);

    }

    for (int i=; i<=m; ++i) {

        scanf("%d%d", &q[i].x, &q[i].y);

        ps.push_back(q[i].x); ps.push_back(q[i].y);

    }

    sort(ps.begin(), ps.end());

    ps.erase(unique(ps.begin(), ps.end()), ps.end());

    for (int i=; i<=n; ++i) a[i] = getid(a[i]);

    for (int i=; i<=m; ++i) q[i].x = getid(q[i].x), q[i].y = getid(q[i].y);

    for (int i=; i<=n; ++i) s[a[i]].insert(i);

    for (int i=; i<=ps.size(); ++i) {

        ans[i] = inf; id[i] = i;

        if(s[i].size() < ) continue;

        for (it = s[i].begin(), it2 = ++s[i].begin(); it2 != s[i].end(); ++it, ++it2)

            ans[i] = min(ans[i], *it2 - *it);

        Ans = min(Ans, ans[i]);

    }

    for (int i=, X, Y, x, tans; i<=m; ++i) {

        X = q[i].x, Y = q[i].y;

        if(!s[id[X]].size()) {

            printf("%d\n", Ans);

            continue;

        }

        if(!s[id[Y]].size()) {

            swap(id[X], id[Y]);

            printf("%d\n", Ans);

            continue;

        }

        tans = min(ans[id[X]], ans[id[Y]]);

        if(s[id[X]].size() > s[id[Y]].size()) swap(id[X], id[Y]);

        for (it = s[id[X]].begin(); it != s[id[X]].end(); ++it) {

            x = *it;

            it2 = s[id[Y]].insert(x).first;

            ++it2;

            if(it2 != s[id[Y]].end()) tans = min(tans, *it2 - x);

            --it2;

            if(it2 != s[id[Y]].begin()) --it2, tans = min(tans, x - *it2);

        }

        s[id[X]].clear();

        ans[id[Y]] = tans;

        ans[id[X]] = inf;

        Ans = min(Ans, tans);

        printf("%d\n", Ans);

    }

    return ;

}

相关文章