BZOJ-3038: 上帝造题的七分钟2

Description

给出长度为n的序列，给出m次操作，区间开根号取下整或区间求和。n,m<=100000，ai<=

发现每个ai最多操作7次后都会变成1。
第一想法：预处理7稞线段树，然后动态改变儿子。
然后邻座的小伙子告诉我很麻烦。
可以直接暴力修改，如果当前的sum为区间的siz就直接返回，发现复杂度是O(nlogn*7)，然后就可以啦。
然后邻座的另一个小伙子告诉我太麻烦了，可以直接树状数组维护前缀和+并查集维护每个点后面最近的不为1的点啊。
然后，写了一个一点都不像并查集的东西。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
int n,m;
ll a[101000],f[101000],sum[101000];
int las[101000];
ll query(int x)
{
    ll re=0;
    while(x>0) re+=f[x],x-=-x&x;
    return re;
}
void fix(int &x,const int y)
{
    if(x>y) return ;
    if(a[x]!=1)
    {
        ll tmp=(ll)sqrt(a[x]+0.9);
        for(int i=x;i<=n;i+=-i&i) f[i]=f[i]-a[x]+tmp;
        a[x]=tmp;
    }
    fix(las[x],y);
    if(a[x]<=1) x=las[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) las[i]=i+1;
    scanf("%d",&m); int x,y,sw;
    while(m--)
    {
        scanf("%d%d%d",&sw,&x,&y);
        if(x>y) swap(x,y);
        if(sw==1) printf("%lld\n",query(y)-query(x-1)+sum[y]-sum[x-1]);
        else fix(x,y);
    }   
    return 0;
}