BZOJ 3211【线段树】

题意： n个数，m个操作。 1,L,R  询问[L , R] 的总和。 2,L,R  将区间所有数都开根号。 思路： 区间和简单。 主要就是一个 区间所有元素相同的标记Same ，但是这样是不是要求太高？ sqrt 好像就算是1e9，也down的非常快到1了，且这里还没有区间加。 so，只要考虑标记区间是否都是1/0就足够了。

水题。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10; struct Seg{ int Left,Right; int Flag; LL Sum; }q[N*4]; void Build(int num,int Left,int Right){ q[num].Left=Left;q[num].Right=Right; if(Left == Right){ scanf("%lld",&q[num].Sum); if(q[num].Sum==0 || q[num].Sum==1) q[num].Flag=1; return; } int Mid=(Left+Right)>>1; Build(num<<1,Left,Mid); Build(num<<1|1,Mid+1,Right); q[num].Sum=q[num<<1].Sum+q[num<<1|1].Sum; q[num].Flag=q[num<<1].Flag&q[2*num|1].Flag; } void Update(int num,int Left,int Right) { if(q[num].Flag) return; if(q[num].Left==q[num].Right) { q[num].Sum=sqrt(q[num].Sum); if(q[num].Sum==0||q[num].Sum==1) q[num].Flag=1; return; } int Mid=(q[num].Left+q[num].Right)>>1; if(Mid>=Right) Update(num<<1,Left,Right); else if(Mid<Left) Update(num<<1|1,Left,Right); else { Update(num<<1,Left,Mid); Update(num<<1|1,Mid+1,Right); } q[num].Sum=q[num<<1].Sum+q[num<<1|1].Sum; q[num].Flag=q[num<<1].Flag&q[num<<1|1].Flag; } LL Query(int num,int Left,int Right) { if(q[num].Left>=Left && q[num].Right<=Right) return q[num].Sum; int Mid=(q[num].Left+q[num].Right)>>1; if(Mid>=Right) return Query(num<<1,Left,Right); else if(Mid<Left) return Query(num<<1|1,Left,Right); else return Query(num<<1,Left,Mid)+Query(num<<1|1,Mid+1,Right); } int main() { int n,Q; int op,Left,Right; scanf("%d",&n); Build(1,1,n); scanf("%d",&Q); while(Q--) { scanf("%d%d%d",&op,&Left,&Right); switch(op){ case 1:printf("%lld\n",Query(1,Left,Right));break; case 2:Update(1,Left,Right);break; } } return 0; }