bzoj 3211花神遊歴各国線分樹

長さnのシーケンスを維持し、2つの操作をサポートします:1、区間開根号(下に整頓);2、区間の和を求める.n<=10000000,m<=20000000,シーケンスの数<=10^9で非負の整数である.
题目分析:このように追い詰めてまた水をこすりにきて、私は心が大きいですかそれとも头が糞に入りますT_T
区間開根号というデータ構造のメンテナンスはありませんが、10^9という大きな数の開根号は5回で1になります.だからセグメントツリーは区間和を守って、それから修正すれば暴力的にセグメントツリーで変更すればいいのですが、もう修正する必要のない区間にはマークをつけて、修正するときは動かなければいいのです.
時間複雑度O(nlogn)は,全数に対して最大5 n回,毎回の修正時間複雑度がlognを超えず,単一クエリーlognであるためnlognである.
不注意で非負にTを2発返して、私は本当に......頭が糞に入った......
コードは次のとおりです.

#include 
#include 
#include 
#define N 120000
#define ls(c) (c<<1)
#define rs(c) (c<<1|1)
using namespace std;
typedef long long LL;
int n,m;
int a[N];
struct segment{
    int l,r,mark;
    LL sum;
}seg[N<<2];
void build_tree(int c,int l,int r)
{
    seg[c].l=l,seg[c].r=r;
    if(l==r)
    {
        seg[c].sum=a[l];
        seg[c].mark=a[l]<=1;
        return;
    }
    int mid=l+r>>1;
    build_tree(ls(c),l,mid);
    build_tree(rs(c),mid+1,r);
    seg[c].sum=seg[ls(c)].sum+seg[rs(c)].sum;
    seg[c].mark=seg[ls(c)].mark&seg[rs(c)].mark;
}
void update(int c,int l,int r)
{
    if(seg[c].mark) return;
    if(seg[c].l==seg[c].r)
    {
        seg[c].sum=int(sqrt(seg[c].sum));
        seg[c].mark=seg[c].sum<=1;
        return;
    }
    int mid=seg[c].l+seg[c].r>>1;
    if(l<=mid) update(ls(c),l,r);
    if(r>mid) update(rs(c),l,r);
    seg[c].sum=seg[ls(c)].sum+seg[rs(c)].sum;
    seg[c].mark=seg[ls(c)].mark&seg[rs(c)].mark;
}
LL query(int c,int l,int r)
{
    if(l<=seg[c].l && r>=seg[c].r) return seg[c].sum;
    int mid=seg[c].l+seg[c].r>>1;
    if(r<=mid) return query(ls(c),l,r);
    if(l>mid) return query(rs(c),l,r);
    return query(ls(c),l,r)+query(rs(c),l,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    build_tree(1,1,n);
    for(int i=1,opt,l,r;i<=m;i++)
    {
        scanf("%d%d%d",&opt,&l,&r);
        if(l>r) swap(l,r);
        if(opt==1) printf("%lld
",query(1,l,r));
        else update(1,l,r);
    }
    return 0;
}