题目链接：
(1.) 题意人话翻译
有一个长度为(n)（(nleq1e5)）的序列(a_n)。
有(m)组操作
每组操作包含三个数：(opt,l,r)
如果(opt=0)，则对区间每个数开方
如果(opt=1)，则输出区间和
- 注：若(l>r)，请交换(l,r)，(sum_{i=1}^n a_i leq 10^{18})
(2.) 条件处理
题目要求区间每个数开方，这种信息线段树区间修改(lazy)无法维护。
but 正解就是线段树
首先关于数据范围(sum_{i=1}^n a_i leq 10^{18})，我们发现最多开六次就变成1了。所以我们对于一个全为1的区间就不必修改。
其余信息递归到叶子结点修改。
可是我们要如何维护这个信息呢？
法一：建两个线段树，一个维护区间和，一个维护区间最大
如果建立一个维护区间最大的树，我们可以较快维护这个信息。我们只需同时维护两个树上的信息就可以了。
代码（以(SP2713)为例）：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<stack>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<deque>
#include<bitset>
#include<set>
using namespace std;
#define int long long
#define ull unsigned long long
#define rg register
namespace MySpace{
inline int read(){
rg int s=0,f=0;
rg char ch=getchar();
while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
const int N=1e5+15;
int sumv[N<<2],maxv[N<<2],a[N],n,m;
#define ls (now<<1)
#define rs (now<<1|1)
inline void pushup(int now){
sumv[now]=sumv[ls]+sumv[rs];
maxv[now]=max(maxv[ls],maxv[rs]);
}
inline void build(int now,int l,int r){
if(l==r){ sumv[now]=maxv[now]=a[l]; return; }
rg int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
inline void change(int now,int l,int r,int ql,int qr){
if(maxv[now]==1) return;
if(l==r){ sumv[now]=maxv[now]=(int)sqrt(sumv[now]); return; }
rg int mid=(l+r)>>1;
if(ql<=mid) change(ls,l,mid,ql,qr);
if(mid<qr) change(rs,mid+1,r,ql,qr);
pushup(now);
}
inline int query(int now,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sumv[now];
rg int mid=(l+r)>>1,ans=0;
if(ql<=mid) ans+=query(ls,l,mid,ql,qr);
if(mid<qr) ans+=query(rs,mid+1,r,ql,qr);
return ans;
}
inline void main(){
rg int cnt=0;
while(scanf("%d",&n)!=EOF){
printf("Case #%lld:
",++cnt);
for(rg int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
m=read();
for(rg int i=1;i<=m;i++){
rg int opt=read(),l=read(),r=read();
if(l>r) swap(l,r);
if(opt==0) change(1,1,n,l,r);
else printf("%lld
",query(1,1,n,l,r));
}
}
}
}
signed main(){
MySpace::main();
return 0;
}
法二：记一个标记代表全为0或一
我们可以知道全0或1的标记可以用简单的逻辑运算来解决。
如果两个子区间均为0或1，那么合并起来的区间也为0或1。
(3.)后记
后来发现，分块(5)其实就是这个操作。具体思想和上面的法二差不多，也不再赘述。