区間開方、区間求和、線分ツリー

普通の問題2
                                              Time Limit: 500 MS     Memory Limit: 64 MB
Submit Status
長さnの数列a 1...anとnの操作を与え,操作は区間開方,区間求和に関連する.
Input
1行目にn(1≦n≦50000)の数字を入力します.
2行目はn個の非負の整数を入力し、i番目の数字はai、(0≦ai≦109)はスペースで区切られる.
次にn行の質問を入力し、各行に4つの数字opt,l,r,cを入力し、スペースで区切ります.
opt=0であれば、[l,r]の間に位置する数字がすべて開方されることを示す.区間の各ai(l≦i≦r)について、ai→⌊√ai⌋
opt=1の場合、[l,r]にあるすべての数字の和を表す.
Output
質問のたびに、z行の数値を出力して答えを表します.
すべてのデータがintの範囲内であることを保証します.
Sample input and output
Sample Input
Sample Output

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

6
2

 
実はこの問題はブロックで作ることができて、詳しくは私のブログを見て、構想とブロックの差は多くなくて、0あるいは1に出会って0(更に開方値は変わらない)とマークして、その他のマークは1で、
1つの区間が0と表記されている場合は、開方しません.そうしないと、暴力的にサブ区間を検索します.

#include
#include
#include
using namespace std;
const int maxn=50005;
struct node
{
    int tag;
    int val;
}b[maxn<<2];
int a[maxn];
void judge(int rt)
{
    if(b[rt].val==0||b[rt].val==1) b[rt].tag=0;
    else    b[rt].tag=1;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        b[rt].val=a[l];
        if(b[rt].val==0||b[rt].val==1) b[rt].tag=0;
        else    b[rt].tag=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    b[rt].val=b[rt*2].val+b[rt*2+1].val;
    b[rt].tag=b[rt*2].tag||b[rt*2+1].tag;
}
int  query(int l,int r,int rt,int ll,int rr)
{
    if(ll<=l&&r<=rr)
    {
        return b[rt].val;
    }
    int mid=(l+r)>>1;
    int  ans=0;
    if(ll<=mid) ans+=query(l,mid,rt*2,ll,rr);
    if(rr>mid) ans+=query(mid+1,r,rt*2+1,ll,rr);
    return ans;
}
void change(int l,int r,int rt,int ll,int rr)
{
    if(ll<=l&&r<=rr&&!b[rt].tag) return ;
    if(l==r)
    {
        b[rt].val=int(sqrt(b[rt].val));
        judge(rt);
        return ;
    }
    int mid=(l+r)>>1;
    if(ll<=mid) change(l,mid,rt*2,ll,rr);
    if(rr>mid)  change(mid+1,r,rt*2+1,ll,rr);
    b[rt].val=b[rt*2].val+b[rt*2+1].val;
    b[rt].tag=b[rt*2].tag||b[rt*2+1].tag;
}
int main()
{
    int n;
    int o,l,r,c;
    while(scanf("%d",&n)!=EOF)
    {

        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        build(1,n,1);
        for(int i=0;i