首页 > 代码库 > BZOJ3212: Pku3468 A Simple Problem with Integers
BZOJ3212: Pku3468 A Simple Problem with Integers
3212: Pku3468 A Simple Problem with Integers
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 810 Solved: 354
[Submit][Status]
Description
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
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
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
55
9
15
HINT
The sums may exceed the range of 32-bit integers.
Source
题解：
想了想树状数组如何维护区间修改，区间求和，觉得貌似很简单？
差分了之后 用树状数组维护 a[i] 以及 i*a[i] 即可
sum(1,n)=(n+1)*sigma(a[i])-sigma(i*a[i])
靠着树状数组刷进了第一页。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+1000 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline ll read() 48 49 { 50 51 ll x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 ll s[2][maxn],n,m; 61 inline void add(int k,int x,ll y) 62 { 63 for(;x<=n;x+=x&(-x))s[k][x]+=y; 64 } 65 inline ll sum(int k,int x) 66 { 67 ll t=0; 68 for(;x;x-=x&(-x))t+=s[k][x]; 69 return t; 70 } 71 72 int main() 73 74 { 75 76 freopen("input.txt","r",stdin); 77 78 freopen("output.txt","w",stdout); 79 80 n=read();m=read(); 81 ll x=0,y,z; 82 for(ll i=1;i<=n;i++) 83 { 84 y=read(); 85 add(0,i,y-x); 86 add(1,i,i*(y-x)); 87 x=y; 88 } 89 while(m--) 90 { 91 char ch[2]; 92 scanf("%s",ch); 93 if(ch[0]==‘C‘) 94 { 95 x=read();y=read();z=read(); 96 add(0,x,z);add(1,x,x*z); 97 add(0,y+1,-z);add(1,y+1,(-z)*(y+1)); 98 } 99 else100 {101 x=read();y=read();102 ll sum1=(x)*sum(0,x-1)-sum(1,x-1);103 ll sum2=(y+1)*sum(0,y)-sum(1,y);104 printf("%lld\n",sum2-sum1);105 }106 }107 108 return 0;109 110 }
BZOJ3212: Pku3468 A Simple Problem with Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。