[Solution][Data Structure][Segment Tree]BZOJ3211 花神游历各国

【题目】

戳这里

【题意】

支持区间开方下取整和区间求和,开始的整数不超过,数的个数和询问次数均不超过.

【思路】

注意到对于一个不超过的整数,最多连续开方5次就变成了1,再继续开方就不发生变化了。

使用线段树维护当前区间是否均为1,以及当前区间和。

修改区间时,如果当前区间不都是1,则暴力向下单点修改,并维护当前节点。

显然暴力修改的时间复杂度为.

询问的时间复杂度为.

因此总时间复杂度为.

【代码】

#include<cstdio>
#include<cstring>
#include<cmath>
#define N 201001
typedef long long LL;
LL val[N >> 1];
int l[N] , r[N] , dl[N] , dr[N] , ind;
bool sign[N];
LL sum[N];
inline void update(int x)
{
    sum[x] = sum[l[x]] + sum[r[x]];
    sign[x] = sign[l[x]] & sign[r[x]];
}
int build(int tl , int tr)
{
    int q = ++ind;
    dl[q] = tl;
    dr[q] = tr;
    if (tl == tr)
    {
        sum[q] = val[tl];
        sign[q] = (sum[q] == 1 || !sum[q]);
        return q;
    }
    int mid = (tl + tr) >> 1;
    l[q] = build(tl , mid);
    r[q] = build(mid + 1 , tr);
    update(q);
    return q;
}
inline LL query(int tl , int tr , int x)
{
    if (tl > tr)
        return 0;
    if (dl[x] >= tl && dr[x] <= tr)
        return sum[x];
    int mid = (dl[x] + dr[x]) >> 1;
    if (tl > mid)
        return query(tl , tr , r[x]);
    else if (tr <= mid)
        return query(tl , tr , l[x]);
    else
        return query(tl , mid , l[x]) + query(mid + 1 , tr , r[x]);
}
inline void modify(int tl , int tr , int x)
{
    if (tl > tr || sign[x])
        return;
    if (dl[x] == dr[x])
    {
        sum[x] = LL(sqrt(sum[x]));
        sign[x] = (sum[x] == 1 || !sum[x]);
        return;
    }
    int mid = (dl[x] + dr[x]) >> 1;
    if (tr <= mid)
        modify(tl , tr , l[x]);
    else if (tl > mid)
        modify(tl , tr , r[x]);
    else
    {
        modify(tl , mid , l[x]);
        modify(mid + 1 , tr , r[x]);
    }
    update(x);
}
int main()
{
    int n;
    scanf("%d" , &n);
    register int i;
    for(i = 1 ; i <= n ; ++i)
        scanf("%lld" , &val[i]);
    build(1 , n);
    int m , ask , a , b;
    scanf("%d" , &m);
    while(m--)
    {
        scanf("%d%d%d" ,&ask ,  &a , &b);
        if (ask == 1)
            printf("%lld\n" , query(a , b , 1));
        else
            modify(a , b , 1);
    }
    return 0;
}
comments powered by Disqus