Ynoi2012 NOIP2016 人生巅峰

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;
}