Ynoi2012 NOIP2016 人生巅峰

发布时间 2023-10-07 16:50:02作者: Ender_32k

Day \(\text{XXX}\)

注意到修改是易于复合的立方操作,而且值域非常小,所以可以直接 \(O(v\log m)\) 预处理出对每个 \(i\in[0,v)\) 操作了 \(2^{j}\le m\) 次的结果,维护出每一位被修改了多少次,查询某一位的值直接倍增 \(O(\log m)\) 即可。

然后这个限制很弱,因为如果区间内有重复的数的话直接分别选了这两个数,所以当 \(r-l+1\ge v\) 时就一定满足了。

考虑进一步弱化限制,你发现这东西再看一眼就会爆炸。因为区间 \([l,r]\) 的子集数为 \(2^{r-l+1}\),而子集的贡献和的范围只有 \(v(r-l+1)\),则 \(2^{r-l+1}>v(r-l+1)\) 时必定满足,所以 \(r-l+1\ge 14\) 时必定满足(事实上很难构造出长度 \(\le 13\) 且子集贡献和的个数卡满 \(2^{r-l+1}\) 的数据,所以乱搞都能过)。

接下来考虑 \(r-l+1\le 13\) 的情况,令 \(f_{i,j}\) 表示前 \(i\) 个数是否能凑出大小为 \(j\) 的集合。发现对于一个位置 \(i\in [l,r]\)\(f_{i-1,j}=f_{i-1,j-a_i-1}=1\) 则有解,因为可以直接将 \(i\) 塞进后者集合,并且不用担心有交集的情况(如果有交集,两边同时减去交集即可)。

然后 bitset 开冲就完事了。

// Problem: P5527 [Ynoi2012] NOIP2016 人生巅峰
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5527
// Memory Limit: 125 MB
// Time Limit: 500000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int N = 1e5 + 100;
const int M = 1e3 + 100;

int n, m, P;
int a[N], tr[N], f[M][18];
bitset<M * 13> b;

#define lb(x) (x & (-x))
void upd(int x, int y) { for (int i = x; i <= n; i += lb(i)) tr[i] += y; }
int qry(int x) { int res = 0; for (int i = x; i; i -= lb(i)) res += tr[i]; return res; }

void solve() {
	cin >> n >> m >> P;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i < P; i++) f[i][0] = i * i * i % P;
	for (int j = 1; (1 << j) <= m; j++)
		for (int i = 0; i < P; i++)
			f[i][j] = f[f[i][j - 1]][j - 1];
	for (int _ = 1, op, l, r; _ <= m; _++) {
		cin >> op >> l >> r;
		if (op == 2) upd(l, 1), upd(r + 1, -1);
		else {
			if (r - l + 1 > 13) {
				cout << "Yuno\n";
				continue;
			}
			int fl = 0; b.reset(), b[0] = 1;
			for (int i = l; i <= r; i++) {
				int x = a[i], y = qry(i);
				for (int j = 0; (1 << j) <= m; j++)
					if ((y >> j) & 1) x = f[x][j];
				if ((b & (b << (x + 1))).any()) {
					fl = 1;
					break;
				}
				b |= (b << (x + 1));
			}
			if (fl) cout << "Yuno\n";
			else cout << "Yuki\n";
		}
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen("1.in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}