Time Limit: 3 Sec Memory Limit: 128 MB

Description

XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
"第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

Input

第一行一个整数n，代表数列中数的个数。
第二行n个正整数，表示初始状态下数列中的数。
第三行一个整数m，表示有m次操作。
接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。

Output

对于询问操作，每行输出一个回答。

Sample Input

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

Sample Output

HINT

1：对于100%的数据，1<=n<=100000，1<=l<=r<=n，数列中的数大于0，且不超过1e12。

2：数据不保证L<=R 若L>R，请自行交换L,R，谢谢！

Solution

显然的，1e12的数可以在最多10次以内就可以被开为1，所以到了线段树一个区间，如果这个区间全是1，不管是询问还是修改都直接return回去。不然直接在线段树里面暴力修改。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#define lowbit(x) ((x)&(-(x)))

#define lc o<<1

#define rc o<<1|1

using namespace std;

#define REP(i,a,n) for(register int i=(a);i<=(n);++i)

#define PER(i,a,n) for(register int i=(a);i>=(n);--i)

#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)

template<typename A>inline void read(A&a){a=0;char c=0;int f=1;while(c<'0'||c>'9')(c=getchar())=='-'?f=-1:0;while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();f==-1?a=-a:0;}

char buf[30];template<typename A>inline void write(A a){if(a<0)putchar('-'),a=-a;int top=0;if(!a)buf[top=1]='0';while(a)buf[++top]=a%10+'0',a/=10;while(top)putchar(buf[top--]);}

typedef long long ll;typedef unsigned long long ull;

template<typename A,typename B>inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;}

template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}

const int N=100000+7;

int n,Q,opt,x,y;ll a[N];//错误笔记：似乎a数组就要开ll了

struct Node{ll maxv;}t[N<<2];

inline void Build(int o,int L,int R){if(L==R)t[o].maxv=a[L];else{int M=(L+R)>>1;Build(lc,L,M);Build(rc,M+1,R);t[o].maxv=max(t[lc].maxv,t[rc].maxv);}}

inline void Update(int o,int L,int R,int l,int r){

	if(t[o].maxv<=1)return;if(L==R)return (void)(t[o].maxv=sqrt(t[o].maxv));

	int M=(L+R)>>1;if(l<=M)Update(lc,L,M,l,r);if(r>M)Update(rc,M+1,R,l,r);

	t[o].maxv=max(t[lc].maxv,t[rc].maxv);

}

inline ll Sum(int o,int L,int R,int l,int r){

	if(t[o].maxv<=1)return (min(R,r)-max(L,l)+1)*t[o].maxv;if(L==R)return t[o].maxv;

	int M=(L+R)>>1;ll ans=0;if(l<=M)ans+=Sum(lc,L,M,l,r);if(r>M)ans+=Sum(rc,M+1,R,l,r);

	return ans;

}

int main(){

	read(n);for(register int i=1;i<=n;++i)read(a[i]);

	Build(1,1,n);read(Q);

	for(register int i=1;i<=Q;++i){

		read(opt),read(x),read(y);if(x>y)x^=y^=x^=y;

		if(opt)write(Sum(1,1,n,x,y)),putchar('\n');

		else Update(1,1,n,x,y);

	}

}

分钟