CF979D Kuro and GCD and XOR and SUM

初始有一个空的集合，和 \(Q\) 个操作。对于每个操作，有两种类型，分别用如下的两种形式表示：

\(1\ u\) ：加入 \(u\) 到集合
\(2\ x\ k\ s\) ：求一个最大的 \(v\) ，使得:

1. \(v+x\leq s\)
2. \(k|gcd(v,x)\)
3. \(x \oplus v\) 最大

如果找不到满足条件的就输出 \(-1\) .

\(2\leq q\leq 10^5,1\leq u,x,k,s\leq 10^5\)

想了很久没有思路的一道题 . 是我 sbsbsb .

\(\oplus\) 想到什么，想到 \(\mathrm{01\ trie}\) 啊 . 这么普遍的套路我都忘了 qwq .

条件 \(2\) 相当于考虑把 \(k|v\) 并且 \(k|x\) . 此时想到对于每个数，从 \(1\) 到 \(10^5\) 都建立一个 \(\mathrm{trie}\) 树，可以在插入 \(u\) 的时候将 \(u\) 插入到每一个因数的 \(\mathrm{trie}\) 树中，然后每个节点还需要维护一个最小值 \(mn(i)\) ，对付询问 \(1\) . 询问的时候在 \(k\) 的 \(\mathrm{trie}\) 树直接可以找到答案 .

时间复杂度 : \(O(q\log^2 n)\)

空间复杂度 : \(O(n\log n)\)

code

#include
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline int rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(int res){
	if(res==0){putchar('0');return;}
	static int out[10];int len=0;
	if(res<0)putchar('-'),res=-res; 
	while(res>0)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
const int inf=1e9+10;
const int N=1e5+10;
class trie{
public:
	int cnt=0;
	vector >t;
	vectormn;
	void init(){
		t.push_back(MP(-1,-1));
		mn.push_back(inf);
		cnt++;
	}
	inline int new_node(){
		t.push_back(MP(-1,-1));
		mn.push_back(inf);
		return cnt++;
	}
	void upd(int val){
		int x=0;
		for(int i=16;i>=0;i--){
			mn[x]=min(mn[x],val);
			if(val&(1<=0;i--){
			if(t[x].FI==-1&&t[x].SE==-1)return -1;
			if(mn[x]+val>s)return -1;
			if(val&(1<