uoj228 基础数据结构练习题

题意

给出一个长度为 $n$ 的数列 $A$,接下来有 $m$ 次操作,操作有三种:

  1. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $A_i +x$。
  2. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $\sqrt {A_i}$。
  3. 对于所有的$i \in [l,r]$,询问 $A_i$ 的和。

50%

这个也是最开始的想法…很无脑,但一味以为是对的就写了。

想到<花神游历各国>那个题,于是直接觉得区间开根号操作可以直接通过判断$max$是否$\geq 1$再递归开根即可,这样的话每个数最多开根6次,那么最多是$\mathcal O(6n)$的。然而这样想是错的,因为每个数还有加操作,那么一旦开根它还可以加回来,这样就会达到$\mathcal O(nm)$,会很慢。对于这题而言,$n\leq 3000$和没有加操作的数据是可以用这个粗暴的线段树过掉的。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e5+5;
typedef long long ll;
#define lson (o<<1)
#define rson (o<<1|1)
int n,m;
ll a[maxn];
struct intervaltree{
ll sumv[maxn<<2],addv[maxn<<2],maxv[maxn<<2];
void maintain(int o,int l,int r)
{
sumv[o]=sumv[lson]+sumv[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
if(addv[o]) sumv[o]+=addv[o]*(r-l+1),maxv[o]+=addv[o];
}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r){
sumv[o]=maxv[o]=a[l];
addv[o]=0;
return;
}else{
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
addv[o]=0;
sumv[o]=sumv[lson]+sumv[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
}
}
void getadd(int o,int l,int r,ll val)
{
addv[o]+=val;
sumv[o]+=val*(r-l+1);
maxv[o]+=val;
}
void getsqrt(int o,int l,int r)
{
if(l>r) return;
if(maxv[o]<=1) return;
if(l==r){
sumv[o]=(ll)sqrt(sumv[o]);maxv[o]=(ll)sqrt(maxv[o]);
addv[o]=0;
return;
}else{
pushdown(o,l,r);
int mid=(l+r)>>1;
if(maxv[lson]>1) getsqrt(lson,l,mid);
if(maxv[rson]>1) getsqrt(rson,mid+1,r);
maintain(o,l,r);
}
}
void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(addv[o]) getadd(lson,l,mid,addv[o]),getadd(rson,mid+1,r,addv[o]),addv[o]=0;
maintain(o,l,r);
}
void Uadd(int o,int l,int r,int ql,int qr,ll val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){
getadd(o,l,r,val);
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Uadd(lson,l,mid,ql,qr,val);
if(qr>mid) Uadd(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
void Usqrt(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr) {
getsqrt(o,l,r);
return ;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Usqrt(lson,l,mid,ql,qr);
if(qr>mid) Usqrt(rson,mid+1,r,ql,qr);
maintain(o,l,r);
}
}
ll Qsum(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return sumv[o];
else{
int mid=(l+r)>>1;
pushdown(o,l,r);ll ret=0;
if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr);
return ret;
}
}
} Tree;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
Tree.build(1,1,n);
int op,l,r;ll x;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%lld",&x);
Tree.Uadd(1,1,n,l,r,x);
}else if(op==2){
Tree.Usqrt(1,1,n,l,r);
}else {
printf("%lld\n",Tree.Qsum(1,1,n,l,r));
}
}
return 0;
}

80%

暴力开根的线段树会被卡成上述复杂度,那么要想一些不暴力的办法。

对于一个区间,如果我们发现它的最大值和最小值开根号后相等,是不是直接区间修改就可以辣。

对于一个区间,如果我们发现它的最大值和最小值相差$1$并且开根号后不相等,是不是有$max-min=1$并且$\sqrt{max} -\sqrt{min} =1$,那么自然我们需要对每个数进行加上$\sqrt{min}-min$操作即可。

