01trie特训2

题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。

debug：我自己实现不好写的原因是没开第二个后缀异或和，在那一直用前缀和偏移位置，边界不好处理。

//trie树 + 前缀异或和 + 枚举
#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 2e5 + 10;
int a[N], ls[N], rs[N], lmax[N], lmin[N], rmax[N], rmin[N];
int n;
int ltre[1 << 22][3], rtre[1 << 22][3],  cnt;

void add(int x, int tre[][3]){
	int p = 0;	
	for(int i = 20; i >= 0; i --){
		int bit = (x >> i) & 1;
		if(tre[p][bit])
			p = tre[p][bit];
		else
		{
			tre[p][bit] = ++ cnt;
			p = tre[p][bit];
		}
	}
	return;
}

int query_max(int x, int tre[][3]){
	int res = 0, p = 0;
	for(int i = 20; i >= 0; i --){
		int bit = (x >> i) & 1;
		if(tre[p][!bit]){
			p = tre[p][!bit];
			res += (1 << i);
		}else{
			p = tre[p][bit];
		}
				
	}
	return res;	
}

int query_min(int x, int tre[][3]){
	int res = 0, p = 0;
	
	for(int i = 20; i >= 0; i --){
		int bit = (x >> i) & 1;
		if(tre[p][bit]){
			p = tre[p][bit];
		}else{
			p = tre[p][!bit];
			res += (1 << i);
		}	
	}
	return res;
}

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}

	for(int i = 0; i <= n + 1; i ++){
		lmax[i] = rmax[i] = 0;
		lmin[i] = rmin[i] = INF;
	}

    add(0, ltre);

	for(int i = 1; i <= n; i ++){
		ls[i] = ls[i - 1] ^ a[i];
		lmax[i] = max(lmax[i - 1], query_max(ls[i], ltre));

		lmin[i] = min(lmin[i - 1], query_min(ls[i], ltre));
		
		add(ls[i], ltre);
	}

	cnt = 0;
	add(0, rtre);
	for(int i = n; i >= 1; i --){
		rs[i] = rs[i + 1] ^ a[i];
		rmax[i] = max(rmax[i + 1], query_max(rs[i], rtre));
		rmin[i] = min(rmin[i + 1], query_min(rs[i], rtre));
		add(rs[i], rtre);
	}

	int ans = 0;
	for(int i = 1; i <= n - 1; i ++){
		ans = max(ans, max(lmax[i] - rmin[i + 1], rmax[i + 1] - lmin[i]));
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}

https://www.luogu.com.cn/problem/U109923给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$，选定四个整数 $l_1,r_1,l_2,r_2(1\le l_1\le r_1<l_2\le r_2\le n)$，则函数 $\operatorname{F}(l_1,r_1,l_2,r_2)$ 的计算方式如下：

$$\operatorname{F}(l_1,r_1,l_2,r_2)=(a_{l_1}\oplus a_{l_1+1} \oplus \cdots \oplus a_{r_1})+(a_{l_2}\oplus a_{l_2+1} \oplus \cdots \oplus a_{r_2})$$

对于所有符合条件的 $(l_1,r_1,l_2,r_2)$ ,求 $\operatorname{F}(l_1,r_1,l_2,r_2)$ 的最大值。

Sol:上面的题和这个题非常像，这个维护和最大的非常直接，我们还是枚举分界点，固定端点求前缀异或和的单点最大值，再更新成前缀后缀最大值。后缀完全不需要特殊处理，直接对称的从后往前做异或和，并更新，没有顺序问题。

int a[N];
int ch[N*31][2], idx;

