Solution được đóng góp từ bạn SPyofgame

Nhận xét truy vấn 1:

Nếu truy vấn 1 không đủ nhanh thì TLE trước cả truy vấn 2 nên mình cần tìm một cấu trúc dữ liệu đủ nhanh

Ta có thể sử dụng các cấu trúc dữ liệu cây đề tìm, chèn, xóa trong ~O(log n)~ hoặc nhanh hơn, ví dụ như trong C++ có std::set

Nhận xét truy vấn 2:

Nếu như ~x = 0~ thì in ra ~0~.

Nếu như tập ~A~ rỗng, hoặc là tập ~A~ không bao gồm số 1, thì không thể phủ được đoạn con ~[1, 1]~ trong đoạn ~[1, x]~ nên ta xuất ~-1~ và thực hiện truy vấn tiếp theo

Ngược lại ta luôn tồn tại cách phủ xuất phát từ đoạn con ~[1, 1]~. Vấn đề chúng ta bây giờ là làm sao để biết bao nhiêu đoạn nào đã bị phủ, và nên sử dụng thêm số nào?

• Nhận xét 1: Nếu đoạn ~[1, k]~ đã bị phủ, thì nếu cho thêm giá trị ~v > k + 1~ thì sẽ luôn thiếu mất đoạn ~[k + 1, k + 1]~, nhưng nếu cho thêm giá trị ~v \leq k + 1~ thỉ đoạn bị phủ hiện tại sẽ là ~[1, k + v]~ vì luôn tồn tại số ~y~ thuộc đoạn ~[1, k]~ để phủ thêm lên đoạn ~[k + 1, k + v]~. Vì đoạn càng ngày càng được nới rộng dần sang phía ~[x]~, nên giá trị ~v~ ta chọn sẽ càng lớn dần

• Nhận xét 2: Nếu cứ phải xét một nhóm k đoạn ~[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]~ (~1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \dots < l_k \leq r_k)~ đã bị phủ thì sẽ phải chèn thêm các số vào giữa để lấp lại các đoạn bị sót. Nhưng như thế cũng có nghĩa là tồn tại một cách sắp xếp thứ tự chèn các số để sao cho các đoạn bị phủ sẽ phủ lần lượt ~[1, r_1] \rightarrow [1, r_2] \rightarrow \dots \rightarrow [1, r_k]~, mà từ nhận xét ~1~, ta cũng chỉ cần chọn các số theo thứ tự từ nhỏ đến lớn mà thôi. Nên cách này vừa cài khó, vừa khó tính toán và tối ưu hơn cách làm theo nhận xét ~1~, hoặc thậm chí nhận xét ~2~ không tồn tại thuật toán để giải

Vì mình muốn phủ bằng càng ít số càng tốt và không được chọn số lớn hơn ~k + 1~ hay không có trong tập. Nên mình sẽ chọn số ~v_0 = \underset{u \in A}{max}(u | u \leq k + 1)~. Mình có thể chặt nhị phân trên cây trong ~O(log^2(n))~ hoặc tìm kiếm trực tiếp trên cây trong ~O(log\ n)~

Nhưng giờ mình không thể cứ thêm từng số được, mà nhận thấy rằng để tìm được số ~v~ tiếp theo thỏa mãn, thì đó sẽ là ~v_1 = \underset{u \in A}{max}(u | u \leq k + v + 1)~, và cho đến lúc đó mình chỉ có thêm số ~v_0~.

• Nhận xét 3: Tồn tại ~p~ là vị trí mà khi đoạn bị phủ chứa cả ~[1, p]~ mình sẽ thấy ~v_0~ sẽ không còn tối ưu để thêm nữa. Rõ ràng ~p = min(v_1, x) \geq k~. Cho tới lúc đó thì mình cần thêm ~v_0~ với số lần là ~\lceil \frac{p - k}{v_0} \rceil = \lfloor \frac{p - k + v_0 - 1}{v_0} \rfloor~

Mỗi bước, có vẻ như ~v_1~ có thể thay thế ~v_0~ với ~O(|A|)~ lần trong trường hợp xấu nhất. Nhưng điều này chỉ khả thi khi giới hạn của các số ~v \in A~ đủ lớn. Bởi vì sau mỗi bước đưa đoạn ~[1, k]~ nới rộng lên trên đoạn ~[1, p]~ thì độ dài tăng ít nhất ~2~ lần trong 1 bước, cụ thể là ~1 \leq \frac{k}{2} \leq v_0 \leq k + 1 \leq 2 \times v_0 \leq v_1~. Nên số bước thực tế sẽ là ~O(min(|A|, log_2(max(x \in A)))~ . Mà vì mỗi bước, mình cần tìm kiếm trên cây mất ~O(log n)~ nên độ phức tạp của bài này là ~O(log\ n \times log(min(n, max(x))))~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define int long long
#define _(x) (1LL<<(x))
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define turn_all(x) (_(x)-1LL)
#define bitCnt(x) __builtin_popcountll(x)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

signed main()
{
    fastIO

    int q;
    cin>>q;

    set<int> s;
    while (q--)
    {
        int cmd;
        int x;
        cin>>cmd>>x;
        if (cmd == 1)
        {
            if (s.find(x) != s.end()) s.erase(x);
            else s.insert(x);
        }
        else
        {
            if (s.find(1) == s.end())
            {
                cout<<-1<<"\n";
                continue;
            }

            int res = 0;
            int curSum = 0;
            while (curSum < x)
            {
                auto it = s.upper_bound(curSum+1);
                auto val = *prev(it);

                int targetSum = x;
                if (it != s.end()) targetSum = min(targetSum, *(it) - 1);

                int cnt = (targetSum - curSum) / val;
                while (curSum + cnt*val < targetSum) ++cnt;
                res += cnt;
                curSum += cnt*val;
            }

            cout<<res<<"\n";
        }
    }
}