第一鲜花外传一：卡评测

《不归之人与望眼欲穿的人们》是一道著名 Ynoi，并被搬至联考，这题有一定卡常的性质。强大的 ky 做了这道题。由于他太弱小，没有能通过 6、7、20 三个测试点。为了解决这一卡常问题，ky 进行了分块题卡常的传统步骤：调大调小块长后观察变化，并发现块长为 400 时可以通过测试点 6、7，开到 1000 最快，而块长为 150 时可以通过测试点 20，并且很快。

面对这一两难困境，普通人可能选择：

1. 优化代码写法，浪费生命。
2. 套取数据特判，自欺欺人。
3. 抄袭题解通过，丧失底线。
4. 放弃继续卡常，毫无追求。

强大的 ky 不是普通人，他选择了卡评测。具体地，以下程序以 50% 的概率使用 150 块长，否则使用 1000。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

mt19937 ran(chrono::system_clock::now().time_since_epoch().count());
const int N = 50005, B = ran() & 1 ? 150 : 1000, B1 = N / 150 + 5, B2 = 1000 + 5;

int n, m, a[N];
int mx[B1][B2], all[B1];
vector<pair<int, int>> pre[B1], suf[B1];

inline int getid(int x) { return (x - 1) / B + 1; }
inline int getfr(int id) { return min(n + 1, (id - 1) * B + 1); }

bool exi[31];

void build_block(int id)
{
	int l = getfr(id), r = getfr(id + 1) - 1;

	F(i, 1, B) mx[id][i] = 0;
	vector<pair<int, int>> tmp;
	suf[id].clear();
	all[id] = 0;
	F(i, l, r)
	{
		all[id] |= a[i];
		tmp.clear();
		F(j, 0, 30) if (a[i] >> j & 1) tmp.push_back({i, j});
		for (auto pi : suf[id]) if (!(a[i] >> pi.second & 1)) tmp.push_back(pi);
		suf[id].swap(tmp);

		int x = 0;
		for (auto pi : suf[id])
		{
			x |= 1 << pi.second;
			MAX(mx[id][i - pi.first + 1], x);
		}
	}
	F(i, 1, B) MAX(mx[id][i], mx[id][i - 1]);

	F(j, 0, 30) exi[j] = 0;
	pre[id].clear();
	int x = 0;
	F(i, l, r) F(j, 0, 30) if (a[i] >> j & 1 && !exi[j])
	{
		exi[j] = 1;
		x |= 1 << j;
		pre[id].push_back({i, x});
	}
	reverse(pre[id].begin(), pre[id].end());
}

int query(int x)
{
	int res = n + 1;
	vector<pair<int, int>> vec, tmp;
	F(id, 1, getid(n))
	{
		if (!vec.empty())
		{
			int p = 1, y = 1 << vec[0].second;
			for (auto pi : pre[id])
			{
				while (p < vec.size() && (y | pi.second) < x)
					y |= 1 << vec[p++].second;
				if ((y | pi.second) < x) break;
				MIN(res, pi.first - vec[p - 1].first + 1);
			}
		}
		
		tmp = suf[id];
		for (auto pi : vec) if (!(all[id] >> pi.second & 1)) tmp.push_back(pi);
		vec.swap(tmp);

		int cl = 1, cr = B;
		while (cl <= cr)
		{
			int cm = (cl + cr) >> 1;
			if (mx[id][cm] >= x) cr = cm - 1, MIN(res, cm);
			else cl = cm + 1;
		}
	}
	return res == n + 1 ? -1 : res;
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n >> m;
	F(i, 1, n) cin >> a[i];
	F(i, 1, getid(n)) build_block(i);

	F(i, 1, m)
	{
		int op; cin >> op;
		if (op == 1)
		{
			int p, x; cin >> p >> x;
			a[p] = x;
			build_block(getid(p));
		}
		else
		{
			int x; cin >> x;
			cout << query(x) << '\n';
		}
	}
	
	return 0;
}

这是他的战果：

ky 素质如此！ky 好闪，拜谢 ky！