Untitled
raw download clone
CPP
views 14
,
size 3593 b
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define ms(a, b) memset(a, b, sizeof(a))
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr ll MOD = 1e9 + 7;

const int maxn = 1e6 + 5;
int n, q;
int seg[maxn * 4], input[maxn + 1];
bool tag[maxn * 4];
void pull(int id) {
	seg[id] = seg[id << 1] | seg[id << 1 | 1];
}
int upd(int id) {
	int ret = 0;
	for(int i = 0, tmp = seg[id]; tmp; tmp >>= 1, ++i) {
		if(tmp & 1)
			ret |= (1 << (19 - i));
	}
	return ret;
}
void push(int id) {
	if(tag[id] == 0) return;
	seg[id << 1] = upd(seg[id << 1]);
	seg[id << 1 | 1] = upd(seg[id << 1 | 1]);
	tag[id << 1] = 1;
	tag[id << 1 | 1] = 1;
	tag[id] = 0;
}
void build(int l = 1, int r = n, int id = 1) {
	if(l == r) {
		seg[id] |= (1 << __builtin_popcount(input[l]));
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, id << 1);
	build(mid + 1, r, id << 1 | 1);
	pull(id);
}
void upd(int ql, int qr, int l = 1, int r = n, int id = 1) {
	if(ql <= l && r <= qr) {
		tag[id] = 1;
		seg[id] = upd(seg[id]);
		return;
	}
	if(qr < l || r < ql) return;
	int mid = (l + r) >> 1;
	push(id);
	upd(ql, qr, l, mid, id << 1);
	upd(ql, qr, mid + 1, r, id << 1 | 1);
	pull(id);
}
int d;
pii qry(int ql, int qr, int l = 1, int r = n, int id = 1) {
	if(ql <= l && r <= qr) {
		pii ret = {-1e9, 1e9};
		for(int i = 0; i <= 10; ++i) {
			bool b = 0;
			if(d - i >= 0 && seg[id] & (1 << (d - i)))
				ret.F = d - i, b = 1;
			if(d + i >= 0 && seg[id] & (1 << (d + i)))
				ret.S = d + i, b = 1;
			if(b)
				return ret;
		}
	}
	if(qr < l || r < ql) return {-1e9, 1e9};
	int mid = (l + r) >> 1;
	auto a = qry(ql, qr, l, mid, id << 1);
	auto b = qry(ql, qr, mid + 1, r, id << 1 | 1);
	pii ret = {-1e9, 1e9};
	ret.F = (abs(a.F - d) < abs(b.F - d)) ? a.F : b.F;
	ret.S = (abs(a.S - d) < abs(b.S - d)) ? a.S : b.S;
	return ret;
}
int qry3(int l, int r, int x, int id) {
	if(l == r) return l;
	int mid = (l + r) >> 1;
	if(seg[id << 1] & (1 << x))
		return qry3(l, mid, x, id << 1);
	else
		return qry3(mid + 1, r, x, id << 1 | 1);
}
int qry2(int ql, int qr, int x, int l = 1, int r = n, int id = 1) {
	if(ql <= l && r <= qr) return qry3(l, r, x, id);
	if(qr < l || r < ql) return 1e9;
	int mid = (l + r) >> 1;
	int a = qry2(ql, qr, x, l, mid, id << 1);
	int b = qry2(ql, qr, x, mid + 1, r, id << 1 | 1);
	return min(a, b);
}
int q_qry(int ql, int qr) {
	auto p = qry(ql, qr);
	if(abs(p.F - d) > abs(p.S - d))
		return qry2(ql, qr, p.S);
	if(abs(p.F - d) < abs(p.S - d))
		return qry2(ql, qr, p.F);
	return min(qry2(ql, qr, p.F), qry2(ql, qr, p.S));
}
inline void solve() {
	ms(seg, 0), ms(tag, 0);
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> input[i];
	build();
	while(q--) {
		int k, l, r;
		cin >> k >> l >> r;
		if(k == 1) {
			cin >> d; d = __builtin_popcount(d);
			cout << q_qry(l, r) << '\n';
		}
		else
			upd(l, r);
	}
}

#define IOFILE
int main() {
#ifndef IOFILE
	cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);
#endif
#ifdef IOFILE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
	clock_t time = clock();
#endif
	int t = 1;
	cin >> t;
	for(int i = 1; i <= t; ++i) {
		cout << "Case " << i << ":\n";
		solve();
	}

#ifdef IOFILE
	cout << "\nUse " << static_cast<double>(clock() - time) / CLOCKS_PER_SEC << " seconds";
#endif
}
close fullscreen
Login or Register to edit or fork this paste. It's free.