对于其余情况,用50%的方法暴力开根(虽然听上去就比较傻逼,但我居然觉得这就没问题了)

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
137
138
139
140
141
142
143
144
145
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=(int)1e5+5;
#define lson (o<<1)
#define rson (o<<1|1)
int n,m;
ll a[maxn];
struct intervaltree{
ll sumv[maxn<<2],maxv[maxn<<2],minv[maxn<<2],addv[maxn<<2],setv[maxn<<2];
void maintain(int o,int l,int r)
{
if(l<r){
sumv[o]=sumv[lson]+sumv[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
minv[o]=min(minv[lson],minv[rson]);
}else sumv[o]=maxv[o]=minv[o]=a[l];
if(setv[o]!=-1) sumv[o]=setv[o]*(r-l+1),maxv[o]=setv[o],minv[o]=setv[o];
if(addv[o]) sumv[o]+=addv[o]*(r-l+1),maxv[o]+=addv[o],minv[o]+=addv[o];
}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r){
sumv[o]=maxv[o]=minv[o]=a[l];
addv[o]=0,setv[o]=-1;
return;
}else{
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
addv[o]=0,setv[o]=-1;
maintain(o,l,r);
}
}
void getset(int o,int l,int r,ll val)
{
setv[o]=val;
addv[o]=0;
maintain(o,l,r);
}
void getadd(int o,int l,int r,ll val)
{
addv[o]+=val;
maintain(o,l,r);
}
void getsqrt(int o,int l,int r)
{
if(l>r) return;
if(maxv[o]<=1) return;
if(l==r){
sumv[o]=(ll)sqrt(sumv[o]);maxv[o]=(ll)sqrt(maxv[o]);minv[o]=(ll)sqrt(minv[o]);
a[l]=sumv[o];
setv[o]=-1,addv[o]=0;
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(maxv[lson]>1) getsqrt(lson,l,mid);
if(maxv[rson]>1) getsqrt(rson,mid+1,r);
maintain(o,l,r);
}
}
void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(setv[o]!=-1){
getset(lson,l,mid,setv[o]);getset(rson,mid+1,r,setv[o]);
setv[o]=-1;
maintain(o,l,r);
}
if(addv[o]){
getadd(lson,l,mid,addv[o]);getadd(rson,mid+1,r,addv[o]);
addv[o]=0;
maintain(o,l,r);
}
}
void Usqrt(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){
if((ll)sqrt(maxv[o])==(ll)sqrt(minv[o])) {
getset(o,l,r,(ll)sqrt(maxv[o]));
}else if(maxv[o]==minv[o]+1){
getadd(o,l,r,(ll)sqrt(minv[o])-minv[o]);
}else getsqrt(o,l,r);
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Usqrt(lson,l,mid,ql,qr);
if(qr>mid) Usqrt(rson,mid+1,r,ql,qr);
maintain(o,l,r);
}
}
void Uadd(int o,int l,int r,int ql,int qr,ll val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){getadd(o,l,r,val);return;}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Uadd(lson,l,mid,ql,qr,val);
if(qr>mid) Uadd(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
ll Qsum(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) {return sumv[o];}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
ll ret=0;
if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr);
return ret;
}
}
} Tree;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
}
Tree.build(1,1,n);
int op,l,r;
ll x;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%lld",&x);
Tree.Uadd(1,1,n,l,r,x);
}else if(op==2){
Tree.Usqrt(1,1,n,l,r);
}else if(op==3){
printf("%lld\n",Tree.Qsum(1,1,n,l,r));
}
}
return 0;
}

100%

对于上述方法,剩余的区间暴力开根不可取啊。当数据浮动很大时,这相当于是完全暴力开根了,依旧会被卡成$\mathcal O(nm)$,自然不行。

