BZOJ 3038 -- 上帝造题的七分钟2

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

区间开平方维护区间和

题面

解

注意到进行少量开平方操作，值就会变为 1

于是暴力开方，把 1 跳过即可

用并查集维护下一个 1 的位置

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
#include <cstdio>
#include <cmath>
#include <algorithm>

using std::swap;

const int MAXN=100011;

int N, M;
int F[MAXN];
long long A[MAXN];
long long C[MAXN];

inline int lowbit(const int &a){
	return a&(-a);
}

inline void Add(const int &p, const long long &d){
	for(int i=p;i<=N;i+=lowbit(i))
		C[i]+=d;
}

inline long long Ask(const int &p){
	long long ret=0LL;
	for(int i=p;i>0;i-=lowbit(i))
		ret+=C[i];
	return ret;
}

int Find(const int &a){
	return a==F[a]?a:F[a]=Find(F[a]);
}

void Deal(int p){
	Add(p, -A[p]);
	A[p]=sqrt(A[p]);
	Add(p, A[p]);
}

void Modi(int l, int r){
	for(int i=Find(l);i<=r;++i, i=Find(i)){
		Deal(i);
		if(A[i]==1)	F[i]=i+1;
	}
}

int main(){
	
	scanf("%d", &N);
	
	for(int i=1;i<=N;++i){
		scanf("%lld", &A[i]);
		F[i]=i;
	}
	F[N+1]=N+1;
	
	for(int i=1;i<=N;++i)	Add(i, A[i]);
	
	scanf("%d", &M);
	
	for(int t, l, r;M--;){
		scanf("%d%d%d", &t, &l, &r);
		if(l>r)	swap(l, r);
		if(t)
			printf("%lld\n", Ask(r)-Ask(l-1));
		else	Modi(l, r);
	}
	
	return 0;
}

/*
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

*/