题目链接：点击打开链接
题目大意：略。
解题思路：数组大小定义为：2e6+10，数组大小与 n，m 是无关的，只与 cid 的最大值相关，算出对应的最多位数，比如：此题目中 cid 最大值为 1000000，对应的二进制位数最多 20位，根据完全二叉树的结点公式，最多 2^21-1。因为这里是边作为 二进制位，结点作为 链接下一个结点的下标。又因为题目说了是 cid^pid 最大的数，所以根据异或相同则0，不同则1的性质可知，只要是高位二进制各异就是最大的数了，所以 query 函数先尽量找与自己不一样的二进制，实在找不到的话，再选择自己的二进制位。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; int n,m,cnt; int trie[21*maxn][2]; int val[21*maxn]; void init() { cnt=0; mem(val,0); mem(trie,0); } void add(int cid) { int rt=0,id; for(int i=19;i>=0;i--) // 从 19 开始是因为从最高位开始操作 { id=(cid>>i)&1; if(!trie[rt][id]) trie[rt][id]=++cnt; // trie[rt][id] 不能等于 0，以免与初始化混淆 rt=trie[rt][id]; } val[rt]=cid; } int query(int pid) { int rt=0,id; for(int i=19;i>=0;i--) // 同上 { id=(pid>>i)&1; if(trie[rt][id^1]) rt=trie[rt][id^1]; else rt=trie[rt][id]; } return val[rt]; } int main() { while(~scanf("%d",&n)) { init(); int cid; for(int i=0;i<n;i++) { scanf("%d",&cid); add(cid); } scanf("%d",&m); int op,id; for(int i=0;i<m;i++) { scanf("%d%d",&op,&id); if(op) printf("%d\n",query(id)); else add(id); } } return 0; }
