外贸自建站平台价格,安装失败未能找到wordpress目录,上海网站建设网站制作,鞍山百姓网B - 秋实大哥与花 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status秋实大哥是一个儒雅之人#xff0c;昼听笙歌夜醉眠#xff0c;若非月下即花前。 所以秋实大哥精心照料了很多花朵。现在所有的花朵排成了一行#xff… B - 秋实大哥与花 Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status 秋实大哥是一个儒雅之人昼听笙歌夜醉眠若非月下即花前。 所以秋实大哥精心照料了很多花朵。现在所有的花朵排成了一行每朵花有一个愉悦值。 秋实大哥每天要对着某一段连续的花朵歌唱然后这些花朵的愉悦值都会增加一个相同的值v(v可能为负)。 同时他想知道每次他唱完歌后这一段连续的花朵的愉悦值总和是多少。 Input 第一行有一个整数n表示花朵的总数目。 第二行包含n个整数ai表示第i朵花初始的愉悦值。 第三行包含一个整数m表示秋实大哥唱了m天的歌。 接下来m行每行包含三个整数l r v表示秋实大哥对着[l,r]这个区间内的花朵歌唱每朵花的愉悦值增加了v。 1≤nmai|v|≤1000001≤l≤r≤n。 Output 输出共m行第i行表示秋实大哥完成第i天的歌唱后那一段花朵的愉悦值总和。 Sample input and output Sample InputSample Output 3
0 0 0
3
1 2 1
1 2 -1
1 3 1 2
0
3 解题报告: 没啥好说的线段树模板基础题。。唯一需要注意的就是long long了. 当然我是使用的树状数组: 题目中操作属于区间更新 - 区间查询查询点也是区间嘛类型可使用树状数组来实现. 令C[i]为从1至i号花的共同更新之和. 首先考虑更新,add[l,r,v] → c[r] v , c[l-1] -v; Sum[x] 从 1 至 x 号花的value之和. Sum[x] c[1]*1 c[2]*2 c[3] * 3 ..... c[x] * x (c[x1] .... C[n] ) *x; (segema)f(x) (segema)g(x) * x; 两个树状数组一个维护 c[i]*i ,一个维护c[i] 之后考虑区间查询: Query(l , r) sum[r] - sum[l-1] 1 #include iostream2 #include cstring3 typedef long long ll;4 using namespace std;5 const int maxn 1e5 50;6 ll n;7 ll f[maxn],g[maxn];8 9
10 inline ll lowbit(ll idx)
11 {
12 return idx (-idx);
13 }
14
15 void updataf(ll idx,ll res)
16 {
17 if (!idx)
18 return;
19 while(idx n)
20 {
21 f[idx] res;
22 idx lowbit(idx);
23 }
24 }
25
26 void updatag(ll idx,ll res)
27 {
28 if (!idx)
29 return;
30 while(idx n)
31 {
32 g[idx] res;
33 idx lowbit(idx);
34 }
35 }
36
37 ll sumf(ll idx)
38 {
39 ll res 0;
40 while(idx 0)
41 {
42 res f[idx];
43 idx - lowbit(idx);
44 }
45 return res;
46 }
47
48 ll sumg(ll idx)
49 {
50 ll res 0;
51 while(idx 0)
52 {
53 res g[idx];
54 idx - lowbit(idx);
55 }
56 return res;
57 }
58
59 int main(int argc,char *argv[])
60 {
61 ll m;
62 scanf(%lld%lld,n,m);
63 memset(f,0,sizeof(f));
64 memset(g,0,sizeof(g));
65 for(int j 1 ; j n ; j)
66 {
67 ll v;
68 scanf(%lld,v);
69 updataf(j,v*j);
70 updataf(j-1,-v*(j-1));
71 updatag(j,v);
72 updatag(j-1,-v);
73 }
74 while(m--)
75 {
76 ll i,j,v;
77 scanf(%lld%lld%lld,i,j,v);
78 updataf(j,v*j);
79 updataf(i-1,-v*(i-1));
80 updatag(j,v);
81 updatag(i-1,-v);
82 i--;
83 ll res1 sumf(i) i*(sumg(n)-sumg(i));
84 ll res2 sumf(j) j*(sumg(n)-sumg(j));
85 printf(%lld\n,res2 - res1);
86 }
87 return 0;
88 } 转载于:https://www.cnblogs.com/Xiper/p/4470205.html
