一開始一個陣列 $a_1, a_2, \dots, a_n$，請寫一個程式支援以下幾種操作：
- Insert $i\ x$ - 在陣列的第 $i$ 項之前插入一個數字 $x$。如果 $i-1$ 是當前陣列長度的話則代表插入到陣列尾端。
- Delete $i$ - 刪除陣列的第 $i$ 項。
- Reverse $l\ r$ - 將陣列 $[l, r]$ 區間反轉。
- Query $l\ r\ k$ - 求陣列區間 $[l, r]$ 中的第 $k$ 小元素。
第一行有兩個正整數 $n\ q$ $(1\le n, q\le 50000)$ 代表初始陣列長度與操作數量。
第二行有 $n$ 個整數 $a_1, a_2, \dots, a_n$ $-10^5\le a_i\le 10^5$ 為初始陣列。
接下來有 $q$ 行，每行代表一個操作。
假設 $N$ 是當前陣列長度，那麼每個操作均滿足以下條件：
- Insert $i\ x$: $1\le i\le N+1, -10^5\le x\le 10^5$。
- Delete $i$: $1\le i\le N$。
- Reverse $l\ r$: $1\le l\le r\le N$。
- Query $l\ r\ k$: $1\le l\le r\le N,1\le k\le r-l+1$。
對於每個 Query 操作輸出一行一個整數代表該詢問的答案。
# 範例測資 1 5 5 -10 1 4 -3 -5 Query 4 4 1 Query 1 2 1 Query 4 5 2 Query 2 3 2 Query 4 5 1 # 範例測資 2 5 5 -2 4 4 -7 2 Delete 5 Delete 1 Insert 2 6 Query 3 3 1 Query 4 4 1 # 範例測資 3 5 5 -6 7 3 3 0 Reverse 1 4 Insert 3 -6 Query 3 4 1 Reverse 4 5 Query 1 4 2
# 範例測資 1 -3 -10 -3 4 -5 # 範例測資 2 4 -7 # 範例測資 3 -6 -6
本題限用 C 來實做，請大家好好練習實做能力，如有 C 以外的 submission 將會改成 special judge 強制只有 C 能通過（由於這樣會看不到執行時間與記憶體因此請各位好好遵照要求）。
本題為嚴格比對。
本題時間與空間限制較緊，或許可以好好計算時間/空間複雜度來選擇最適合的參數（時限至少有標程的 2 倍）。
Hint: Unrolled Linked List
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||