本题链接:CF972 D. Kuro and GCD and XOR and SUM

题目大意

有\(n\)个询问,每个询问形如如下两种:

• 增加一个数\(x\)到一开始为空的序列中.
• 给定三个参数\(x,k,s\).要求在序列找一个数\(v\)满足\(k | gcd(x,v)\),\(x + v \leq s\),\(x \oplus v\)最大.如果不存在这样的\(v\)则输出\(-1\).

数据范围:

\(1 \leq q \leq 10^5\)

\(1 \leq x,k,s \leq 10^5\).

思路

显然\(gcd\)这个条件的约束性可比什么求和强多了,先对这玩意下手.注意到\(k | gcd(x,v)\)事实上跟一般的条件不大一样,他其实只是满足:\(k | x\)以及\(k | x\)而已.所以对于每个询问可以先排除掉一种无解情况:即\(x\)不是\(k\)的倍数的时候.接下来其实只用找\(k\)的倍数\(v\)了.

不过有一点需要分开讨论:如果\(k=1\)此时的倍数太多了,所以我们不妨只讨论\(k=1\)的情况以及\(k\neq 1\)的情况:

• 若\(k=1\),那么必然有\(k|v\),此时只需要找一个在序列里面的数\(v\)满足\(x+v\leq s\)就可以满足有解的存在了,之后就需要满足\(x \oplus v\)最大,这个可以用一个Trie来做,模型还是比较典型的插入数以及查询.那么为了满足不等式条件,我们只需要对每个在Trie上的点额外打一个最小值标记表示在这个点下最小的值是多少,如果最小值标记都不能满足不等式关系,那么说明:在这个点之下无论在怎么去找都找不到一个合法的点了,只能尝试另外一边的点是否合法,如果都走不通就说明不存在点.贪心去找就可以了.
• 枚举\(z=k\)的若干倍,满足\(z+x \leq s\).在这种情况下,我们只需要查询在Trie上是否存在着这个\(z\)就可以了.更新最大的异或值,维护对应的答案即可.

(感觉复杂度有点玄幻)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 1e5+7,M = 24;
int tr[N * M][2],idx,dwtag[N * M];

void insert(int v)
{
	int p = 0;
	for(int i = M;i >= 0;--i)
	{
		int k = v >> i & 1;
		if(!tr[p][k])	tr[p][k] = ++idx;
		p = tr[p][k];
		dwtag[p] = min(v,(dwtag[p] == 0 ? v : dwtag[p]));
	}
}

int query(int x,int limit)
{
	int p = 0;
	for(int i = M;i >= 0;--i)
	{
		int o = tr[p][x >> i & 1],r = tr[p][!(x >> i & 1)];
		if(dwtag[o] + x > limit && dwtag[r] + x > limit) return -1;
		if(dwtag[r] + x <= limit)	p = r;
		else p = o;
	}
	return dwtag[p];
}

int query(int x)
{
	int p = 0;
	for(int i = M;i >= 0;--i)
	{
		p = tr[p][x >> i & 1];
		if(!p)	return 0;
	}	
	return p;
}

int main() 
{
	dwtag[0] = 1e9;
	int q;scanf("%d",&q);
	while(q--)
	{
		int t;scanf("%d",&t);
		if(t == 1)
		{
			int x;scanf("%d",&x);
			insert(x);
		}
		else
		{
			int x,k,s;scanf("%d%d%d",&x,&k,&s);
			if(x % k)	puts("-1");
			else
			{
				if(k == 1)	printf("%d\n",query(x,s));
				else
				{
					int resx = -1e9,resv = -1;
					for(int z = k;x + z <= s;z += k)
						if(query(z))
						{
							if((z ^ x) > resx)
							{
								resx = z ^ x;
								resv = z;
							}
						}
					printf("%d\n",resv);
				}
			}
		}
	}
	return 0;
}