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;
}