勉強になった。
問題概要
1 〜N の順列 a1, a2, ..., aN が与えられる。 この順列に対して Q 個のクエリが順に与えられる。i 番目のクエリでは次の操作をしなければならない:
- 値 q が与えられる。順列 {a1, a2,…,aN} において qiの左側の順列を L、qiの右側の順列を R としたとき、元の順列 (L q R) を (R q L) に変更する
Q 個のクエリを順に処理した後の順列を一行に出力せよ。
考えたこと
連結リストね。。。
言われてみれば。。。
通常クエリ処理問題において index が指定されることが多いのに対し、今回は「値」が指定されているので、連結リスト向きだった。。。
#include <iostream> #include <vector> using namespace std; struct node { int val; node *left, *right; node() : val(-1), left(NULL), right(NULL) { } }; void print(node* cur) { while (cur != NULL) { cout << cur->val + 1; if (cur->right) cout << " "; cur = cur->right; } cout << endl; } int main() { int N, Q; cin >> N >> Q; vector<int> a(N); for (int i = 0; i < N; ++i) cin >> a[i], --a[i]; vector<node*> vec(N); node *head = new node(); node *tail = new node(); for (int i = 0; i < N; ++i) vec[i] = new node(); for (int i = 0; i < N; ++i) { if (i > 0) vec[a[i]]->left = vec[a[i-1]]; else head = vec[a[i]]; if (i+1 < N) vec[a[i]]->right = vec[a[i+1]]; else tail = vec[a[i]]; vec[a[i]]->val = a[i]; } //print(head); for (int _ = 0; _ < Q; ++_) { int q; cin >> q; --q; if (vec[q] == head) { vec[q]->left = tail; tail->right = vec[q]; vec[q]->right->left = NULL; head = vec[q]->right; vec[q]->right = NULL; tail = vec[q]; } else if (vec[q] == tail) { vec[q]->right = head; head->left = vec[q]; vec[q]->left->right = NULL; tail = vec[q]->left; vec[q]->left = NULL; head = vec[q]; } else { vec[q]->left->right = NULL; swap(vec[q]->left, tail); vec[q]->left->right = vec[q]; vec[q]->right->left = NULL; swap(vec[q]->right, head); vec[q]->right->left = vec[q]; } //print(head); } print(head); }