void insert(int x){
  int p=0;
  for(int i=30; i>=0; i--){
    int j=x>>i&1; //取出第i位
    if(!ch[p][j])ch[p][j]=++idx;
    p=ch[p][j];
  }
}
int query(int x){
  int p=0,res=0;
  for(int i=30; i>=0; i--){
    int j=x>>i&1;
    if(ch[p][!j]){
      res += 1<<i; //累加位权
      p=ch[p][!j];
    }
    else p=ch[p][j];
  }
  return res;
}
int l[N],r[N];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int sum=0;insert(sum);
	for(int i=1;i<=n;i++){
		sum^=a[i];
		insert(sum);
		l[i]=max(l[i-1],query(sum));
	}
	memset(ch,0,sizeof ch);
	idx=0;sum=0;
	insert(0);
	//本质上是后缀异或和之间找匹配最大
	for(int i=n;i>=1;i--){
		sum^=a[i];
		//insert(sum);//由于后缀和不能超出边界，所以我们要注意处理插入时机
		r[i]=max(r[i+1],query(sum));
		insert(sum);
	}
	int ans=0;
	for(int i=1;i<=n-1;i++){
		ans=max(ans,l[i]+r[i+1]);
	}
	cout<<ans<<endl;
}

有一个初始为空的可重集 $S$。现在有 $Q$ 次操作，每次操作有 $3$ 种类型，分别是：

  • $1,p_i$，把 $p_i$ 加入 $S$。

  • $2,p_i$，将 $p_i$ 从 $S$ 中删除，保证在删除前 $p_i$ 已经在 $S$ 中。

  • $3,p_i,l_i$，询问 $S$ 中有多少个数按位异或上 $p_i$ 的结果小于 $l_i$。

Choosing The Commander - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Sol：对于前两个操作只需要开一个数组，每次在树上走的时候维护标记。对于第三个操作有点像在线段树二分上的感觉，都是计算一边的答案，然后递归到另一边。

具体来说，我们在$l_{i}$的某位为1的时候才有机会让某些数$\oplus p_{i}$使得其小于$l_{i}$,所以我们要在每一个节点上维护当前左右儿子的节点数量。

int tot=0;
int t[N*31][2];
int num[N*31];
int l,ans;
void insert(int x){
	int u=0;
	for(int i=30;i>=0;i--){
		//cerr<<u<<" ";
		bool op=(x&(1<<i));
		if(!t[u][op])t[u][op]=++tot;
		u=t[u][op];
		num[u]++;
	}
	//cerr<<endl;
}
void del(int x){
	int u=0;
	for(int i=30;i>=0;i--){
		//cerr<<u<<" ";
		bool op=(x&(1<<i));
		u=t[u][op];
		num[u]--;
	}
	//cerr<<endl;
}
void ask(int x){
	int u=0; ans=0;
	for(int i=30;i>=0;i--){
		//cerr<<u<<" ";
		bool op=(x&(1<<i));
		bool pp=(l&(1<<i));
		if(pp==1){
//在当前子树节点下都是前面和x相同的
//现在L是1，是贡献的时机，前面一直不能超过他且也不能走相反方向
//当前x如果走与自己相同的部分，会出现0，这段子树的数都比k小，累加答案
//然后走与自己相反的路，异或起来是1保证高位到这位都与L相同，未来有潜力贡献
		ans+=num[t[u][op]];
		u=t[u][op^1]; 
		}
		else{
			//在没有出现机会之前，一直走的是x的路线，也就是说一旦后面
			//选择某一位和x不同做贡献，前面全部抑或掉一定小于L
			u=t[u][op];//这里求小于它的数，所以前面也要保证一样
			//由于为0的时候不贡献，所以为0的时候我们只需要让异或为0
			//也就是x走树上和自己节点相同的节点，这样异或起来是0
			//和L保证一致
		}
		if(!u)break;
	}
	//cerr<<endl;
}
void solve(){
	int q;cin>>q;
	while(q--){
		int op,p;cin>>op>>p;
		if(op==1)insert(p);
		else if(op==2)del(p);
		else {
			cin>>l;
			ask(p);
			cout<<ans<<endl;
		}
	}
      
}

Tokitsukaze 有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$。 https://ac.nowcoder.com/acm/contest/67742/C

她想知道有多少种序列 $b_1, b_2, \ldots, b_m$，满足：

  • $1 \leq b_i \leq n$
  • $b_{i-1} < b_i$ $(2 \leq i \leq m)$
  • $\min(a_{b_1}, a_{b_2}, \ldots, a_{b_m}) \oplus \max(a_{b_1}, a_{b_2}, \ldots, a_{b_m}) \leq k$

