网站及系统建设维护,wordpress主题后台汉化,服务器上建设网站,制作视频的软件哪个最好免费的题目链接#xff1a; http://acm.hdu.edu.cn/showproblem.php?pid4027 题意及思路#xff1a; 有一排战舰#xff0c;给出每个战舰的能力值#xff0c;存在两种操作#xff1a;第一种是把一定范围内所有战舰能力值开根号并向下取整#xff0c;第二种是求一定区域内所有战… 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid4027 题意及思路 有一排战舰给出每个战舰的能力值存在两种操作第一种是把一定范围内所有战舰能力值开根号并向下取整第二种是求一定区域内所有战舰能力值之和。如果我们暴力递归更新区间上的每一个点会TLE(不要问我是怎么知道的)。我们可以稍微做一些优化。例如能力值01。它们开根号还是它们本身不需要更新。我们可以增加一个标记tag。如果这个区间都是0或者1我们就把tag标记为1。以后我们再次更新的时候如果区间tag为1我们就不继续向下递归。 代码 1 #include iostream2 #include cmath3 #include algorithm4 #include cstdio5 #include cstring6 #define maxn 10000057 #define LL long long8 using namespace std;9 typedef struct node
10 {
11 LL a;
12 int tag;
13 }node;
14 node tree[maxn2];
15 void pushup(int rt) //更新节点的和以及tag值
16 {
17 tree[rt].atree[rt1].atree[rt1|1].a;
18 if(tree[rt1].tagtree[rt1|1].tag)
19 tree[rt].tag1;
20 return ;
21 }
22 int build(int l,int r,int rt)
23 {
24 if(lr)
25 {
26 scanf(%lld,tree[rt].a);
27 if(tree[rt].a0||tree[rt].a1)
28 tree[rt].tag1;
29 return 1;
30 }
31 int m(lr)1;
32 build(l,m,rt1);
33 build(m1,r,rt1|1);
34 pushup(rt);
35 }
36 void update(int L,int R,int l,int r,int rt)
37 {
38 if( Ll r Rtree[rt].tag1) //如果区间tag值为1直接返回
39 return ;
40 if(lr)
41 {
42 tree[rt].a(LL)(sqrt(1.0*tree[rt].a));
43 if(tree[rt].a1||tree[rt].a0)
44 tree[rt].tag1;
45 return ;
46 }
47 int m(lr)1;
48 if(L m)
49 update(L,R,l,m,rt1);
50 if(R m)
51 update(L,R,m1,r,rt1|1);
52 pushup(rt);
53 }
54 LL query(int L,int R,int l,int r,int rt)
55 {
56 if(L l r R)
57 {
58 return tree[rt].a;
59 }
60 int m(lr)1;
61 LL ans0;
62 if(L m)
63 ansquery(L,R,l,m,rt1);
64 if(R m)
65 ansquery(L,R,m1,r,rt1|1);
66 return ans;
67 }
68 int main()
69 {
70 int n,jishu;
71 jishu0;
72 while(scanf(%d,n)!EOF)
73 {
74 printf(Case #%d:\n,jishu);
75 build(1,n,1);
76 int k;
77 scanf(%d,k);
78 while(k--)
79 {
80 int c,a,b;
81 scanf(%d%d%d,c,a,b);
82 if(ab)
83 swap(a,b);
84 if(c0)
85 update(a,b,1,n,1);
86 else
87 coutquery(a,b,1,n,1)endl;
88 }
89 coutendl;
90 }
91 } 转载于:https://www.cnblogs.com/blame/p/11369474.html
