test20191218

发表于

闲扯

大家 $T1$ 怎么都会写 $O(n\log ^2 n)$ 的算法啊，为啥我只会写带 $\sqrt{n}$ 的莫队啊。。

题面

2020WC集训训练赛day4

$T1$

Solution

  • 直观的想法

求出 $dfn$ ，每次修改相当于是给一个区间增加和减少一个数。

我们维护一颗线段树，在每个区间设置一颗 $Trie$ 。

区间修改就是给区间的 $Trie$ 加上，减去一个数。

单点询问就是进行 $\log n$ 次求最大异或。

由于是单点询问，我们可以直接标记永久化。

时间复杂度： $O(n\log^2 n)$ ，空间复杂度： $O(n\log^2 n)$ 。

但是空间只有 $128MB$ ，会被卡掉。。

  • 优化空间

我们有一个很常见的套路？？？，将操作离线。

具体的，我们用一颗线段树来维护这些操作。

对于线段树的每一个区间，我们相当于是给了它一个操作序列，每次增加一个数，减少一个数或者进行一次询问。

我们对每一个操作序列，分别用 $Trie$ 来维护，这样时间复杂度依旧是 $O(n\log^2 n)$ ，但是空间上只需要开一个 $Trie$ 就行了。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int n,m,q,val[MAXN],f,opt,x,y,ans[MAXN];
vector<int> G[MAXN];
vector<pair<int,int> > T[MAXN<<2];
int dfn[MAXN],ed[MAXN],cnt;
il DFS(int u){
	dfn[u]=++cnt;
	for(int v:G[u]) DFS(v);
	ed[u]=cnt;
}
#define lc (cur<<1)
#define rc (cur<<1|1)
il Updata(int cur,int l,int r,int L,int R,int k,int ty){
	if(l>=L&&r<=R) return T[cur].push_back(make_pair(ty,k)),void();
	if(mid>=L) Updata(lc,l,mid,L,R,k,ty);
	if(R>mid) Updata(rc,mid+1,r,L,R,k,ty);
}
il Query(int cur,int l,int r,int pos,int k,int id){
	T[cur].push_back(make_pair(id+10,k));
	if(l==r) return ;
	if(mid>=pos) Query(lc,l,mid,pos,k,id);
	else Query(rc,mid+1,r,pos,k,id);
}
int Trie[MAXN*31][2],sz[MAXN*31];
il Init(){
	for(ri i=0;i<=cnt;++i)
		Trie[i][0]=Trie[i][1]=0,sz[i]=0;
	cnt=0;
}
il Trie_Updata(int val,int k){
	int now=0;sz[now]+=k;
	for(ri i=30;i>=0;--i){
		int c=val>>i&1;
		if(!Trie[now][c]) Trie[now][c]=++cnt;
		now=Trie[now][c],sz[now]+=k;
	}
}
it Trie_Query(int val){
	if(cnt==0) return 0;
	int res=0,now=0;
	for(ri i=30;i>=0;--i){
		int c=val>>i&1;
		if(sz[Trie[now][c^1]]&&Trie[now][c^1]) res+=1<<i,now=Trie[now][c^1];
		else now=Trie[now][c];
	}
	return res;
}
il Calc(vector<pair<int,int> > vec){
	Init();
	for(auto v:vec){
		if(v.first==1||v.first==-1)
			Trie_Updata(v.second,v.first);
		else{
			int id=v.first-10;
			int val=v.second;
			ans[id]=max(ans[id],Trie_Query(val));
		}
	}
}
il Solve(int cur,int l,int r){
	Calc(T[cur]);
	if(l==r) return ;
	Solve(lc,l,mid),Solve(rc,mid+1,r);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) read(val[i]);
	for(ri i=2;i<=n;++i) read(f),G[f].push_back(i);
	DFS(1),cnt=0;
	for(ri i=1;i<=n;++i) Updata(1,1,n,dfn[i],ed[i],val[i],1);
	for(ri i=1;i<=m;++i){
		read(opt);
		if(opt==0){
			read(x),read(y);
			Updata(1,1,n,dfn[x],ed[x],val[x],-1);
			val[x]=y;
			Updata(1,1,n,dfn[x],ed[x],val[x],1);
		}
		else{
			read(x),++q;
			Query(1,1,n,dfn[x],val[x],q);
		}
	}
	Solve(1,1,n);
	for(ri i=1;i<=q;++i)
		print(ans[i]),puts("");
	return 0;
}

$T2$

Solution

先考虑 $f(x)$ 怎么计算。

由定义，我们可以得到这样的式子：

$x=1$ 的时候问题等价于抛硬币，问抛到正面的期望步数。

当 $x=2n$ 时，二进制下最后一位为 $0$ ，无论加减 $lowbit(x)$ 都与它无关，所以步数和将它去掉是相等的。

当 $x=2n+1$ 时，加减 $lowbit(x)$ 分别等于 $x-1,x+1$ ，都为偶数，带入上面的式子即可。

我们继续考虑怎么求出 $S(x)$ 。

还是分类讨论。

  • $x=2n$

我们将 $S(x)$ 按照 $i$ 的奇偶性分为两半。

  • $x=2n+1$

与上面一样的方法，可以解得：

然后我们就可以直接记搜了。

时间复杂度： $O(T\log^2n)$ 。（大概是这样）

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int mod = 998244353,inv2 = 499122177;
ll T,x,y;
unordered_map<ll,int> mp;
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
il inc(int &x,int y){x=add(x,y);}
it DFS(ll val){
	if(val==0) return 0;
	if(mp[val]) return mp[val];
	if(val&1){
		int s1=DFS(val>>1),s2=DFS((val>>1)+1);
		return mp[val]=(1ll*s1+1+(val>>1)+1ll*(s1+s2)*inv2)%mod;
	}
	int s1=DFS(val>>1),s2=DFS((val>>1)-1);
	return mp[val]=(1ll*s1+(val>>1)+1ll*(s1+s2)*inv2)%mod;
}
il Solve(){
	read(x),read(y);
	int res=add(DFS(y),mod-DFS(x-1));
	print(res),puts("");
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(T),mp[1]=2;
	for(ri i=1;i<=T;++i)
		Solve();
	return 0;
}