HDU - 4027 Can you answer these queries?（线段树）

给定一个长度为n的序列，m次操作。

每次操作

　　可以将一个区间内的所有数字变为它的根号。

　　可以查询一个区间内所有元素的和。

线段树的初级应用。

如果把一个区间内的元素都改为它的根号的话，是需要每个数字都进行修改的。这样就会超时。

一个优化就是区间修改的当区间时，若区间长度等于区间和，那这个区间里的所有元素都不用修改了。

而题目中区间里的元素之和最大是 2^63，时间完全够用。

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cmath>

using namespace std;

#define maxn 100000 + 1000

#define LL long long

#define in_int(x) int x; scanf("%d", &x);

struct Sect

{

        int l, r, flag;

        LL sum;

        Sect() : flag() {}

}

t[*maxn];

LL

        n, a[*maxn];

void build(int id, int l, int r)

{

        if (l == r)

        {

                t[id].sum = a[l];

                t[id].l = l, t[id].r = r;

                return;

        }

        int mid = (l+r) >> ;

        build(id*, l, mid);

        build(id*+, mid+, r);

        t[id].sum = t[id*].sum + t[id*+].sum;

        t[id].l = t[id*].l, t[id].r = t[id*+].r;

}

//void update(int id, int x, int val)

//{

//        if(t[id].l == t[id].r)

//        {

//                if (t[id].l == x) t[id].sum += val;

//                return;

//        }

//        int mid = (t[id].l+t[id].r) >> 1;

//        if (x <= mid) update(id*2, x, val);

//                else update(id*2+1, x, val);

//        t[id].sum = t[id*2].sum + t[id*2+1].sum;

//}

//void markdown(int id)

//{

//        t[id].flag = 0;

//        t[id].sum = (int)sqrt(t[id].sum);

//        if (t[id*2].flag) markdown(id*2);

//        t[id*2].flag = 1;

//        if (t[id*2+1].flag) markdown(id*2+1);

//        t[id*2+1].flag = 1;

//}

LL query(int id, int l, int r)

{

        //if(t[id].flag) markdown(id);

        if (t[id].l >= l && t[id].r <= r) return t[id].sum;

        int mid = (t[id].l + t[id].r) >> ;

        if (r <= mid) return query(id*, l, r);

                else if (l > mid) return query(id*+, l, r);

                else return query(id*, l, mid) + query(id*+, mid+, r);

}

void change(int id, int l, int r)

{

        if (t[id].l == t[id].r)

        {

                t[id].sum = sqrt(t[id].sum);

                return;

        }

        if (t[id].r - t[id].l +  == t[id].sum) return;

        int mid = (t[id].l + t[id].r) >> ;

        if (r <= mid) change(id*, l, r);

                else if (l > mid) change(id*+, l, r);

                else

                {

                        change(id*, l, mid);

                        change(id*+, mid+, r);

                }

        t[id].sum = t[id*].sum + t[id*+].sum;

}

int main()

{

        int n, ca = ;

        while(scanf("%lld", &n) != EOF)

        {

                for (int i = ; i <= n; i++)

                        scanf("%lld", &a[i]);

                build(, , n);

                printf("Case #%d:\n", ++ca);

                in_int(m);

                for (int i = ; i <= m; i++)

                {

                        in_int(x);

                        in_int(l);

                        in_int(r);

                        if (l > r) swap(l, r);

                        if (x) printf("%lld\n", query(, l, r));

                                else change(, l, r);

                }

                printf("\n");

        }

}

巴特西

HDU - 4027 Can you answer these queries?（线段树）

最新文章

热门文章