折半搜索玄关求条

#include <bits/stdc++.h>
using namespace std;
int a[200005], tr[200005], n, m, v, b[15], c[7005];
int lb(int x) { return x & (-x); }
int qpow(int a, int b, int p) {
	int c = 1;
	while(b) {
		if(b & 1) c = (c * a) % p;
		a = (a * a) % p; b >>= 1;
	} return c;
} void upd(int x, int d) {
	while(x <= n) tr[x] += d, x += lb(x);
} int qry(int x) { int s = 0;
	while(x) s += tr[x], x -= lb(x); return s;
} int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> v; int p = v, q = v; 
	for(int i = 2;i * i <= v;i++)
		if(v % i == 0) {
			p = p / i * (i - 1);
			while(v % i == 0) v /= i;
		}
	if(v > 1) p = p / v * (v - 1);
	for(int i = 1;i <= n;i++) cin >> a[i];
	while(m--) {
		int opt, l, r; cin >> opt >> l >> r;
		if(opt == 2) upd(l, 1), upd(r, -1);
		else {
			if(l == r) { cout << "Yuki\n"; continue; }
			if((r - l + 1) >= 13) {
				cout << "Yuno\n"; continue;
			} int k = r - l + 1;
			for(int i = 1;i <= k;i++) {
				int x = qpow(3, qry(i + l - 1), q);
				int t = (x < p ? x : x % p + p);
				b[i] = qpow(a[i], t, q);
			} int s = k / 2, cur = 0; //左边 1 ~ s，右边 s + 1 ~ k
			for(int i = 1;i < pow(3, s);i++) {
				int x = i, s1 = 0, s2 = 0;
				for(int j = 1;j <= s;j++) {
					int d = x % 3;
					if(d == 1) s1 += b[j] + 1;
					else if(d == 2) s2 += b[j] + 1;
					x /= 3;
				} c[i] = abs(s1 - s2); cur++;
			} sort(c+1, c+cur); bool f = 0;
			for(int i = 1;i < pow(3, k - s);i++) {
				int x = i, s1 = 0, s2 = 0;
				for(int j = 1;j <= k - s;j++) {
					int d = x % 3;
					if(d == 1) s1 += b[j + s] + 1;
					else if(d == 2) s2 += b[j + s] + 1;
					x /= 3;
				} int y = abs(s1 - s2);
				int z = *lower_bound(c+1, c+cur, y);
				if(y == z) { f = 1; break; }
			} cout << (f ? "Yuno" : "Yuki") << "\n";
		}
	}
	return 0;
}