题解：P8955 「VUSC」Card Tricks

前言

在练习整体二分的时候找到了这道，~~大力卡常后~~过了，顺便写篇题解。

思路

由于一个数或上另一个数，其结果必然不小于原数，所以满足单调性。

先想对于单个

a_x

如何二分求解。

设当前二分的区间为

[L,R]

（下文令

mid=\displaystyle{\lfloor \frac{L+R}{2} \rfloor}

）：

对于操作区间 $[L,mid]$ ，计算 $k=\bigvee_{i=L}^{mid}[l_i \le x][x \le r_i]v_i$ （即对于每个 $l_i \le x \le r_i$ 的区间，将它们的 $v_i$ 或起来）。
若 $a_x \vee k > p$ ，在左半区间继续查找，否则令 $a_x \larr a_x \vee k$ ，在右半区间继续查找。

对于多个

a_i

，我们需要进行多次二分，显然这是不可取的。

考虑整体二分，则我们需要快速对一个区间进行或运算，查询单点权值，可以使用线段树。

值得一提的是，这道题只需要单点查询，因此可以使用一个类似于标记永久化的方法，如果在区间取或的递归过程中，当前区间被需要操作的区间完全覆盖，则在该区间打上或标记，查询时一路向下求标记或起来的和即可。

~~还有这道题需要卡常，笔者卡了很久才从 90pts 到 100pts~~。

代码：

CPP

#include<bits/stdc++.h> 
using namespace std;
const int N=1e6+5;
namespace SGT{
	#define L (x<<1)
	#define R (x<<1|1)
	int l[N<<2],r[N<<2];
	int tag[N<<2];
	inline void build(int x,int lq,int rq){
		l[x]=lq;
		r[x]=rq;
		tag[x]=0;
		if(lq==rq)return;
		const int mid=lq+rq>>1;
		build(L,lq,mid);
		build(R,mid+1,rq);
	}
	inline void modify(int x,int lq,int rq,int k){
		if(lq<=l[x]&&r[x]<=rq){
			if(k)tag[x]|=k;
			else tag[x]=0;//便于快速清空线段树
			return;
		}
		const int mid=l[x]+r[x]>>1;
		if(lq<=mid)modify(L,lq,rq,k);
		if(rq>mid)modify(R,lq,rq,k);
	}
	inline int query(int x,int i){
		if(l[x]==r[x])return tag[x];
		const int mid=l[x]+r[x]>>1;
		int res=tag[x];
		if(i<=mid)res|=query(L,i);
		else res|=query(R,i);
		return res;
	}
	#undef L
	#undef R
}
using SGT::build;
using SGT::modify;
using SGT::query;

int q[N],ql[N],qr[N];
int n,Q,p,a[N];
int l[N],r[N],k[N];
int ans[N];

//整体二分板子
inline void solve(int vaL,int vaR,int lq,int rq){
	if(lq>rq)return;
	if(vaL==vaR){
		for(int i=lq;i<=rq;++i)
			ans[q[i]]=vaL;
		return;
	}
	const int mid=vaL+vaR>>1;
	int cntl=0,cntr=0;
	for(int i=vaL;i<=mid;++i)
		modify(1,l[i],r[i],k[i]);
	for(int i=lq;i<=rq;++i){
		const int k=query(1,q[i]);
		if((k|a[q[i]])>p){
			ql[++cntl]=q[i];
		}else{
			a[q[i]]|=k;
			qr[++cntr]=q[i];
		}
	}
	for(int i=vaL;i<=mid;++i)
		modify(1,l[i],r[i],0);//清空线段树
	for(int i=1;i<=cntl;++i)
		q[lq+i-1]=ql[i];
	for(int i=1;i<=cntr;++i)
		q[lq+cntl+i-1]=qr[i];
	solve(vaL,mid,lq,lq+cntl-1);
	solve(mid+1,vaR,lq+cntl,rq);
}

template<typename T>
inline void read(T &x){
    char c;
    x=0;
    int fu=1;
    c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')fu=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x*=fu;
}
template<typename T>
inline void print(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

int main(){
	read(n);read(Q);read(p);
	for(register int i=1;i<=n;++i){
		read(a[i]);
		q[i]=i;
	}
	for(register int i=1;i<=Q;++i){
		read(l[i]);read(r[i]);read(k[i]);
	}
	build(1,1,n);
	solve(1,Q+1,1,n);
	for(register int i=1;i<=n;++i){
		if(ans[i]>Q)print(-1);
		else print(ans[i]);
		printf(" ");
	}
	return 0;
}

题解：P8955 「VUSC」Card Tricks

文章操作

前言

思路

代码：

相关推荐

评论

题解：P8955 「VUSC」Card Tricks