P4145——线段树点修改&&模板题

题目

题意：对一个数列进行以下两种操作：

给$[l,r]$中的每个数开平方(下取整)
询问$[l,r]$中各个数的和

解决方法

显然，区间开平方不满足区间可加性，所以对区间中每个数开平方不能通过标记完成，只能使用暴力的单点修改。因为1e12的数开方6次就变成了1，所以需要修改的次数实际上很少。同时维护一个区间最大值maxv，如果maxv大于1才需要进行开平方操作。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int INF = 0x3f3f3f3f;
 6 const int maxn = 100000 + 10;
 7 ll maxv[maxn << 2], sum[maxn << 2];
 8 int n;
 9 ll a[maxn];
10 
11 void build(int o, int L, int R)
12 {
13     //printf("o:%d  L:%d  R:%d
", o, L, R);
14     int M = L + (R-L) / 2;
15     if(L == R)
16     {
17          maxv[o] = a[L];
18          sum[o] = a[L];
19     }
20     else
21     {
22         build(2*o, L, M);
23         build(2*o+1, M+1, R);
24         maxv[o] = max(maxv[2*o], maxv[2*o+1]);
25         sum[o] = sum[2*o] + sum[2*o+1];
26     }
27 }
28 
29 int ql, qr;    //查询[ql, qr]中的和
30 void query(int o,int L,int R, ll& ssum)
31 {
32     //printf("o:%d  L:%d  R:%d
", o, L, R);
33     if(ql <= L && R <= qr)
34     {
35         //maxx =  maxv[o];
36         ssum = sum[o];
37     }
38     else
39     {
40         int M = L + (R - L) / 2;
41         //maxx = -INF;
42         ll lsum =0, rsum = 0;
43         if(ql <= M)  query(2*o, L, M, lsum);
44         if(qr > M)  query(2*o+1, M+1, R, rsum);
45         //maxx = max(lmax, rmax);
46         ssum = lsum + rsum;
47 
48     }
49 }
50 
51 int cl, cr;  //修改sqrt(A[cl...cr])
52 void update(int o, int L, int R)
53 {
54     //printf("o:%d  L:%d  R:%d
", o, L, R);
55     if(L == R)   //更新叶子结点
56     {
57         maxv[o] = (ll)sqrt(maxv[o]);
58         sum[o] = maxv[o];
59     }
60     else
61     {
62         int M = L + (R-L)/2;
63         if(cl <= M && maxv[2*o] > 1)  update(2*o, L ,M);
64         if(cr > M && maxv[2*o+1] > 1)  update(2*o+1, M+1, R);
65         maxv[o] = max(maxv[2*o], maxv[2*o+1]);  //更新非叶子结点
66         sum[o] = sum[2*o] + sum[2*o+1];
67     }
68 }
69 
70 int main()
71 {
72     scanf("%d", &n);
73     for(int i = 1;i <= n;i++)  scanf("%lld", &a[i]);
74 
75     build(1, 1, n);
76 
77     int T;
78     scanf("%d", &T);
79     while(T--)
80     {
81         int order, l, r;
82         scanf("%d%d%d", &order, &l, &r);
83         if(l > r)  swap(l, r);
84         if(order == 0)
85         {
86             cl = l; cr = r;
87             update(1, 1, n);
88         }
89         else
90         {
91             ll ans = 0;
92             ql = l; qr = r;
93             query(1, 1, n, ans);
94             printf("%lld
", ans);
95         }
96     }
97 
98     return 0;
99 }

看讨论区还有分块、树状数组+并查集等做法，Orz.