Andy种树

原题题面

描述

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
   <bits tdc++.h="">

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="">

     

      

     

      

     


      

       
      

     

     

      

     

      

     
众所周知，然后就……TLE了。

     

      

     

      

     
学习新知

     

      

     

      

     
待老师讲解该题时，才了解到要使用一种差分的思想。

     

      

     

      

     
所谓差分

     

      

     

      

     
概念

     

      

     

      

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

     

      

     

      

     
基本操作

     

      

     

      

     


      
加/减第i个数字：将a[i]±x，a[i+1]±(-x)。

      
同时加/减第i~j个数字：将a[i]±x，a[j+1]±(-x)。

      
还原数字：遍历a数组，并用sum累加当前值。结束当前一次累加后，sum即为该数字。

     

     

      

     

      

     
代码实现

     

      

     

      

     
#include
      <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="">

        

         

        

         

        

         
QWQ.

        

        

         

        

         

        
最后的最后

        

         

        

         

        
总结一下前缀和和差分的异同点。

        

         

        

         

        


         


          


           


            
：）

            
前缀和

            
差分

           

           


            
记录值

            
Σa[i]->a[n]

            
a[i]-a[i-1]

           

           


            
预处理

            
遍历数组，O(n)

            
O(1)

           

           


            
计算a[n]

            
O(1)

            
遍历数组，O(n)

           

           


            
特点/适用题型

            
高效求出连续一段和

            
连续一段同时加减

           

          

         

        

        

         

       </a[i]<<">
      </bits>
    </a[i]<<">
   </bits>