自动搬运

查看原文

来自洛谷，原作者为

	Little09 「按照我们原来的期待 去证明我们的未来」

搬运于2025-08-24 22:44:04，当前版本为作者最后更新于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。