bzoj3211 花神游历各国

这题有两个做法…

本质都是因为一个点开根号 最多开到1或者本身为0就不回继续开下去,所以这段区间可以跳过不处理

于是就有了两种做法:

  • 像疯狂的馒头那题那样,并查集跳过不需要再开根号的区间(即开了根号也和原数相同。)
  • 线段树维护,只要发现当前区间的最大值都小于等于1了,那么不需要修改这个区间,返回即可。

并查集

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>
using namespace std;
typedef long long ll;
const int maxn=100000+5,maxm=200000+5;
int f[maxn],siz[maxn];
ll a[maxn];
int getf(int x){return x==f[x]?f[x]:f[x]=getf(f[x]);}
void merge(int u,int v)
{
int fu=getf(u),fv=getf(v);
if(fu==fv) return;
else{
if(siz[fu]>siz[fv]){
siz[fu]+=siz[fv];
f[fv]=fu;
}else{
siz[fv]+=siz[fu];
f[fu]=fv;
}
}
}
inline int lowbit(int x){return x&(-x);}
ll sum[maxn];
int n,m;
void add(int pos,ll ad)
{
while(pos<=n){
sum[pos]+=ad;
pos+=lowbit(pos);
}
}
ll getsum(int pos)
{
ll ret=0;
while(pos>0){
ret+=sum[pos];
pos-=lowbit(pos);
}
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
add(i,a[i]);
}
for(int i=1;i<=n+1;i++) f[i]=i;
scanf("%d",&m);
int x,l,r,tmp;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&l,&r);
if(x==1){
printf("%lld\n",getsum(r)-getsum(l-1));
}else{
for(int j=getf(l);j<=r;j=getf(j+1)){
if(j>r) break;
tmp=(ll)sqrt((double)a[j]);
add(j,tmp-a[j]);
a[j]=tmp;
if(a[j]<=1ll) f[j]=getf(j+1);
}
}
}
return 0;
}

线段树

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <cassert>
#include <climits>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
int a[maxn],n,m;
#define lson (o<<1)
#define rson (o<<1|1)
struct intervaltree{
ll sumv[maxn<<2],maxv[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]);}
void build(int o,int l,int r)
{
if(l>r) return;
if(l==r) maxv[o]=sumv[o]=a[l];
else{
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
maintain(o,l,r);
}
}
void getsqrt(int o,int l,int r)
{
if(l>r) return;
if(maxv[o]<=1) return;
else if(l==r) {
sumv[o]=(int)sqrt(sumv[o]),maxv[o]=(int)sqrt(maxv[o]);
return;
}else{
int mid=(l+r)>>1;
if(l<=mid) getsqrt(lson,l,mid);
if(r>=mid+1) getsqrt(rson,mid+1,r);
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;
Usqrt(lson,l,mid,ql,qr),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;
ll ret=0;
ret+=Qsum(lson,l,mid,ql,qr),ret+=Qsum(rson,mid+1,r,ql,qr);
return ret;
}
}
} Tree;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Tree.build(1,1,n);
int op,l,r;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&op,&l,&r);
if(op==1) printf("%lld\n",Tree.Qsum(1,1,n,l,r));
else Tree.Usqrt(1,1,n,l,r);
}
return 0;
}