HDU 4027 Can you answer these queries(Segment tree)

Description

给出一个数字N，给出1到N这个N个数字的初值

M个操作：

1. 更新x、y之间所有数字为他们的算术平方根
2. 查询x、y之间所有数字的和

Something about Segment Tree

线段树有initial、update、query三个函数

initial函数用到了int mid = ( + ) >> 1;

而流氓写法的update、query函数没有用到mid

Analyze

觉得这种题目的更新没办法lazy，区间更新只能换成暴力单点更新。

此题的剪枝在于“算术平方根”，所给范围内的数字求8次以内次数的算术平方根就会变成1，现在拿一组变量纪录每个区间的最大值，若区间最大值是1，那么就没必要向下更新了。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 100005;

ll n, k, ans, val[N];
struct node
{
    ll L, R, sum, mmax;
}a[N << 2 | 1];

void init(ll num, ll l, ll r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].sum = 0;
    a[num].mmax = 0;

    if(l == r)
    {
        a[num].sum = a[num].mmax = val[r];
        return ;
    }

    ll mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
    a[num].sum = a[num << 1].sum + a[num << 1 | 1].sum;
    a[num].mmax = max(a[num << 1].mmax, a[num << 1 | 1].mmax);
}

void update(ll num, ll l, ll r)
{
    if(a[num].L > r || a[num].R < l || a[num].mmax <= 1)///pruning
        return ;
    if(a[num].L == a[num].R)///Brute single node change!
    {
        a[num].sum = sqrt(a[num].sum);
        a[num].mmax = a[num].sum;
        return ;
    }
    update(num << 1, l, r);
    update(num << 1 | 1, l, r);
    a[num].sum = a[num << 1].sum + a[num << 1 | 1].sum;
    a[num].mmax = max(a[num << 1].mmax, a[num << 1 | 1].mmax);
}

void query(ll num, ll l, ll r)
{
    if(a[num].L > r || a[num].R < l)
        return ;
    if(a[num].L >= l && a[num].R <= r)
    {
        ans += a[num].sum;
        return ;
    }
    if(a[num].L == a[num].R)
        return ;
    query(num << 1, l, r);
    query(num << 1 | 1, l, r);
}

int main()
{
    ll cnt = 1, order, x, y;
    while(~scanf("%lld", &n))
    {
        for(ll i = 1; i <= n; ++i)
            scanf("%lld", &val[i]);
        init(1, 1, n);
        cout << "Case #" << cnt++ << ":\n";
        scanf("%lld", &k);
        while(k--)
        {
            scanf("%lld %lld %lld", &order, &x, &y);
            if(x > y)
                swap(x, y);
            if(order == 1)
            {
                ans = 0, query(1, x, y);
                cout << ans << '\n';
            }
            else
                update(1, x, y);
        }
        cout << '\n';
    }
    return 0;
}