数据有问题还是
查看原帖
数据有问题还是
758679
phoenixzhan楼主2023/11/8 17:20

我的程序有问题 /ll /ll

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
namespace IO {
	#define BF 65536
	char buf[BF], *p1 = buf, *p2 = buf;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BF, stdin), p1 == p2) ? EOF : *p1++)
//	template<typename T>
	inline int uread() {
		int x = 0; char c = getchar();
		while (!isdigit(c)) c = getchar();
		while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x;
	}
//	template<typename T>
	inline int read() {
		int x = 0, f = 0; char c = getchar();
		while (!isdigit(c)) f |= c == '-', c = getchar();
		while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return f ? -x : x;
	}
	char obuf[BF + 30]; int o1, o2, num[30];
	#define flush() fwrite(obuf, 1, o1, stdout), o1 = 0
	inline void putchar(const char &c) {
		obuf[o1++] = c; if (o1 >= BF) flush();
	}
//	template<typename T>
	inline void uwrite(int x) {
		do num[++o2] = x % 10; while (x /= 10);
		do obuf[o1++] = num[o2] ^ 48; while (--o2); obuf[o1++] = '\n'; if (o1 >= BF) flush();
	}
//	template<typename T>
	inline void write(const int& x) {
		if (x < 0) obuf[o1++] = '-', uwrite(-x); else uwrite(x);
	}
} using namespace IO;
namespace Loser {
	const int blk = 220, phz = 50000 / blk + 5;
	int n, m, a[50005], tot, bel[50005], L[50005], R[50005], val[phz][blk + 5], tmp[50005], xo[phz];
	vector<int> pre[phz]; vector<pii> suf[phz]; 
	void upd(int b) {
		queue<pii> q, qq;
		memset(val[b], 0, sizeof val[b]);
		for (int l = R[b]; l >= L[b]; l--) {
			tmp[l] = 0;
			for (int x = a[l]; x; x = x ^ (x & (-x)))
				qq.push({__builtin_ctz(x), l});
			while (!q.empty()) {
				if (~a[l] >> q.front().fi & 1) qq.push(q.front()); q.pop();
			}
			int xr = 0;
			while (!qq.empty()) {
				q.push(qq.front());
				xr |= 1 << qq.front().fi;
				int pos = qq.front().se; qq.pop(); 
				val[b][pos - l + 1] = max(val[b][pos - l + 1], xr); 
			}
		}
		for (int i = 1; i <= blk; i++) val[b][i] = max(val[b][i - 1], val[b][i]);
		int xr = 0;
		pre[b].clear();
		for (int i = R[b]; i >= L[b]; i--) {
			if ((xr | a[i]) != xr) {
				xr |= a[i];
				pre[b].pb(i);
			}
		}
		xr = 0;
		suf[b].clear();
		for (int i = L[b]; i <= R[b]; i++) {
			if ((xr | a[i]) != xr) {
				xr |= a[i];
				suf[b].pb({i, xr});
			}
		}
		xo[b] = xr;
	}
	bool cmp(int x, int y) { return x > y; }
	void main() {
		n = uread(), m = uread();
		for (int i = 1; i <= n; i++) a[i] = uread(), bel[i] = (i - 1) / blk + 1;
		tot = bel[n]; for (int i = 1; i <= tot; i++) L[i] = (i - 1) * blk + 1, R[i] = i * blk, upd(i); R[tot] = n;
		while (m--) {
			int op = uread(), x = uread(), y;
			if (op == 1) {
				y = uread(); a[x] = y; upd(bel[x]);
			} else {
				int ans = 1e9;
				for (int i = 1, l, r, mid; i <= tot; i++) {
					l = 1, r = min(R[i] - L[i] + 1, ans);
					while (l < r) {
						mid = (l + r) >> 1;
						if (val[i][mid] >= x) r = mid; else l = mid + 1;
					} 
					if (val[i][l] >= x) ans = min(ans, l);
				}
				vector<int> pos(0), tmp(0);
				for (int b = 1; b < tot; b++) {
					int xr = xo[b];
					tmp = pre[b];
					for (auto p: pos) {
						if ((xr | a[p]) != xr) {
							xr |= a[p]; tmp.pb(p);
						}
					}
					swap(tmp, pos);
					int l = -1; xr = 0;
					for (int r = suf[b + 1].size() - 1; r >= 0; r--) {
//						deb(r),deb(suf[b+1][r].se),deb(suf[b+1][r].fi); 
						while (l + 1 < pos.size() && (xr | a[pos[l + 1]] | suf[b + 1][r].se) < x) {
							xr |= a[pos[++l]]; 
						}
						if (l + 1 < pos.size()) ans = min(ans, suf[b + 1][r].fi - pos[l + 1] + 1);
					}
				}
				write(ans <= n ? ans : -1);
			}
		}
	}
}
signed main() {
	return Loser::main(), flush();
}
/*
5 1
4 0 1 3 1
2 6
ans: 4
*/

求调

2023/11/8 17:20
加载中...