洛谷 P8955 「VUSC」Card Tricks

// Problem: P8955 「VUSC」Card Tricks
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8955
// Memory Limit: 100 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

bool Mst;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 20], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    for (; !isdigit(c); c = getchar()) ;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

const int maxn = 1000100;

int n, m, K, a[maxn], ans[maxn];

struct i24 {
	unsigned char a, b, c;
	
	inline void set(int x) {
		a = x & 255;
		b = (x >> 8) & 255;
		c = (x >> 16) & 255;
	}
	
	inline int val() {
		return a + ((int)b << 8) + ((int)c << 16);
	}
} fa[30][maxn];

inline int find(int k, int x) {
	while (fa[k][x].val() != x) {
		int t = fa[k][fa[k][x].val()].val();
		fa[k][x].set(t);
		x = t;
	}
	return x;
}

void solve() {
	n = read();
	m = read();
	K = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		ans[i] = -1;
	}
	for (int j = 0; j < 30; ++j) {
		for (int i = 1; i <= n + 1; ++i) {
			fa[j][i].set((a[i] & (1 << j)) ? i + 1 : i);
		}
	}
	for (int t = 1, l, r, x; t <= m; ++t) {
		l = read();
		r = read();
		x = read();
		for (int j = 0; j < 30; ++j) {
			if ((~x) & (1 << j)) {
				continue;
			}
			for (int i = find(j, l); i <= r; i = find(j, i)) {
				a[i] |= (1 << j);
				if (a[i] > K && ans[i] == -1) {
					ans[i] = t;
				}
				fa[j][i].set(i + 1);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d ", ans[i]);
	}
}

bool Med;

int main() {
	fprintf(stderr, "%.2lf MB\n", (&Mst - &Med) / 1048576.);
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}