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}$,歡迎追蹤!
留言
張貼留言