TIOJ 1739：[APIO '08] Beads [Interactive]

TIOJ 1739：[APIO '08] Beads [Interactive]

題目大意：有 $n$ 個珠子，有 $m$ 個時刻，在第 $i$ 個時刻會交換位置 $p_i$ 與 $p_i+1$ 的珠子，之後有 $q$ 筆強制在線的詢問，問你在第 $B$ 個時刻之後，原本在第 $A$ 個位置的珠子現在在哪裡。

解法：紀錄每個珠子位置有改變的時刻，再 $\text{upper_bound}$ 即可找出答案。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "lib1739.h"
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 3e5 + 5;

int n, m, q, a[SIZE];
vector<pair<int, int>> v[SIZE];

int main() {
    scanf ("%d %d", &n, &m);
    iota (a, a + n + 1, 0);
    FOR (i, 1, n) v[i].pb (0, i);
    FOR (i, 1, m) {
        int p;
        scanf ("%d", &p);
        int &x = a[p], &y = a[p + 1];
        v[x].pb (i, p + 1);
        v[y].pb (i, p);
        swap (x, y);
    }
    q = getNumQuestions();
    while (q--) {
        int id, t;
        getQuestion(id, t);
        int pos = upper_bound (v[id].begin(), v[id].end(), make_pair (t, n + 1)) - v[id].begin() - 1;
        answer (v[id][pos].S);
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！