bzoj 3211 花神游历各国

Posted on | Views:

线段树.

对于修改操作,若区间内全为 $1$ ,就跳过,否则就暴力开根.

利用线段树维护区间和.

因为每个数是不会增大的,所以每个数最多被开 $\log \log a_i$ 次根号就被开成 $1$ 了.

时间复杂度 $O(m\log n+n\log \log a)$ .

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
//%std
#include<bits/stdc++.h>
#define rg register
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
inline int Sq(int x)
{
	return (int)(sqrt(x));
}
const ll inf=9e18;
const int MAXN=1e5+10;
int n,m,a[MAXN];
struct node
{
	int mx;
	ll sum;
} Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
void pushup(int o)
{
	root.mx=max(lson.mx,rson.mx);
	root.sum=lson.sum+rson.sum;
}
void BuildTree(int o,int l,int r)
{
	if(l==r)
	{
		root.sum=root.mx=a[l];
		return;
	}
	int mid=(l+r)>>1;
	BuildTree(o<<1,l,mid);
	BuildTree(o<<1|1,mid+1,r);
	pushup(o);
}
int query_mx(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
		return root.mx;
	int res=0;
	int mid=(l+r)>>1;
	if(L<=mid)
		res=max(res,query_mx(o<<1,l,mid,L,R));
	if(R>mid)
		res=max(res,query_mx(o<<1|1,mid+1,r,L,R));
	return res;
}
ll query_sum(int o,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
		return root.sum;
	ll res=0;
	int mid=(l+r)>>1;
	if(L<=mid)
		res+=query_sum(o<<1,l,mid,L,R);
	if(R>mid)
		res+=query_sum(o<<1|1,mid+1,r,L,R);
	return res;
}
void Rebuild(int o,int l,int r,int L,int R)
{
	if(root.mx<=1)
		return;
	if(l==r)
	{
		root.mx=root.sum=Sq(root.mx);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)
		Rebuild(o<<1,l,mid,L,R);
	if(R>mid)
		Rebuild(o<<1|1,mid+1,r,L,R);
	pushup(o);
}
void Sqrt(int L,int R)
{
	int mx=query_mx(1,1,n,L,R);
	if(mx<=1)
		return;
	Rebuild(1,1,n,L,R);
}
int main()
{
	n=read();
	for(rg int i=1; i<=n; ++i)
		a[i]=read();
	BuildTree(1,1,n);
	m=read();
	for(rg int i=1; i<=m; ++i)
	{
		int op=read(),L=read(),R=read();
		if(op==1)
			printf("%lld\n",query_sum(1,1,n,L,R));
		else
			Sqrt(L,R);
	}
	return 0;
}