HDU-4027

$n$ 个数，和在 $2^{63}$ 范围内。

也就是 $\sum a_i \leq 2^{63}$

现在有「两种」操作

x y ```把区间 $[x,y]$ 内的每个数开方，下取整

```1 x y```询问区间 $[x,y]$ 的每个数的和

## 思路

这道题两年半以前做过一次，所以思路都还记得，但还是被坑了。

首先注意一个性质： $0$ 与 $1$ 在开方以后仍为原数不变。

其次，数据范围，一个数最大为 $2^{63}$ ，所以最多开 $6$ 次方，就变为了 $1$ 。

这样的话，考虑建立线段树，维护区间和和一个标记，该标记用来说明该节点区间内是否都为 $0$ 或 $1$ 。

对于操作 $0$ ，由于开方的有限性，所以直接对每个点暴力开方即可 。

对于操作 $1$ ，直接查询区间和即可。

坑点：不保证 $x<y$ ，需自行调整 $x,y$ 顺序。输出格式中，每个测试点结束要输出空行。

## 代码

```cpp
#include<bits/stdc++.h>
#define ll long long 
#define N 100010

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

class Segment_Tree{
  private:
    ll sum[N<<2];
    bool flag[N<<2];
    #define s(x) sum[x]
    #define f(x) flag[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls)+s(rs);
        f(p)=f(ls)&f(rs);
    }
  public:
    void build(int p,int l,int r) {
        if(l==r) {
            s(p)=read();
            f(p)=(!s(p)||s(p)==1);
            return ;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void modify(int p,int l,int r,int L,int R) {
        if(f(p)||l>R||r<L) return ;
        if(l==r) {
            s(p)=(int)sqrt(s(p)); 
            f(p)=(!s(p)||s(p)==1);
            return ;
        }
        modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
    }
}SMT;

int n,m,t=0;

int main() {
    while(cin>>n) {
        printf("Case #%d:\n",++t);
        SMT.build(1,1,n);
        m=read();
        for(int i=1;i<=m;i++) {
            int op,l,r;
            op=read(),l=read(),r=read();
            if(l>r) swap(l,r);
            if(op==0) SMT.modify(1,1,n,l,r);
            else printf("%lld\n",SMT.ask(1,1,n,l,r));
        }
        printf("\n");
    }
    system("pause");
    return 0;
}