Problem - 4027 (hdu.edu.cn)
许多邪恶的战舰在战斗前排成一排。我们的指挥官决定使用我们的秘密武器来消灭战列舰。每艘战列舰都可以标记为耐力值。对于我们秘密武器的每一次攻击，它都可能降低连续部分战列舰的续航能力，使它们的续航力达到其原始续航力值的平方根。在我们的秘密武器的一系列攻击中，指挥官想要评估武器的效果，所以他向你寻求帮助。
您被要求回答以下问题：战列舰线连续部分的耐力之和。
请注意，平方根运算应向下舍入为整数。
输入
输入包含多个测试用例，由 EOF 终止。对于每个测试用例，第一行包含一个整数 N，表示一行中有 N 艘邪恶的战舰。（1 <= N <= 100000）
第二行包含N个整数Ei，表示每艘战列舰从该行开始到结束的续航值。您可以假设所有耐力值的总和小于 263。
下一行包含一个整数 M，表示操作和查询的数量。（1 <= M <= 100000）
对于以下 M 行，每行包含三个整数 T、X 和 Y。T=0表示秘密武器的动作，这将降低第X号和第Y号战列舰之间的战列舰的续航值。T=1 表示指挥官的查询，要求战列舰在 X 号和 Y 号之间的耐力值之和，包括在内。
输出
对于每个测试用例，请在第一行打印案例编号。然后为每个查询打印一行。请记住，在每个测试用例之后都要跟一个空行。
思路
使用线段树。因为一个数x连续开方最终到1只需要很少的次数，所以我们当更新区间的时候直接暴力更新，而且一旦发现区间和小于等于区间长度代表不需要更新了。其余操作均为线段树处理区间的通用操作，贴出代码：
1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
2 #define bug(x) cout<<#x<<" is "<<x<<endl
3 #include <iostream>
4 #include <list>
5 #include <unordered_map>
6 #include <map>
7 #include <vector>
8 #include <sstream>
9 #include <cmath>
10 #include <algorithm>
11 #define iter ::iterator
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int>P;
15 #define pb push_back
16 #define mk make_pair
17 #define se second
18 #define fi first
19 #define rs o*2+1
20 #define ls o*2
21 const ll mod=1e9+7;
22 const int N=1e5+5;
23
24
25 int n;
26
27 ll a[N],sum[N*4];
28
29
30 void build(int o,int l,int r){
31 if(l==r){
32 sum[o]=a[l];
33 return;
34 }
35 int m=(l+r)/2;
36 build(ls,l,m);
37 build(rs,m+1,r);
38 sum[o]=sum[ls]+sum[rs];
39 }
40
41 ll qu(int o,int l,int r,int ql,int qr){
42 if(l>=ql&&r<=qr)return sum[o];
43 if(l>qr||r<ql)return 0;
44 int m=(l+r)/2;
45 ll lsum=qu(ls,l,m,ql,qr);
46 ll rsum=qu(rs,m+1,r,ql,qr);
47 return lsum+rsum;
48 }
49
50 void up(int o,int l,int r,int ql,int qr){
51
52 if(sum[o]<=(r-l+1))return;
53
54 if(l>qr||r<ql)return;
55 if(l==r){
56 sum[o]=sqrt(sum[o]);
57 return;
58 }
59 int m=(l+r)/2;
60 up(ls,l,m,ql,qr);
61 up(rs,m+1,r,ql,qr);
62 sum[o]=sum[ls]+sum[rs];
63 }
64
65 int main(){
66
67 int Case=0;
68 while(~scanf("%d",&n)){
69 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
70
71 Case++;
72 printf("Case #%d:\n", Case);
73 build(1,1,n);
74
75 int q;
76 scanf("%d",&q);
77
78
79 while(q--){
80 int op,L,R;
81 scanf("%d%d%d",&op,&L,&R);
82 if(L>R)swap(L,R);
83 if(op==0){
84 up(1,1,n,L,R);
85 }
86 else{
87
88 printf("%lld\n",qu(1,1,n,L,R));
89 //cout<<qu(1,1,n,L,R)<<endl;
90 }
91 }
92 printf("\n");
93 }
94
95
96
97 }
标签：ll,int,线段,战列舰,hdu4027,区间,include,sum,define From： https://www.cnblogs.com/ccsu-kid/p/18202857