洛谷 P4883 mzf的考验 简易题解【fhq treap】

发表于 更新于 分类于

题目传送门：洛谷 P4883 mzf的考验

想法

引入

$\ \ \ \ \ \ \,$首先我们看他的操作：

  • $opt==1$：两个正整数：$l$，$r$。请翻转区间$[l,r]$；
  • $opt==2$：三个正整数：$l$，$r$，$d$。请将区间$[l,r]$中的所有卦象都异或卦象$d$;
  • $opt==3$：两个正整数：$l$，$r$。请查询区间$[l,r]$的卦象权值和。

解法

$\ \ \ \ \ \ \,$显然是一个平衡树可以做的啦，我们试着选择$Fhq_treap$ 做一下：

$\ \ \ \ \ \ \,$对于操作 $1$，$3$ 操作很简单，我们 $pushup$ 一下子树和， $pushdown$ 一下旋转标记，提出区间 $[l,r]$ 进行对应的操作就可以了。

$\ \ \ \ \ \ \,$那么对应的 $2$ 操作似乎没有那么简单操作了，我们先看看我们需要修改的 $pushdown$ 操作是什么：

  1. 单点权值$(val)$：直接异或上修改的值，在$pushdown$操作的时候同理。
  2. 权值懒人标记$(lazy_w)$：直接异或上修改的值，在$pushdown$操作的时候同理。
  3. 子树和$(sum)$：？

$\ \ \ \ \ \ \,$可以发现子树和的处理特别麻烦，但是对于异或问题，我们通常可以拆位解决，对于每一个节点，我们新开一个数组 $num[i]$ ，表示这个子树内的值，数位 $i$ 上面为 $1$ 的值是多少，这个很显然，我们可以通过 $pushup$ 一并传递上去。

$\ \ \ \ \ \ \,$如何处理子树和呢？因为打了标记的子树都要异或这一个值，所以我们把这个值拆了，如果这一位为 $1$ ，那么子树这一位都会 $1$变$0$，$0$变$1$，所以说有：

$num[i]=size-num[i]$

$\ \ \ \ \ \ \,$其中$size$为子树大小，修改了$num$数组之后，我们就可以重新计算子树和了：

$sum=\sum_{i=0}^{limit}2^i\times num[i]$

$\ \ \ \ \ \ \,$所以 $pushup$ 和 $pushdown$ 差不多应该是这样的：

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
void Xor(int rt,int x){
	lazy_w[rt]^=x;val[rt]^=x;
    sum[rt]=0;
	for(int i=0;i<=20;++i)tmp[i]=(x>>i)&1;
  	for(int i=0;i<=20;++i){
      	if(tmp[i])num[rt][i]=size[rt]-num[rt][i];
      	sum[rt]+=(1ll<<i)*num[rt][i];
    }
}
void pushup(int rt){
	size[rt]=size[lson]+size[rson]+1;
	sum[rt]=sum[lson]+sum[rson]+1ll*val[rt];
	for(int i=0;i<=20;i++)
	num[rt][i]=num[lson][i]+num[rson][i]+((val[rt]>>i)&1);
}
void pushdown(int rt){
	if(lazy[rt]){
		swap(lson,rson);
		if(lson)lazy[lson]^=1;
		if(rson)lazy[rson]^=1;
		lazy[rt]=0;
	}
	if(lazy_w[rt]){
		int x=lazy_w[rt];lazy_w[rt]=0;
		if(lson){Xor(lson,x);}
		if(rson){Xor(rson,x);}
	}
}

$\ \ \ \ \ \ \,$总期望复杂度应该是$O(n\log n\ limit)$，其中$limit=\log val$

$\ \ \ \ \ \ \,$懒得卡常了，吸氧过：

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
	if(f)return x;else return -x;
}
const int N=1e5+10;
struct fhq_treap{
	#define lson ls[rt]
	#define rson rs[rt]
	int ls[N],rs[N];
	bool lazy[N];
	int lazy_w[N],val[N],key[N],size[N];
	long long sum[N];
	int root,cnt;
	int tmp[25],num[N][25];
	void Xor(int rt,int x){
		lazy_w[rt]^=x;val[rt]^=x;
    	sum[rt]=0;
		for(int i=0;i<=20;++i)tmp[i]=(x>>i)&1;
  		for(int i=0;i<=20;++i){
      		if(tmp[i])num[rt][i]=size[rt]-num[rt][i];
      		sum[rt]+=(1ll<<i)*num[rt][i];
    	}
	}
	void pushup(int rt){
		size[rt]=size[lson]+size[rson]+1;
		sum[rt]=sum[lson]+sum[rson]+1ll*val[rt];
		for(int i=0;i<=20;i++)
		num[rt][i]=num[lson][i]+num[rson][i]+((val[rt]>>i)&1);
	}
	void pushdown(int rt){
		if(lazy[rt]){
			swap(lson,rson);
			if(lson)lazy[lson]^=1;
			if(rson)lazy[rson]^=1;
			lazy[rt]=0;
		}
		if(lazy_w[rt]){
			int x=lazy_w[rt];lazy_w[rt]=0;
			if(lson){Xor(lson,x);}
			if(rson){Xor(rson,x);}
		}
	}
	int merge(int a,int b){
		if(!a||!b)return a|b;
		if(key[a]<key[b]){pushdown(a);rs[a]=merge(rs[a],b);pushup(a);return a;}
		else {pushdown(b);ls[b]=merge(a,ls[b]);pushup(b);return b;}
	}
	void split(int rt,int x,int &a,int &b){
		if(!rt){a=b=0;return;}
		pushdown(rt);
		if(x<=size[lson]){b=rt;split(lson,x,a,lson);}
		else {a=rt;split(rson,x-size[lson]-1,rson,b);}
		pushup(rt);
	}
	int newnode(int x){
		int rt=++cnt;
		size[rt]=1;val[rt]=x;key[rt]=rand();
		lazy[rt]=0;lazy_w[rt]=0;
		lson=rson=0;
		return rt;
	}
	int build(int a[],int len){
		stack<int> S;
		int rt,last;
	  	for(int i=1;i<=len;i++){
	    rt=newnode(a[i]);last=0;
	    while(!S.empty()&&key[S.top()]>key[rt])
			pushup(last=S.top()),S.pop();
	    	if(!S.empty())rs[S.top()]=rt;
	    	lson=last;S.push(rt);
	  	}
	  	while(!S.empty())pushup(last=S.top()),S.pop();
	  	return last; 
	}
	void Revers(int l,int r){
		int a,b,c;
		split(root,r,a,c);
		split(a,l-1,a,b);
		lazy[b]^=1;
		root=merge(merge(a,b),c);
	}
	void Update(int l,int r,int d){
		int a,b,c;
		split(root,r,a,c);
		split(a,l-1,a,b);
		Xor(b,d);
		root=merge(merge(a,b),c);
	}
	long long Query(int l,int r){
		int a,b,c;
		split(root,r,a,c);
		split(a,l-1,a,b);
		long long ret=sum[b];
		root=merge(merge(a,b),c);
		return ret;
	}
}Tree;
int n,m;
int a[N],op,l,r,d;
int main()
{
	srand(time(NULL));
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	Tree.root=Tree.build(a,n);
	while(m--){
		op=read();l=read();r=read();
		if(op==1)Tree.Revers(l,r);
		if(op==2)d=read(),Tree.Update(l,r,d);
		if(op==3)cout<<Tree.Query(l,r)<<endl;
	}
	return 0;
}