先考虑 q2。
考虑到如果是以 \(2^N\) 为入手点因为进位的原因看起来就做不了。
于是考虑以 \(M\) 为前缀入手。
考虑刻画出 \(M\) 为前缀的数 \(x\) 的形式。
可以考虑根据 \(M\) 后面的位数 \(k\) 来刻画，有 \(x\in \bigcup_{k = 0}^{\lfloor{\frac{L}{\log_2 10}}\rfloor} [M\times 10^k, (M + 1)\times 10^k)\)。
又考虑到判断的是 \(2^N\)，于是考虑取 \(\log_2\)。
相当于判断 \(N\) 是否在 \(\bigcup_{k = 0}^{\lfloor{\frac{L}{\log_2 10}}\rfloor} [\log_2 M + k \log_2 10, \log_2 (M + 1) + k \log_2 10)\) 中。
那么因为对于不同的 \(k\) 的区间是无交的，所以可以先让 \(\log_2 M + k\log_2 10\le N\)，解出最大的 \(k = \lfloor\frac{N - \log_2 M}{\log_2 10}\rfloor\)，再判断 \([N < \log_2 (M + 1) + k\log_2 10]\)。
接下来考虑 q1。
那么相当于是求 \(x\in \bigcup_{k = 0}^{\lfloor{\frac{L}{\log_2 10}}\rfloor} [\log_2 M + k \log_2 10, \log_2 (M + 1) + k \log_2 10)\) 中的最小的整数。
考虑到 \(\log_2 (M + 1) - \log_2 M\le 1\)，这说明对于每个 \(k\) 对应的区间里面至多一个整数。
那么此时就需要满足 \(\log_2 M - \lfloor\log_2 M\rfloor + \{k\log_2 10\} \le 1, \log_2 (M + 1) - \lfloor\log_2 M\rfloor + \{k\log_2 10\} > 1(\{x\} = x - \lfloor x\rfloor)\)。
于是就能解出 \(\{k\log_2 10\}\in (1 + \lfloor\log_2 M\rfloor - \log_2 (M + 1), 1 + \lfloor\log_2 M\rfloor - \log_2 M]\)。
同时因为 \(N\in [\log_2 M + k \log_2 10, \log_2 (M + 1) + k \log_2 10)\)，所以可以知道 \(N = \lceil\log_2 M + k \log_2 10\rceil\)，所以最小化 \(N\) 就是最小化 \(k\)。
于是可以预处理出 \(k\in [0, \lfloor{\frac{L}{\log_2 10}}\rfloor]\) 中的 \(\{k\log 10\}\)，并按 \((\{k\log 10\}, k)\) 排序。
然后二分得到 \(\{k\log_2 10\}\) 的范围，线段树查询区间 \(k\) 最小值。
最后考虑 q3。
通过 q1 已经知道了 \(\{k\log_2 10\}\) 的范围。
同时又知道了 \(N = \lceil\log_2 M + k \log_2 10\rceil\)，于是可以同样二分求出 \(k\) 的范围。
于是相当于是在 \((\{k\log 10\}, k)\) 处有一个点，查矩形内点的数量。
那么可以预处理建可持久化线段树也可以离线下来扫描线。
时间复杂度 \(\mathcal{O}(L\log L + q\log L)\)。
其中 \(L\) 带个 \(\frac{1}{\log_2 10}\) 的常数，看起来必须带这个常数才能过？
实现用的是可持久化线段树，为了防止一些奇奇怪怪的边界特殊处理了 \(k = 0\) 的情况，同时记得判一下 \(M = 0\) 的情况。
#include<bits/stdc++.h>
inline void Freopen(std::string NAME) {
freopen((NAME + ".in").c_str(), "r", stdin);
freopen((NAME + ".out").c_str(), "w", stdout);
}
const double I = log2(10);
inline double getval(double x) {return x - floor(x);}
const int maxL = 1e6 / 3 + 10, LIM = 1e6;
int L, TL;
double l2[LIM + 10], a[maxL];
int id[maxL];
namespace opt1 {
int mn[maxL * 4];
void build(int k = 1, int l = 1, int r = L) {
if (l == r)
return mn[k] = id[l], void();
int mid = l + r >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
mn[k] = std::min(mn[k << 1], mn[k << 1 | 1]);
}
int query(int fl, int fr, int k = 1, int l = 1, int r = L) {
if (fl <= l && r <= fr)
return mn[k];
int mid = l + r >> 1, ans = L + 1;
if (fl <= mid) ans = std::min(ans, query(fl, fr, k << 1, l, mid));
if (mid < fr) ans = std::min(ans, query(fl, fr, k << 1 | 1, mid + 1, r));
return ans;
}
}
namespace opt3 {
int sum[maxL * 23], ls[maxL * 23], rs[maxL * 23], tot;
void update(int x, int &k, int lk, int l = 1, int r = L) {
k = ++tot, sum[k] = sum[lk] + 1, ls[k] = ls[lk], rs[k] = rs[lk];
if (l == r)
return ;
int mid = l + r >> 1;
if (x <= mid) update(x, ls[k], ls[lk], l, mid);
else update(x, rs[k], rs[lk], mid + 1, r);
}
int query(int fl, int fr, int k, int l = 1, int r = L) {
if ((! k) || (fl <= l && r <= fr))
return sum[k];
int mid = l + r >> 1, ans = 0;
if (fl <= mid) ans += query(fl, fr, ls[k], l, mid);
if (mid < fr) ans += query(fl, fr, rs[k], mid + 1, r);
return ans;
}
}
int pw[20], rt[maxL];
inline void init() {
for (int i = pw[0] = 1; i < 20; i++)
pw[i] = pw[i - 1] << 1;
for (int i = 1; i <= LIM; i++)
l2[i] = log2(i);
for (int i = 1; i <= L; i++)
a[i] = getval(a[i - 1] + I);
std::iota(id + 1, id + L + 1, 1);
std::sort(id + 1, id + L + 1, [&](int x, int y) {
return a[x] < a[y];
});
opt1::build();
for (int i = 1; i <= L; i++)
opt3::update(id[i], rt[i], rt[i - 1]);
}
inline double getlog2(int k, int M) {
return I * k + l2[M];
}
inline int getl(int M) {
double val = getval(1.0 - getval(l2[M + 1]));
int l = 1, r = L, w = L + 1;
while (l <= r) {
int mid = l + r >> 1;
if (a[id[mid]] >= val) w = mid, r = mid - 1;
else l = mid + 1;
}
return w;
}
inline int getr(int M) {
double val = 1.0 - getval(l2[M]);
int l = 1, r = L, w = -1;
while (l <= r) {
int mid = l + r >> 1;
if (a[id[mid]] <= val) w = mid, l = mid + 1;
else r = mid - 1;
}
return w;
}
inline int getL(int M, int L) {
int l = 1, r = L, p = L + 1;
while (l <= r) {
int mid = l + r >> 1;
if (getlog2(mid, M) > L) p = mid, r = mid - 1;
else l = mid + 1;
}
return p;
}
inline int getR(int M, int R) {
int l = 1, r = L, p = 0;
while (l <= r) {
int mid = l + r >> 1;
if (getlog2(mid, M) <= R) p = mid, l = mid + 1;
else r = mid - 1;
}
return p;
}
inline void solve() {
int opt, M; scanf("%d%d", &opt, &M);
if (opt == 1) {
for (int i = 0; i < 20; i++)
if (pw[i] == M)
return printf("%d\n", i), void();
int k = opt1::query(getl(M), getr(M));
printf("%.0lf\n", ceil(getlog2(k, M)));
} else if (opt == 2) {
int N; scanf("%d", &N);
if (M == 0)
return puts("0"), void();
int k = floor((N - l2[M]) / I);
puts(getlog2(k, M) <= N && N < getlog2(k, M + 1) ? "1" : "0");
} else {
int A, B; scanf("%d%d", &A, &B);
if (M == 0)
return puts("0"), void();
int ans = 0;
for (int i = 0; i < 20; i++)
ans += pw[i] == M && A <= i && i <= B;
int fl = getl(M), fr = getr(M);
int kl = getL(M, A - 1), kr = getR(M, B);
if (fl <= fr && kl <= kr)
ans += opt3::query(kl, kr, rt[fr]) - opt3::query(kl, kr, rt[fl - 1]);
printf("%d\n", ans);
}
}
int main() {
Freopen("p2");
int Q; scanf("%d%d", &Q, &L);
L /= 3, L++;
init();
for (; Q--; )
solve();
return 0;
}