T3

Little09 · 2023-01-16 21:01:57 · 题解

考虑到每个数一定不会变小，即随时间单调不降。我们考虑对每个数算答案：找出所有该数涉及的操作，放到时间轴上，在时间轴上二分一下第一个超过 P 的时间。

具体地，我们可以用线段树实现这个事情。线段树第 i 个位置放的是第 i 次操作 or 上的值，如果第 i 次操作与该数无关，就放上 0。对于每个数在线段树上二分一下即可。由于第 i 的操作区间是 [l_i,r_i]，我们只要在 l_i 个数的时候加入这个操作，再第 r_i+1 个数的时候删除。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e6+5;
int n,q,p;
int a[N],b[N],s[N*4];
int t[N*2],h[N],val[N*2],nxt[N],cnt;
inline void add(int x,int y,int z)
{
    t[++cnt]=y,val[cnt]=z;
    nxt[cnt]=h[x],h[x]=cnt;
}

void update(int u,int l,int r,int x,int y)
{
    if (l==r)
    {
        s[u]=y;
        return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) update(u*2,l,mid,x,y);
    else update(u*2+1,mid+1,r,x,y);
    s[u]=s[u*2]|s[u*2+1];
}
int ask(int u,int l,int r,int x)
{
    if (l==r)
    {
        if ((x|s[u])<=p) return -1;
        return l; 
    }
    int mid=(l+r)>>1;
    if ((x|s[u*2])>p) return ask(u*2,l,mid,x);
    return ask(u*2+1,mid+1,r,x|s[u*2]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q >> p;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=q;i++) 
    {
        int l,r,x;
        cin >> l >> r >> x;
        b[i]=x;
        add(l,i,b[i]),add(r+1,i,0);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=h[i];j;j=nxt[j]) update(1,1,q,t[j],val[j]);
        cout << ask(1,1,q,a[i]) << " ";
    }
    return 0;
}

使用 zkw 线段树可以获得更小的常数，代码可以私信 5ab。