[cf1261F]Xor-Set

构造一棵权值范围恰为$[0,2^{60})$的权值线段树，考虑其中从下往上第$h$层（$0\le h\le 60$）中的一个区间，假设其左端点为$l$，即$[l,l+2^{h})$

这样的一个区间具有一个很好的性质，其是按位独立的，即其等价于二进制下最高的$60-h$位与$l$相同，剩下的$h$位任意的数所构成的集合

对于这样的两个集合$[l_{1},l_{1}+2^{h_{1}})$和$[l_{2},l_{2}+2^{h_{2}})$合并的结果，也就是最高的$60-\max(h_{1},h_{2})$位与$l_{1}\oplus l_{2}$相同，剩下的$\max(h_{1},h_{2})$位任意的数所构成的集合，证明利用按位独立的性质分析即可

更具体的，合并结果对应于区间$[l_{3},l_{3}+2^{\max(h_{1},h_{2})})$，其中$l_{3}=(l_{1}\oplus l_{2})\and (2^{60}-2^{\max(h_{1},h_{2})}))$（后者的意义即取$l_{1}\oplus l_{2}$二进制下最高的$60-\max(h_{1},h_{2})$位）

考虑将$n_{a}$和$n_{b}$个区间分别插入线段树，划分为$\log V$个线段树上区间（即分别有$n_{a}\log V$和$n_{b}\log V$个区间），将其两两按上述方法合并，再对最终的区间快排，复杂度即$o(n^{2}\log^{3}V)$（其中$V$为值域，即$10^{18}$）

这样的复杂度是不能接受的，需要进行优化

对于这个合并的结果（不妨假设$h_{1}\ge h_{2}$），等价于$[l_{1},l_{1}+2^{h_{1}})$与$[l_{3},l_{3}+2^{h_{1}})$（其中$l_{3}=l_{2}\and(2^{60}-2^{h_{1}})$），在线段树上也就是$[l_{2},l_{2}+2^{h_{2}})$这个区间所对应的节点在从下往上第$h_{1}$层的祖先

（以$n_{a}$个区间为例）定义一个节点被标记即其是$n_{a}\log V$个区间中的一个，将所有节点分为三类：

1.其自身被标记

2.其自身未被标记且其子树内存在节点被标记

3.其子树内（包括自身）无节点被标记

类似地，对于$n_{b}\log V$个区间也可以得到节点类型，那么也就可以看作$n_{a}\log V$个区间中1类节点和$n_{b}\log V$个区间中的2类节点两两合并以及前者的2类节点和后者的1类节点两两合并

（关于原因可以参考前面的说明，也就是将所有节点先提到同一层）

对于这样的复杂度，分别考虑每一层第1类和第2类节点个数：

1.第1类节点，也就是被严格包含，但如果其与其兄弟同时被包含即不需要被插入，同时被包含的节点必然是连续若干个，那么至多两个（否则必然存在兄弟）

2.第2类节点，也就是线段树在递归过程中经过且未结束的节点，更具体的即有交点但不被包含，显然每一次插入后每一层至多新增两个（最左边和最右边）

综上，每一层两类的节点数都是$o(n)$的，那么每一层合并复杂度为$o(n^{2})$，总区间个数降为$o(n^{2}\log V)$，再对其排序复杂度即$o(n^{2}\log^{2}V)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 105

 4 #define mod 998244353

 5 #define ll long long

 6 #define mid (l+r>>1)

 7 #define pll pair<ll,ll>

 8 #define fi first

 9 #define se second

10 pll a[8*N*N*N];

11 vector<ll>v[4][N];

12 int V,rt,n,na,nb,ans,ls[4*N*N],rs[4*N*N];

13 ll m,x,y;

14 int sum(ll x,ll y){

15     int s1=(x+y)%mod,s2=(y-x+1)%mod;

16     return 1LL*s1*s2%mod*(mod+1)/2%mod;

17 }

18 void update(int p,int &k,ll l,ll r,ll x,ll y,int z){

19     if ((l>y)||(x>r))return;

20     if (!k)k=++V;

21     if ((x<=l)&&(r<=y)){

22         v[p][z].push_back(l);

23         return;

24     }

25     v[p+2][z].push_back(l);

26     update(p,ls[k],l,mid,x,y,z-1);

27     update(p,rs[k],mid+1,r,x,y,z-1);

28 }

29 int main(){

30     m=(1LL<<60)-1;

31     scanf("%d",&na);

32     for(int i=1;i<=na;i++){

33         scanf("%lld%lld",&x,&y);

34         update(0,rt,0,m,x,y,60);

35     }

36     scanf("%d",&nb);

37     for(int i=1;i<=nb;i++){

38         scanf("%lld%lld",&x,&y);

39         update(1,rt,0,m,x,y,60);

40     }

41     for(int i=0;i<=60;i++){

42         for(int j=0;j<v[0][i].size();j++)

43             for(int k=0;k<v[1][i].size();k++){

44                 x=(v[0][i][j]^v[1][i][k]);

45                 a[++n]=make_pair(x,x+(1LL<<i)-1);

46             }

47         for(int j=0;j<v[0][i].size();j++)

48             for(int k=0;k<v[3][i].size();k++){

49                 x=(v[0][i][j]^v[3][i][k]);

50                 a[++n]=make_pair(x,x+(1LL<<i)-1);

51             }

52         for(int j=0;j<v[1][i].size();j++)

53             for(int k=0;k<v[2][i].size();k++){

54                 x=(v[1][i][j]^v[2][i][k]);

55                 a[++n]=make_pair(x,x+(1LL<<i)-1);

56             }

57     }

58     sort(a+1,a+n+1);

59     ll s=0;

60     for(int i=1;i<=n;i++){

61         if (a[i].fi>s)ans=(ans+sum(a[i].fi,a[i].se))%mod;

62         else{

63             if (s<a[i].se)ans=(ans+sum(s+1,a[i].se))%mod;

64         }

65         s=max(s,a[i].se);

66     }

67     printf("%d",ans);

68 }

巴特西

[cf1261F]Xor-Set

最新文章

热门文章