原题题面

描述

andy在他的庄园里种了n棵树，排列成一排，标号为1到n。最开始的时候n棵树的高度都是0，也就是种子刚刚被埋下，树还没有长出来。

andy会一种魔法，他每使用一次魔法，就可以让树标号落在连续区间[l, r]里的树的高度增加1。他可以使用q次这种魔法，然后他很好奇，在使用了q次魔法之后，他的所有树的高度分别是多少呢？

输入

第一行输入两个整数n，q。(1<= n, q <= 1e5)

接下来q行，每行输入两个整数l, r(l <= r)，表示andy让标号落在区间[l, r]里的数高度都加1。

输出

输出有一行n个整数，每个整数后面有空格。输出末尾没有换行。

第i个数表示第i棵树的高度。

样例输入

10 3
1 3
2 4
3 3

样例输出

1 2 3 1 0 0 0 0 0 0

提示

andy种了10棵树

第一次使用魔法使得1、2、3棵树的高度增加1,

所有树的高度为

1 1 1 0 0 0 0 0 0 0

第二次使用魔法使得2、3、4棵树的高度增加1，

所有树的高度为

1 2 2 1 0 0 0 0 0 0

第三次使用魔法使得第3棵树的高度增加1

所有树的高度为

1 2 3 1 0 0 0 0 0 0

解析

不愧是C艹

刚看到题目，也就想到了用暴力做（蒟蒻实在没有什么好法子了），于是用一个数组记录每一棵树的高度，易得代码：

#include
   
using namespace std;
int n,q;
int l,r;
int a[5000000];
int main(){
cin>>n>>q;
while(q—){
cin>>l>>r;
for(int i=l;i<=r;i++){
a[i]++;
}
}
for(int i=1;i<=n;i++){
cout<
<a[i]<<” ”;="" }="" return="" 0;="" }<="" re="">
1
 <p>
2
  <!-- /wp:enlighter/codeblock --></p>
3

4
 <p>
5
  <!-- wp:image {"align":"center","id":143,"sizeSlug":"large","linkDestination":"none"} --></p>
6

7
 <div class="wp-block-image">
8

9
  <figure class="aligncenter size-large">
10
   <img src="https://blog.amzcd.top:32323/wp-content/uploads/2021/04/image-1024x86.png" alt="" class="wp-image-143" />
11
  </figure>
12

13
 </div>
14

15
 <p>
16
  <!-- /wp:image --></p>
17

18
 <p>
19
  <!-- wp:paragraph --></p>
20

21
 <p>众所周知，然后就……<code>TLE</code>了。</p>
22

23
 <p>
24
  <!-- /wp:paragraph --></p>
25

26
 <p>
27
  <!-- wp:heading --></p>
28

29
 <h2>学习新知</h2>
30

31
 <p>
32
  <!-- /wp:heading --></p>
33

34
 <p>
35
  <!-- wp:paragraph --></p>
36

37
 <p>待老师讲解该题时，才了解到要使用一种<code>差分</code>的思想。</p>
38

39
 <p>
40
  <!-- /wp:paragraph --></p>
41

42
 <p>
43
  <!-- wp:heading {"level":3} --></p>
44

45
 <h3>所谓差分</h3>
46

47
 <p>
48
  <!-- /wp:heading --></p>
49

50
 <p>
51
  <!-- wp:heading {"level":4} --></p>
52

53
 <h4>概念</h4>
54

55
 <p>
56
  <!-- /wp:heading --></p>
57

58
 <p>
59
  <!-- wp:paragraph --></p>
60

61
 <p>我们用数组来记录差分，<code>a[i]</code>表示的是<code>第i个元素</code>与<code>第i-1个元素</code>之差。</p>
62

63
 <p>
64
  <!-- /wp:paragraph --></p>
65

66
 <p>
67
  <!-- wp:heading {"level":4} --></p>
68

69
 <h4>基本操作</h4>
70

71
 <p>
72
  <!-- /wp:heading --></p>
