NKOJ 3652 shallot （线性基+CDQ分治）

发表于 |
字数统计: 1,029字 | 阅读时长 ≈ 5min

P3652 shallot

问题描述

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。
每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为OI选手的你，你能帮帮他吗？
你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出嬰。

输入格式

输入第一行一个正整数T，表示测试数据组数。
对于每组数据，
第一行两个正整数n表示总时间；
第二行n个整数a1; a2; …; an，若ai大于0代表给了小葱一颗数字为ai的小葱
苗，否则代表从小葱手中拿走一颗数字为ai的小葱苗。

输出格式

输出共n行，每行一个整数代表第i个时刻的最大异或和

样例输入

6
1 2 3 4 -2 -3

样例输出

1
3
3
7
7
5

提示

n<=500000,ai<=2^31-1

求从一些数中选取若干个的最大异或和，可以用线性基来做，求出这些数的一组基即可知道答案。

但是线性基只支持插入而不支持删除，因此采用CDQ分治来维护。
预处理出每个数存在的区间$[L,R]$，对时间分治，每次将存在区间与分治子区间无交的数字插入到子区间的线性基中。底层的线性基就是$[L,L]$时刻的答案。

实际实现时，对于每个添加，找到它对应的删除位置，同样对每个删除找到对应的添加位置，然后将在左子区间添加且删除位置在右区间右边的数插入到右区间，将在右区间删除且添加位置在左区间左边的数插入到左区间，然后递归处理。

并不需要每个区间都维护一个线性基，而只需要每一层分治维护一个线性基，回溯的时候将上一层的copy到下一层再插入即可。

时间复杂度$O(n log^2n)$

事实上也可以预处理完了之后直接用线段树维护每个位置的线性基，同样只有插入操作，复杂度也一样。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#define N 543210
using namespace std;
struct node
{
	int cnt,c[32];
	void Ins(int x)
	{
		for(int i=1;i<=cnt;i++)
		if((x^c[i])<x)x^=c[i];
		if(x)c[++cnt]=x;
	}
	int Gans()
	{
		int sum=0;
		for(int i=1;i<=cnt;i++)
		if((sum^c[i])>sum)sum^=c[i];
		return sum;
	}
};
int n,a[N],ST[N],EN[N],ans[N];
node s[99];
map<int,int>fa,ct;
void CDQ(int l,int r,int x)
{
	if(l==r)
	{
		if(a[l]>0)s[x].Ins(a[l]);
		ans[l]=s[x].Gans();
		return;
	}
	int mid=l+r>>1,i;
	s[x+1]=s[x];
	for(i=mid+1;i<=r;i++)
	if(a[i]<0&&ST[i]<=l)s[x+1].Ins(-a[i]);
	CDQ(l,mid,x+1);
	s[x+1]=s[x];
	for(i=l;i<=mid;i++)
	if(a[i]>0&&EN[i]>r)s[x+1].Ins(a[i]);
	CDQ(mid+1,r,x+1);
}
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
	{
		if(a[i]>0)
		{
			ct[a[i]]++;
			if(ct[a[i]]==1)fa[a[i]]=i;
			else a[i]=0;
		}
		else
		{
			ct[-a[i]]--;
			if(!ct[-a[i]])
			{
				ST[i]=fa[-a[i]];
				EN[fa[-a[i]]]=i;
			}
			else a[i]=0;
		}
	}
	for(i=1;i<=n;i++)
	if(a[i]>0&&!EN[i])EN[i]=n+1;
	CDQ(1,n,0);
	for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}