Wi Know

簡化後題目敘述

輸入說明

第一列包含一個正整數 $N$ ($1\le N\le 400000$)。 第二列開始有 $N$ 列，每一列包含一個正整數 $S_i$ ($1\le S_i\le N$)。

輸出說明

若存在答案，請輸出 $A, B$ 之值。若不存在形如 $A, B, A, B$ 的子序列，輸出 -1。

範例輸入 1

8
1
3
2
4
1
5
2
4

範例輸出 1

1 2

範例輸入 2

8
1
2
3
4
5
6
7
1

範例輸出 2

-1

範例輸入 3

4
2
1
2
1

範例輸出 3

2 1

OJ 連結

• Open Kattis - Wi Know

題目出處：ICPC 2018 Asia Singapore Regional

解法

我們可以先做出以下觀察：如果存在至少一組交錯的子序列 A, B, A, B，那麼 A 總可以是序列中第一次出現的那個 A、而 B 總可以挑選序列中最後一次出現的 B。

於是，對於每一個 A，我們想知道 A 的右邊的第一個 B、還有跟 A 左邊出現最靠近的 B，滿足這個條件的 B 的最小值。對於一個特定數字 X，那麼我們可以把整個序列，依據所有 X 出現過的位置，切成許多區間。 利用「掃描線」的概念，從右到左，維護目前跨過這條掃描線的區間們。 假設現在掃描線所在的位置是一個 A 數字，那麼所有橫跨過這個區間、並且左界落在「第一個 A 的右邊」的那些區間編號最小者，就會是一個可能的答案。

如下圖黑色部份，是我們想查詢的區間。打圈代表我們想知道的左界的確落在範圍內。而打叉代表左界落在範圍外：

那麼我們只要找出與黑色區間相交的「最小編號」區間就可以了！實作上我們維護一個區間樹，當掃描線從右掃到左的時候，先將「離開的區間」刪掉，然後再依據當前區間 $[\ell, r]$，查詢現在「左界 $>\ell$」的區間編號最小值。然後再將當前區間左界加入區間樹。

參考程式碼

#include <bits/stdc++.h>
using namespace std;

// 關於區間樹的操作：依序為插入、刪除、詢問。
const int LEAF_OFFSET = (1<<19);
int tree[(1<<20)];
inline int GetMinLabel(int l, int r) {
  if (l == 0 || r == 0) return l+r;
  return min(l, r);
}
void Insert(int x, int label) {
  x += LEAF_OFFSET;
  tree[x] = label;
  for (x/=2; x; x/=2)
    tree[x] = GetMinLabel(tree[x*2], tree[x*2+1]);
}
void Remove(int x) {
  x += LEAF_OFFSET;
  tree[x] = 0;
  for (x/=2; x; x/=2)
    tree[x] = GetMinLabel(tree[x*2], tree[x*2+1]);
}
int Query(int l) {
  l += LEAF_OFFSET;
  int ans = tree[l];
  while (l) {
    if (l%2==0)
      ans = GetMinLabel(ans, tree[l+1]);
    l/=2;
  }
  return ans;
}


// 紀錄輸入的序列。
int S[400005];
vector<int> positions[400005];

pair<int, int> best = {-1, -1};
void UpdateSolution(int A, int B) {
  if (best.first == -1 || best > make_pair(A, B)) {
    best = {A, B};
  }
}

void OutputAnswer() {
  if (best.first == -1) cout << "-1" << endl;
  else cout << best.first << " " << best.second << endl;
}

int main() {
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> S[i];
    positions[S[i]].push_back(i);
  }
  for (int i = N-1; i >= 0; i--) {
    int A = S[i];
    positions[A].pop_back();
    Remove(i);
    if (!positions[A].empty()) {
      int B = Query(positions[A][0]);
      if (B > 0) UpdateSolution(A, B);
      Insert(positions[A].back(), A);
    }
  }
  OutputAnswer();
  return 0;
}

夢月說

花一分鐘想不出來，花三分鐘就想到了！

關於競程日記

🍅 如果您想到更多有趣漂亮簡單乾淨的解法話歡迎留言給競程日記小編群！

ℹ️ 這是一篇投稿給競程日記的文章，歡迎大家投稿、交流與分享程式解題競賽的點點滴滴！