73

74
 <p>
75
  <!-- wp:list --></p>
76

77
 <ul>
78

79
  <li>加/减第i个数字：将<code>a[i]&plusmn;x</code>，<code>a[i+1]&plusmn;(-x)</code>。</li>
80

81
  <li>同时加/减第i~j个数字：将<code>a[i]&plusmn;x</code>，<code>a[j+1]&plusmn;(-x)</code>。</li>
82

83
  <li>还原数字：遍历<code>a</code>数组，并用<code>sum</code>累加当前值。结束当前一次累加后，<code>sum</code>即为该数字。</li>
84

85
 </ul>
86

87
 <p>
88
  <!-- /wp:list --></p>
89

90
 <p>
91
  <!-- wp:heading {"level":3} --></p>
92

93
 <h3>代码实现</h3>
94

95
 <p>
96
  <!-- /wp:heading --></p>
97

98
 <p>
99
  <!-- wp:enlighter/codeblock {"language":"cpp"} --></p>
100

101
 <pre class="EnlighterJSRAW" data-enlighter-language="cpp" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">#include
102
  <bits tdc++.h="">
展开收起
using namespace std;
int n,q,a[100005],l,r;
//a[i]表示第i棵树比第i-1棵树高多少 差分
int main(){
cin>>n>>q;
for(int qwq=1;qwq<=q;qwq++){
cin>>l>>r;
a[l]++;//第l棵树比前面一棵树高1，且后面的树
a[r+1]—;//到r位置都一样高，第r+1棵树是原来那么高，所以减一减回去
}
for(int i=1;i<=n;i++){
a[i]+=a[i-1];
cout<
<a[i]<<” ”;="" }="" return="" 0;="" }<="" re="">
1
    <p>
2
     <!-- /wp:enlighter/codeblock --></p>
3

4
    <p>
5
     <!-- wp:quote --></p>
6

7
    <blockquote class="wp-block-quote">
8
     <p>QWQ.</p>
9

10
    </blockquote>
11

12
    <p>
13
     <!-- /wp:quote --></p>
14

15
    <p>
16
     <!-- wp:heading {"level":1} --></p>
17

18
    <h1>最后的最后</h1>
19

20
    <p>
21
     <!-- /wp:heading --></p>
22

23
    <p>
24
     <!-- wp:paragraph --></p>
25

26
    <p>总结一下<strong>前缀和</strong>和<strong>差分</strong>的异同点。</p>
27

28
    <p>
29
     <!-- /wp:paragraph --></p>
30

31
    <p>
32
     <!-- wp:table {"hasFixedLayout":true,"className":"is-style-stripes"} --></p>
33

34
    <figure class="wp-block-table is-style-stripes">
35

36
     <table class="has-fixed-layout">
37

38
      <tbody>
39

40
       <tr>
41

42
        <td>：）</td>
43

44
        <td>前缀和</td>
45

46
        <td>差分</td>
47

48
       </tr>
49

50
       <tr>
51

52
        <td>记录值</td>
53

54
        <td>Σa[i]-&gt;a[n]</td>
55

56
        <td>a[i]-a[i-1]</td>
57

58
       </tr>
59

60
       <tr>
61

62
        <td>预处理</td>
63

64
        <td>遍历数组，O(n)</td>
65

66
        <td>O(1)</td>
67

68
       </tr>
69

70
       <tr>
71

72
        <td>计算a[n]</td>
73

74
        <td>O(1)</td>
75

76
        <td>遍历数组，O(n)</td>
77

78
       </tr>
79

80
       <tr>
81

82
        <td>特点/适用题型</td>
83

84
        <td>高效求出连续一段和</td>
85

86
        <td>连续一段同时加减</td>
87

88
       </tr>
89

90
      </tbody>
91

92
     </table>
93

94
    </figure>
95

96
    <p>
97
     <!-- /wp:table --></p>
98

99
   </a[i]<<">
100
  </bits></pre>
101
</a[i]<<">
展开收起