那么对于这类区间,我们不断递归下去,将它分成一个个符合前两种策略的区间即可。

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
137
138
139
140
141
142
143
144
145
146
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <iostream>
#include <ctime>
using namespace std;
typedef long long ll;
const int maxn=(int)1e5+5;
#define lson (o<<1)
#define rson (o<<1|1)
int n,m;
ll a[maxn];
struct intervaltree{
ll sumv[maxn<<2],maxv[maxn<<2],minv[maxn<<2],addv[maxn<<2],setv[maxn<<2];
void maintain(int o,int l,int r)
{
if(l<r){
sumv[o]=sumv[lson]+sumv[rson];
maxv[o]=max(maxv[lson],maxv[rson]);
minv[o]=min(minv[lson],minv[rson]);
}else sumv[o]=maxv[o]=minv[o]=a[l];
if(setv[o]!=-1) sumv[o]=setv[o]*(r-l+1),maxv[o]=setv[o],minv[o]=setv[o];
if(addv[o]) sumv[o]+=addv[o]*(r-l+1),maxv[o]+=addv[o],minv[o]+=addv[o];
}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r){
sumv[o]=maxv[o]=minv[o]=a[l];
addv[o]=0,setv[o]=-1;
return;
}else{
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
addv[o]=0,setv[o]=-1;
maintain(o,l,r);
}
}
void getset(int o,int l,int r,ll val)
{
setv[o]=val;
addv[o]=0;
maintain(o,l,r);
}
void getadd(int o,int l,int r,ll val)
{
addv[o]+=val;
maintain(o,l,r);
}
void getsqrt(int o,int l,int r)
{
if(l>r) return;
if(maxv[o]<=1) return;
if(l==r){
sumv[o]=(ll)sqrt(sumv[o]);maxv[o]=(ll)sqrt(maxv[o]);minv[o]=(ll)sqrt(minv[o]);
a[l]=sumv[o];
setv[o]=-1,addv[o]=0;
return;
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(maxv[lson]>1) getsqrt(lson,l,mid);
if(maxv[rson]>1) getsqrt(rson,mid+1,r);
maintain(o,l,r);
}
}
void pushdown(int o,int l,int r)
{
int mid=(l+r)>>1;
if(setv[o]!=-1){
getset(lson,l,mid,setv[o]);getset(rson,mid+1,r,setv[o]);
setv[o]=-1;
maintain(o,l,r);
}
if(addv[o]){
getadd(lson,l,mid,addv[o]);getadd(rson,mid+1,r,addv[o]);
addv[o]=0;
maintain(o,l,r);
}
}
void Usqrt(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr && (ll)sqrt(maxv[o])==(ll)sqrt(minv[o]) ) {
getset(o,l,r,(ll)sqrt(maxv[o]));
}else if(ql<=l && r<=qr && maxv[o]==minv[o]+1){
getadd(o,l,r,(ll)sqrt(minv[o])-minv[o]);
}else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Usqrt(lson,l,mid,ql,qr);
if(qr>mid) Usqrt(rson,mid+1,r,ql,qr);
maintain(o,l,r);
}
}
void Uadd(int o,int l,int r,int ql,int qr,ll val)
{
if(ql>r || qr<l) return;
if(ql<=l && r<=qr){getadd(o,l,r,val);return;}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
if(ql<=mid) Uadd(lson,l,mid,ql,qr,val);
if(qr>mid) Uadd(rson,mid+1,r,ql,qr,val);
maintain(o,l,r);
}
}
ll Qsum(int o,int l,int r,int ql,int qr)
{
if(ql>r || qr<l) return 0;
if(ql<=l && r<=qr) {return sumv[o];}
else{
int mid=(l+r)>>1;
pushdown(o,l,r);
ll ret=0;
if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr);
if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr);
return ret;
}
}
} Tree;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
}
Tree.build(1,1,n);
int op,l,r;
ll x;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%lld",&x);
Tree.Uadd(1,1,n,l,r,x);
}else if(op==2){
Tree.Usqrt(1,1,n,l,r);
}else if(op==3){
printf("%lld\n",Tree.Qsum(1,1,n,l,r));
}
}
cerr<< (double)clock()/CLOCKS_PER_SEC << "s" <<"\n";
return 0;
}