2020 Jiangsu Collegiate Programming Contest D Delete Prime --分塊+二分

2020 Jiangsu Collegiate Programming Contest

題目描述

有 n 個球排成一行。每個球上都有一個數字，第i個球上的數字是i (1 ≤ i ≤ n). 。

對于每一輪，我們選擇索引為1或素數的球，并将它們從清單中踢出按順序排隊。在那之後，我們開始下一輪的比賽，剩下的球保持相對位置不會改變，其索引從1開始按順序重新标記（但球上的數字不會改變）。我們重複這個過程，直到沒有球留下。

有一個踢出序列D，初始為空，從一開始。每次球被踢出時，球上的數字都會被加到D後面。

例如，當n=6時，球[1,2,3,4,5,6]在一條直線上。在第一輪，我們踢出了球[1,2,3,5]（索引1,2,3,5）按順序排列，其餘的球為[4,6]。在第二輪，我們踢出局[4,6]（索引1,2）按順序排列，沒有剩餘的球。是以被踢出的序列是D=[1,2,3,5,4,6]。注D的索引總是從1開始。

現在您需要回答兩類問題：

•類型1給定n和k，踢出序列中k的指數是多少？換言之，找到這樣的xD[x]=k。

•類型2給定n和k，踢出序列中的第k個數字是多少？換句話說，找到x使得D[k]=x。

輸入

輸入的第一行包含一個整數 T （ 1 ≤ T ≤ 2 ⋅ 1 0 5 ) T（1≤ T≤ 2 · 10^5) T（1≤T≤2⋅105)，表示查詢的數量。

對于下面的T行，每行包含三個整數 T ， n ， k （ T ∈ { 1 , 2 } , 1 ≤ K ≤ N ≤ 1 0 6 ) T，n，k（T∈ \{1, 2\}, 1 ≤ K≤ N≤ 10^6) T，n，k（T∈{1,2},1≤K≤N≤106)，代表上面提到的類型為t的查詢。

輸出

對于每個查詢，在一行中輸出答案

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
template<class...Args>
void debug(Args... args) {//Parameter pack
    auto tmp = { (cout << args << ' ', 0)... };
    cout << "\n";
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pll;
typedef pair<int, int>pii;
const ll N = 1e6 + 5;
const ll MOD = 998244353;
const ll INF = 1e9 + 7;

ll primes[N], cnt;
bool st[N];
void get_primes(ll n) {
    for (ll i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (ll j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
vector<int>d[N];
int vis[N];
int cntd;
void get_D(int n) {
    memset(vis, 0, sizeof(vis));
    int viscnt = 0;
    int pos;
    while (viscnt < n) {
        pos = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                pos++;
                if (!st[pos]) {
                    vis[i] = 1;
                    viscnt++;
                    d[cntd].push_back(i);
                }
            }
        }
        cntd++;
    }
}
int get_rank(int n, int k) {
    int ans = 0;
    for (int i = 0; i < cntd; i++) {
        int t = upper_bound(d[i].begin(), d[i].end(), k) - d[i].begin() - 1;
        if (d[i][t] == k) {
            ans += t;
            return ans + 1;
        }
        else ans += upper_bound(d[i].begin(), d[i].end(), n) - d[i].begin();
    }
}
int get_val(int n,int k) {
    int ans = 0;
    for (int i = 0; i < cntd; i++) {
        int t = upper_bound(d[i].begin(), d[i].end(), n) - d[i].begin();
        if (k - t <= 0) return d[i][k-1];
        else k -= t;
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    get_primes(N);
    get_D(1000002);
    int t;
    cin >> t;
    while (t--) {
        int opt, n, k;
        cin >> opt >> n >> k;
        if (opt == 1)cout << get_rank(n, k) << "\n";
        else cout << get_val(n, k) << "\n";
    }
    return 0;
}