做网站公司官网,小程序外包网,什么平台可以推广,免费开发网站Time Limit: 3 Sec Memory Limit: 128 MB Description XLk觉得《上帝造题的七分钟》不太过瘾#xff0c;于是有了第二部。 第一分钟#xff0c;X说#xff0c;要有数列#xff0c;于是便给定了一个正整数数列。 第二分钟#xff0c;L说#xff0c;要能修改#xf…Time Limit: 3 Sec Memory Limit: 128 MB Description XLk觉得《上帝造题的七分钟》不太过瘾于是有了第二部。 第一分钟X说要有数列于是便给定了一个正整数数列。 第二分钟L说要能修改于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟k说要能查询于是便有了求一段数的和的操作。 第四分钟彩虹喵说要是noip难度于是便有了数据范围。 第五分钟诗人说要有韵律于是便有了时间限制和内存限制。 第六分钟和雪说要省点事于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。 第七分钟这道题终于造完了然而造题的神牛们再也不想写这道题的程序了。 ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 Input 第一行一个整数n代表数列中数的个数。 第二行n个正整数表示初始状态下数列中的数。 第三行一个整数m表示有m次操作。 接下来m行每行三个整数k,l,rk0表示给[l,r]中的每个数开平方(下取整)k1表示询问[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 19
7
6 HINT 1对于100%的数据1n1000001lrn数列中的数大于0且不超过1e12。 2数据不保证LR 若LR请自行交换L,R谢谢 Solution 显然的1e12的数可以在最多10次以内就可以被开为1所以到了线段树一个区间如果这个区间全是1不管是询问还是修改都直接return回去。不然直接在线段树里面暴力修改。 #includecstdio
#includealgorithm
#includecmath
#includecstring
#define lowbit(x) ((x)(-(x)))
#define lc o1
#define rc o1|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 ihead[x];i;ig[i].ne)
templatetypename Ainline void read(Aa){a0;char c0;int f1;while(c0||c9)(cgetchar())-?f-1:0;while(c0c9)a(a3)(a1)c-0,cgetchar();f-1?a-a:0;}
char buf[30];templatetypename Ainline void write(A a){if(a0)putchar(-),a-a;int top0;if(!a)buf[top1]0;while(a)buf[top]a%100,a/10;while(top)putchar(buf[top--]);}
typedef long long ll;typedef unsigned long long ull;
templatetypename A,typename Binline bool SMAX(Ax,const By){return yx?xy,1:0;}
templatetypename A,typename Binline bool SMIN(Ax,const By){return yx?xy,1:0;}const int N1000007;
int n,Q,opt,x,y;ll a[N];//错误笔记似乎a数组就要开ll了 struct Node{ll maxv;}t[N2];
inline void Build(int o,int L,int R){if(LR)t[o].maxva[L];else{int M(LR)1;Build(lc,L,M);Build(rc,M1,R);t[o].maxvmax(t[lc].maxv,t[rc].maxv);}}
inline void Update(int o,int L,int R,int l,int r){if(t[o].maxv1)return;if(LR)return (void)(t[o].maxvsqrt(t[o].maxv));int M(LR)1;if(lM)Update(lc,L,M,l,r);if(rM)Update(rc,M1,R,l,r);t[o].maxvmax(t[lc].maxv,t[rc].maxv);
}
inline ll Sum(int o,int L,int R,int l,int r){if(t[o].maxv1)return (min(R,r)-max(L,l)1)*t[o].maxv;if(LR)return t[o].maxv;int M(LR)1;ll ans0;if(lM)ansSum(lc,L,M,l,r);if(rM)ansSum(rc,M1,R,l,r);return ans;
}int main(){read(n);for(register int i1;in;i)read(a[i]);Build(1,1,n);read(Q);for(register int i1;iQ;i){read(opt),read(x),read(y);if(xy)x^y^x^y;if(opt)write(Sum(1,1,n,x,y)),putchar(\n);else Update(1,1,n,x,y);}
} 转载于:https://www.cnblogs.com/hankeke/p/BZOJ3038.html
