题解：P8955 「VUSC」Card Tricks

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
int n,q,P,dat[N];
vector<pair<int,int> > pos[N];
namespace SegmentTree{
	int sum[N << 2];
	void update(int p,int pos,int val,int l,int r){
		if(l == r){
			sum[p] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid){
			update(p << 1,pos,val,l,mid);
		}else{
			update(p << 1 | 1,pos,val,mid + 1,r);
		}
		sum[p] = (sum[p << 1] | sum[p << 1 | 1]);
	}
	int query(int p,int l,int r,int k){
		if((sum[p] | k) <= P){
			return -1;
		}
		if(l == r){
			return l;
		}
		int mid = (l + r) >> 1;
		if((sum[p << 1] | k) > P){
			return query(p << 1,l,mid,k);
		}else{
			return query(p << 1 | 1,mid + 1,r,(k | sum[p << 1]));
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> P;
	for(int i = 1;i <= n;i ++){
		cin >> dat[i];
	}
	for(int i = 1;i <= q;i ++){
		int l,r,k;
		cin >> l >> r >> k;
		pos[l].push_back({i,k});
		pos[r + 1].push_back({i,0});
	}
	for(int i = 1;i <= n;i ++){
		for(pair<int,int> p : pos[i]){
			int id = p.first,val = p.second;
			SegmentTree::update(1,id,val,1,q);
		}
		cout << SegmentTree::query(1,1,q,dat[i]) << " ";
	}
	return 0;
}