有了前面的铺垫看这个题就觉得还行了，先给出官方题解

Sol：由于求的是子序列，套路的，我们可以对 $a$ 进行排序。 排序后发现，当 $max=a_i,min=a_j$ 时，中间数可以随便选，如果这组 min 与 max 满足条件，那么答案是 $2^{i-j-1}$，特别的，当 $i=j$ 时，答案是 $1$。 但这个做法既要枚举 min 又要枚举 max，是 $O(n^2)$ 的。遇到这种情况，优化思路大多都是枚举一个，快速查询另一个。由于条件是异或，我们考虑 01字典树 (01 Trie)。把比当前枚举的 $a_i$ 小的数全部插入进 Trie 里，这样每次就能在 $O(\log n)$ 的时间复杂度内求出所有满足条件的 min 的信息。 此时又有新的问题：怎么用 Trie 维护答案信息呢？ 对于一个 $a_j$，它贡献的答案为 $2^{i-j-1}$。我们可以将这个式子拆掉： $2^{i-j-1}=\dfrac{2^{i-1}}{2^{j}}$，于是 $i$ 与 $j$ 就分离了。所以我们可以把 $v_i = \dfrac {1} {2^{i}}$ 插入 。当 $max=a_i$ 时，在 Trie 中查询 $\sum v_j$, $(a_j \oplus a_i \leq k)$，此时贡献为 $1 + 2^{i-1} \cdot \sum v_j$。 $2^i$ 与 $\dfrac {1}{2^i}$ 都可以预处理求出 （$\dfrac {1}{2^i}$ 要用到逆元）。然后枚举 max，每次在 Trie 中查询，总时间复杂度为 $O(n \log n)$。

我的理解：每个节点维护记录的的不再是简单的数量，而是分离变量以后的贡献函数。

  • 注意全局变量与局部变量重名可能会出大问题，避免。
  • 多测数据下如何清空01trie，根据idx用到哪清理到哪。

debug:init函数中用到变量n，但n首先是变化的并且还没输入呢。所以应该直接给边界常量。

int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int n, m;
int a[N];
int idx=0;
int pw[N];
int inv[N];
int ch[N*30][2];
int num[N*30];
void init(){
	pw[0]=1;
	pw[1]=2;
	inv[1]=qmi(2,mod-2);
	for(int i=2;i<=200000;i++){
		pw[i]=pw[i-1]*2%mod;
		inv[i]=inv[i-1]*inv[1]%mod;
		
	}
}


void insert(int x,int y){
	int p=0;
	for(int i=29;i>=0;i--){
		int u=(x>>i)&1;
		if(!ch[p][u])ch[p][u]=++idx;
		p=ch[p][u];
		num[p]=(num[p]+y)%mod;
	}
}
int query(int x){
	int res=0;
	int p=0;
	for(int i=29;i>=0;i--){
			int u=(x>>i)&1;
			int r=(m>>i)&1;
			if(r==1){
				res+=num[ch[p][u]];res%=mod;
				p=ch[p][!u];
			}
			else {
				p=ch[p][u];
			}
			if(p==0)break;
	}
	res+=num[p];
	res%=mod;
	return res;
}
void solve(){
   cin>>n>>m;
   
   for(int i=1;i<=n;i++)cin>>a[i];
   sort(a+1,a+1+n);
   int ans=0;
   //for(int i=1;i<=n;i++)cerr<<a[i]<<" ";cerr<<endl;
  // for(int i=1;i<=10;i++)cerr<<pw[i]<<" "<<inv[i]<<endl;
   for(int i=1;i<=n;i++){
   	 ans=(ans+1+pw[i-1]*query(a[i])%mod)%mod;
   	 insert(a[i],inv[i]);
   }
   cout<<ans<<endl;
  //每次结束用到哪就清空多少
  for(int i=0;i<=idx;i++)ch[i][1]=ch[i][0]=num[i]=0;
  idx=0;
  
}