题解：P8955 「VUSC」Card Tricks

Bobi2014 · 2025-10-25 16:19:55 · 题解

这是一道可癌的毒瘤数据结构题。

前置知识

• 线段树

思路

我们考虑在线段树上二分，线段树维护 1 到 Q 的修改的异或和，我们遍历每个点，在线段树上二分异或的次数。

那么我们如何才能知道那些修改对那些点有效呢，我们可以创建 n 个 vector，每个操作其实就是在第 l 个 vector 中加入，在第 r + 1 个 vector 中删除。

时间复杂度 O(n \log n)。

Code

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