# 3212: Pku3468 A Simple Problem with Integers

## 3212: Pku3468 A Simple Problem with Integers

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 1053  Solved: 468

[Submit][Status][Discuss]

## Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

## 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

4 55 9 15

## HINT

The sums may exceed the range of 32-bit integers.

## Source

PS：话说我的线段树居然全方位怒踩树状数组是什麽节奏啊啊啊QAQ（上面的是树状数组，下面的是线段树）

``` 1 /**************************************************************
2     Problem: 3212
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:268 ms
7     Memory:15852 kb
8 ****************************************************************/
9
10 var
11    b,c:array[0..1000005] of int64;
12    i,j,k,l,m,n:longint;a1:int64;ch:char;
14           begin
15                while x>0 do
16                      begin
17                           inc(b[x],y);
18                           dec(x,x and (-x));
19                      end;
20           end;
22           var z:int64;
23           begin
24                z:=x;if x=0 then exit;
25                while x<=n do
26                      begin
27                           inc(c[x],z*y);
28                           inc(x,x and (-x));
29                      end;
30           end;
31 function sumb(x:longint):int64;
32          begin
33               sumb:=0;if x=0 then exit;
34               while x<=n do
35                     begin
36                          inc(sumb,b[x]);
37                          inc(x,x and (-x));
38                     end;
39          end;
40 function sumc(x:longint):int64;
41          begin
42               sumc:=0;
43               while x>0 do
44                     begin
45                          inc(sumc,c[x]);
46                          dec(x,x and (-x));
47                     end;
48          end;
49 function summ(x:longint):int64;
50          begin
51               exit(sumb(x)*int64(x)+sumc(x-1));
52          end;
54           begin
57           end;
58 function sum(x,y:longint):int64;
59          begin
60               exit(summ(y)-summ(x-1));
61          end;
62 begin
64      fillchar(b,sizeof(b),0);
65      fillchar(c,sizeof(c),0);
66      for i:=1 to n do
67          begin
71      for i:=1 to m do
72          begin
74               case upcase(ch) of
75                    'Q':begin
77                             writeln(sum(j,k));
78                    end;
79                    'C':begin
82                    end;
83               end;
84          end;
85 end.```

``` 1 /**************************************************************
2     Problem: 3212
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:84 ms
7     Memory:15852 kb
8 ****************************************************************/
9
10 var
11    i,j,k,l,m,n:longint;a1:int64;ch:char;
12    a,b:array[0..1000005] of int64;
13 function min(x,y:longint):longint;
14          begin
15               if x<y then min:=x else min:=y;
16          end;
17 function max(x,y:longint):longint;
18          begin
19               if x>y then max:=x else max:=y;
20          end;
21 procedure built(z,x,y:longint);
22           begin
23                if x=y then
25                else begin
26                          built(z*2,x,(x+y) div 2);
27                          built(z*2+1,(x+y) div 2+1,y);
28                          a[z]:=a[z*2]+a[z*2+1];
29                     end;
30                b[z]:=0;
31           end;
33           begin
34                if l>r then exit;
35                if (x=l) and (y=r) then
36                   begin
37                        inc(b[z],t);
38                        exit;
39                   end;
40                inc(a[z],t*int64(r-l+1));
41                add(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
42                add(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
43           end;
44 function sum(z,x,y,l,r:longint;t:int64):int64;
45          var a1,a2:int64;
46          begin
47               if l>r then exit(0);
48               inc(t,b[z]);
49               if (x=l) and (y=r) then exit(a[z]+t*int64(y-x+1));
50               a1:=sum(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
51               a2:=sum(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
52               exit(a1+a2);
53          end;
54 begin
56      for i:=1 to m do
57          begin
59               case upcase(ch) of
60                    'Q':begin
62                             writeln(sum(1,1,n,j,k,0));
63                    end;
64                    'C':begin
67                    end;
68               end;
69          end;
70 end.```

0 条评论

• ### 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

• ### 算法模板——线段树7（骰子翻转问题）

实现功能：首先输入一个长度为N的序列，由1-4组成（1表示向前滚一下，2表示向后滚一下，3表示向左滚一下，4表示向右滚一下，骰子原始状态：上1前2左4右5后3下...

• ### 1854: [Scoi2010]游戏

1854: [Scoi2010]游戏 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2538  Solved:...

• ### 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列

1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列 Time Limit: 5 Sec  Memory Limit:...

• ### 爱奇艺视频格式转换工具

qsv是爱奇艺研发的一种视频文件格式，一般情况下，只能够用爱奇艺视频播放器才能播放，但是如果想要转换成其他视频格式或使用其他播放器播放该怎么办呢？这时候就需要用...

• ### “resize2fs: Permission denied to resize filesystem”

On CentOS/RHEL 6, an LVM volume group size has been extended and an attempt to d...

• ### 【数据挖掘】大数据用户画像的方法、实践与行业应用

从1991年Tim Berners-Lee发明了万维网（World Wide Web）开始，到20年后2011年，互联网真正走向了一个新的里程碑，进入了“大数据...

• ### Debian系统创建Sudo用户简单方法

为保障服务器的安全性，在安装Debian系统之后，首要任务就是使用root用户登录，然后创建一个Sudo用户，目的是为了以后尽量少用root用户登录。