i629: 序列操作問題
Tags :
Accepted rate : 3人/7人 ( 43% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-08-28 17:48

Content

現在有一個空的序列跟 Q ,泥要對他做 Q 次操作,每次操作會是以下其中一種:

  1. 插入一個數字 k 到序列中
  2. 刪除序列中的一個數字 k
  3. 輸出第 k 小的數字
  4. 把序列中所有數字 xor k

你要怎麼解決這個問題呢?

Input

第一行有一個正整數 Q 代表有幾個操作,接下來有 Q 行,每行有兩個數字 t 跟 k 代表第幾種操作跟每個操作的參數。

 

測資限制:

1 ≤ Q ≤ 2 × 105

1 ≤ t ≤ 4

1 ≤ k ≤ 109

Output

對於第一種和第四種操作,尼不用輸出任何東西。

對於第二種操作,如果序列中沒有 k 這個數字,那就輸出 "HEHE" (不含引號),否則不用輸出任何東西。

對於第三種操作,輸出序列中第 k 小的數字,如果序列的大小不到 k,那就輸出 "QQ" (不含引號),否則不用輸出任何東西。

Sample Input #1
5
1 2
1 4
2 2
4 3
3 1
Sample Output #1
7
測資資訊:
記憶體限制: 128 MB
不公開 測資點#0 (10%): 1.0s , <10M
不公開 測資點#1 (10%): 1.0s , <10M
不公開 測資點#2 (10%): 1.0s , <10M
不公開 測資點#3 (10%): 1.0s , <10M
不公開 測資點#4 (10%): 1.0s , <10M
不公開 測資點#5 (10%): 1.0s , <10M
不公開 測資點#6 (10%): 1.0s , <10M
不公開 測資點#7 (10%): 1.0s , <10M
不公開 測資點#8 (10%): 1.0s , <10M
不公開 測資點#9 (10%): 1.0s , <10M
Hint :
這是個會拿到 TLE 的程式碼,請你優化它
#include ﹤bits/stdc++.h>
using namespace std;
 
int q;
multiset﹤int> s;
vector﹤int> v;
 
signed main() {
       cin >> q;
       while (q--) {
              int op, k;
              cin >> op >> k;
              if (op == 1) s.insert(k);
              if (op == 2) {
                     if (s.find(k) == s.end()) cout << "HEHE\n";
                     else s.erase(s.find(k));
              }
              if (op == 3) {
                     v.clear();
                     for (int i : s) v.push_back(i);
                     if (k - 1 >= v.size()) cout << "QQ\n";
                     else cout << v[k - 1] << '\n';
              }
              if (op == 4) {
                     v.clear();
                     for (int i : s) v.push_back(i ^ k);
                     s.clear();
                     for (int i : v) s.insert(i);
              }
       }
}
Tags:
出處:
[管理者: Easonsfriend(becaidorz) ]


ID User Problem Subject Hit Post Date
31972 r1cky(tour1st) i629
解題心得
49 2022-09-03 10:17