「SPOJ 2713」Can you answer these queries IV

发表于 |
字数统计: 778 | 阅读时长 ≈ 4

给一段正整数构成的区间，支持区间开平方以及询问区间和。

链接

SPOJ 2713

题解

考虑线段树，显然区间开平方是不能用的，所以我们选择暴力修改。
先证明一个引理，区间最大值为的区间进行修改是没有意义的。（这个证明算是补了一个坑）
证明：由于区间内所有数是正整数，所以区间最大值为的区间内所有数均为，而，故修改区间内的值没有意义，证毕。
于是我们考虑在修改区间时判断一下当前区间最大值是不是，如果是，就没有修改的必要。如果这个节点的左右端点重合，直接修改即可，这样可以少修改许多修改了也没用的区间，至于查询还是一样的。
提醒大家有多组数据，记得初始化

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MAXN=1e5+51;
struct SegmentTree{
    ll l,r,sum,maxn;
};
SegmentTree tree[MAXN<<2];
ll cnt,qcnt,op,l,r,ccnt;
ll num[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void update(ll node)
{
    tree[node].sum=tree[node<<1].sum+tree[(node<<1)|1].sum;
    tree[node].maxn=max(tree[node<<1].maxn,tree[(node<<1)|1].maxn);
}
inline void create(ll l,ll r,ll node)
{
    tree[node].l=l,tree[node].r=r;
    if(l==r)
    {
        tree[node].sum=tree[node].maxn=num[l];
        return;
    }
    ll mid=(l+r)>>1;
    create(l,mid,node<<1);
    create(mid+1,r,(node<<1)|1);
    update(node);
}
inline void change(ll l,ll r,ll node)
{
    if(tree[node].maxn<=1)
    {
        return;
    }
    if(tree[node].l==tree[node].r)
    {
        tree[node].sum=tree[node].maxn=sqrt(tree[node].sum);
        return;
    }
    ll mid=(tree[node].l+tree[node].r)>>1;
    if(l<=mid)
    {
        change(l,r,node<<1);
    }
    if(r>mid)
    {
        change(l,r,(node<<1)|1);
    }
    update(node);
}
inline ll querySum(ll l,ll r,ll node)
{
    if(l<=tree[node].l&&r>=tree[node].r)
    {
        return tree[node].sum;
    }
    ll mid=(tree[node].l+tree[node].r)>>1,res=0;
    if(l<=mid)
    {
        res+=querySum(l,r,node<<1);
    }
    if(r>mid)
    {
        res+=querySum(l,r,(node<<1)|1);
    }
    return res;
}
inline ll queryMax(ll l,ll r,ll node)
{
    if(l<=tree[node].l&&r>=tree[node].r)
    {
        return tree[node].maxn;
    }
    ll mid=(tree[node].l+tree[node].r)>>1,res=0;
    if(l<=mid)
    {
        res=max(res,queryMax(l,r,node<<1));
    }
    if(r>mid)
    {
        res=max(res,queryMax(l,r,(node<<1)|1));
    }
    return res;
}
int main()
{
    while(scanf("%lld",&cnt)!=EOF)
    {
        printf("Case #%lld:\n",++ccnt);
        for(register int i=1;i<=cnt;i++)
        {
            num[i]=read();
        }
        create(1,cnt,1);
        qcnt=read();
        for(register int i=0;i<qcnt;i++)
        {
            op=read(),l=read(),r=read();
            if(l>r)
            {
                swap(l,r);
            }
            if(op)
            {
                printf("%lld\n",querySum(l,r,1));
            }
            else
            {
                if(queryMax(l,r,1)>1)
                {
                    change(l,r,1);
                }
            }
        }
        memset(num,0,sizeof(num));
        memset(tree,0,sizeof(tree));
        puts("");
    }
}