POJ3468 A Simple Problem with Integers

摘要:
描述给出了一个序列。您需要处理以下两种查询。“Cabc”表示将c添加到[a,b]间隔中的所有值。“Qab”询问[a,b]区间中所有值的总和。输入的第一行包含两个整数N和Q。1≤N,Q≤100000。第二行包含n个整数,表示初始序列A。接下来,在标题描述格式的Q行询问。输出对于每个Q查询,您需要输出相应的答案,每个答案一行。

Description

给出了一个序列,你需要处理如下两种询问。

"C abc"表示给[a, b]区间中的值全部增加c (-10000  c  10000)

"Q ab" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 N,Q  100000.

第二行包含n个整数,表示初始的序列A (-1000000000  Ai 1000000000)。

接下来Q行询问,格式如题目描述。

Output

对于每一个Q开头的询问,你需要输出相应的答案,每个答案一行。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15


依旧是线段树操作,注意数据范围用long long

 1 //#include<bits/stdc++.h>//POJ不吃这条
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 struct NODE{
 9     int l,r;
10     long long sum,t;
11 }node[1500000];
12 int data[500000];
13 int n,m;
14 void Build(int num,int left,int right){//以num为根建线段树 
15     node[num].l=left;
16     node[num].r=right;
17     if(left==right){
18         node[num].sum=data[left];
19         return;
20     }
21     int mid=(left+right)/2;
22     Build(num*2,left,mid);
23     Build(num*2+1,mid+1,right);
24     node[num].sum=node[num*2].sum+node[num*2+1].sum;
25     return;
26 }
27 
28 void update(int num){//标记下传
29     node[num<<1].t+=node[num].t;
30     node[num*2+1].t+=node[num].t;
31     node[num<<1].sum+=(node[num<<1].r-node[num<<1].l+1)*node[num].t;
32     node[num*2+1].sum+=(node[num*2+1].r-node[num*2+1].l+1)*node[num].t;
33     node[num].t=0;
34     return;
35 }
36 long long qu(int l,int r,int num){//求和 
37     if(node[num].r<l || node[num].l>r)return 0;
38     if(node[num].l>=l && node[num].r<=r)return node[num].sum;
39     if(node[num].t)update(num);
40     return qu(l,r,num<<1)+qu(l,r,num*2+1);
41 }
42 void change(int l,int r,int c,int num){
43     if(node[num].r<l || node[num].l>r)return;
44     if(node[num].l>=l && node[num].r<=r){
45         node[num].sum+=c*(node[num].r-node[num].l+1);
46         node[num].t+=c;
47         return;
48     }
49     if(node[num].t)update(num);
50     change(l,r,c,num<<1);
51     change(l,r,c,num*2+1);
52     node[num].sum=node[num<<1].sum+node[num*2+1].sum;
53     return;
54 }
55 int main(){
56     scanf("%d%d",&n,&m);
57     int i,j;
58     for(i=1;i<=n;i++)scanf("%d",&data[i]);
59     Build(1,1,n);
60     char s;
61     int a,b,c;
62     for(i=1;i<=m;i++)
63     {
64         cin>>s;
65         if(s=='C'){
66             scanf("%d%d%d",&a,&b,&c);
67             change(a,b,c,1);
68         }
69         if(s=='Q'){
70             scanf("%d%d",&a,&b);
71             printf("%lld
",qu(a,b,1));
72         }
73     }
74     return 0;
75 }


因为printf里忘了用lld而WA,纠结了半个多小时才意识到问题所在←又犯了这种蠢错误

免责声明:文章转载自《POJ3468 A Simple Problem with Integers》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[HDOJ1233]还是畅通工程聊聊分布式存储系统的Decommission和Maintenance模式下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

P1772 [ZJOI2006]物流运输

//Pro: 1003: [ZJOI2006]物流运输 //cost[i][j]表示第i天到第j天的最短路长度 //f[i]表示前i天的最小花费 //f[i]=min(f[j-1]+cost[j][i]*(i-j+1)+k) ,j<=i //输出f[n]即为答案 #include<iostream>#include<cstdi...

while 循环、格式化输出、运算符

while 循环 结构: while 条件: 循环语句 死循环 while True: 没有break语句情况下 终止循环 一、 改变条件 (标志位的概念):一般默认使用flag来作为标志位。 flag = True num = 0 while flag: print(num) num = num + 1 if n...

BZOJ 3544 treap (set)

我只是想找个treap的练习题…… 每回找到lower_bound 就好啦 //By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define int long long int...

phonegap 安装和使用eclipse

1.下载nodejs。。。然后注销让nodejs可用 2.下载jdk,ant。和安卓的sdk。 jdk是为ant编译时需要,设置JAVA_HOME环境变量 C:Program FilesJavajdk1.8.0_05 降ant和sdk的路径添加到path中。。 C:Program Files (x86)Gitin;C:UsersAdministra...

C#递归树

1 protected void Page_Load(objectsender, EventArgs e) 2 { 3 bindtree(PopId); 4 } 5 private voidbindtree() 6 { 7 TreeView1.Nodes.Clear(); 8 AddTree(0, (TreeNode)null); 9 }...

collections模块

一. tuple功能 特点:不可变,可迭代,可拆包,但tuple不可变性不是绝对的 其实只要类里包含__iter__或者__getitem__任一个魔法函数都是可迭代的 1. 拆包 1.1 基本用法 name = ("jack", "hong") # 按位置赋值给变量 name1, name2 = name print(name1, name2) 输出...