花神游历各国
题意数据范围思路代码
题意
给定一个长度为
n
n
n的序列，支持两种操作：
返回区间和区间每个数开根
操作个数为
m
m
m
数据范围
1
≤
n
≤
1
0
5
1\leq n \leq 10^5
1≤n≤105
1
≤
m
≤
2
∗
1
0
5
1\leq m \leq 2*10^5
1≤m≤2∗105
0
≤
w
i
≤
1
0
9
0\leq w_i \leq 10^9
0≤wi≤109
思路
这道题显然要用线段树维护。首先看区间每个数的修改，第一反应是懒标记，但是发现难以维护。这个时候，我们思考一下开方，对于每个数，大概执行
5
5
5次开方操作就能降到
1
1
1。所以我们完全可以单点修改，但是要记录一个标志，就是是否减少到
1
1
1。这样进行修改操作的时候，如果这一段每个数都已经变成
1
1
1了，那么就不需要进行修改了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std
;
const int N
= 100010;
typedef long long ll
;
int n
,q
;
ll w
[N
];
struct Node
{
int l
, r
;
ll sum
;
bool flag
;
}tr
[N
<<2];
void pushup(int u
)
{
tr
[u
].sum
= tr
[u
<<1].sum
+ tr
[u
<<1|1].sum
;
tr
[u
].flag
= tr
[u
<<1].flag
&& tr
[u
<<1|1].flag
;
}
void build(int u
,int l
,int r
)
{
if(l
==r
){
tr
[u
] = {l
,r
,w
[r
],w
[r
]<=1};
return;
}
tr
[u
] = {l
,r
};
int mid
= l
+ r
>> 1;
build(u
<<1,l
,mid
), build(u
<<1|1,mid
+1,r
);
pushup(u
);
}
void modify(int u
,int l
,int r
)
{
if(tr
[u
].flag
) return;
if(tr
[u
].l
== tr
[u
].r
){
tr
[u
].sum
= sqrt(tr
[u
].sum
);
tr
[u
].flag
= tr
[u
].sum
<= 1;
}
else{
int mid
= tr
[u
].l
+ tr
[u
].r
>> 1;
if(l
<=mid
) modify(u
<<1,l
,r
);
if(r
>mid
) modify(u
<<1|1,l
,r
);
pushup(u
);
}
}
ll
query(int u
,int l
,int r
)
{
if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
].sum
;
else{
int mid
= tr
[u
].l
+ tr
[u
].r
>> 1;
ll ans
= 0;
if(l
<=mid
) ans
+= query(u
<<1,l
,r
);
if(r
>mid
) ans
+= query(u
<<1|1,l
,r
);
return ans
;
}
}
int main()
{
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%lld",&w
[i
]);
build(1,1,n
);
scanf("%d",&q
);
while(q
--){
int op
,l
,r
;
scanf("%d%d%d",&op
,&l
,&r
);
if(op
==1) printf("%lld\n",query(1,l
,r
));
else modify(1,l
,r
);
}
return 0;
}
