Hướng dẫn giải của Bedao Mini Contest 15 - SEQGAME2


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Với mỗi vị trí i có ~ 1 \le a[i] \le N~ ta tính ~F[i]~ là số lần dịch chuyển cần thiết để đưa ~a[i]~ về đúng vị trí .

Ta có ~cnt[x]~ là số lượng vị trí ~i~ mà có ~F[i] = x~.

Nhận thấy rằng các thao tác biến đổi không ảnh hướng đến nhau. Giả sử ta thực hiện ~x~ lần dịch phải, thì số thao tác cần thiết để biến đổi dãy về dạng ~1 , 2 , ... , N~ là ~x + n - cnt[x]~.

Ta dùng set để lưu lại các giá trị ~ x - cnt[x]~ , tìm giá trị nhỏ nhất để bước biến đổi là min.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 1e5 + 5;
set<pii> se;
int cnt[N], a[N], n, q;

int dist(int a, int b) {
    if (b >= a) return b - a;
    return n - a + b;
}

void add(int i, int v) {
    int x = dist(i, v);
    se.erase({n + x - cnt[x], x});
    cnt[x]++;
    se.insert({n + x - cnt[x], x});
}

void del(int i, int v) {
    int x = dist(i, v);
    se.erase({n + x - cnt[x], x});
    cnt[x]--;
    se.insert({n + x - cnt[x], x});
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n;
    for1(i,0,n - 1) se.insert({n + i, i});
    for1(i,1,n) {
        cin >> a[i];
        if (a[i] <= n) add(i, a[i]);
    }

    cin >> q;
    while (q--) {
        int i, v;
        cin >> i >> v;
        if (a[i] <= n) del(i, a[i]);
        a[i] = v;
        if (a[i] <= n) add(i, a[i]);

        cout << (*se.begin()).first << "\n";
    }

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.