1.5.7 uncle-lu的种草日记(题解)

Description

新北山上有一排空地，uncle-lu想重些草上去，于是乎他将这一排空地分割成nnn块并标上号1...n1...n1...n。(这片空地上什么草都没有)

你完全想不到，uncle-lu个有E技能，他一口气可以在一段连续的区间内种上一株草。例如，他想在区间[2,5][2,5][2,5]上种草，一个E！那空地[2,5][2,5][2,5]上草数量分别+1+1+1。当然uncle-lu身体没那么好，他只能使用mmm次E技能。

当uncle-lu用完mmm次E技能，他有qqq个疑惑，他想知道某一块草地上的草的数量。

Input

第一行包含3个正整数 分别是 n,m,qn,m,qn,m,q

接下来mmm行中，每行包含2个正整数 x,yx,yx,y 表示 uncle-lu 一次的E技能 在[x,y][x,y][x,y]区间内种一株草(保证x≤yx≤yx≤y)

第m+2m+2m+2行，包含qqq个正整数 表示每次uncle-lu询问的草地.

Output

输出包含qqq行，对于每次询问，输出询问答案

Sample Input 1

10 5 4
2 4
3 5
4 6
5 7
1 10
4 6 3 5

Sample Output 1

4
3
3
4

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #a,b =map(int,input('输入a,b空格隔开:').split())
     
    
   

    

     

    
    

     

      n,m,q=map(int,input().split(' '))
     
    
   

    

     

    
    

     

      item  = 0
     
    
   

    

     

    
    

     

      a = [item]*(n+2)
     
    
   

    

     

    
    

     

      b = [item]*(n+2)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      for i in range (m):
     
    
   

    

     

    
    

     

          l,r=map(int,input().split(' '))
     
    
   

    

     

    
    

     

          b[l]+=1
     
    
   

    

     

    
    

     

          b[r+1]-=1
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

      for i in range(n):
     
    
   

    

     

    
    

     

          a[i]=a[i-1]+b[i]
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     

      ls=[]
     
    
   

    

     

    
    

     

      ls=map(int,input().split(' '))
     
    
   

    

     

    
    

     

      for x in ls:
     
    
   

    

     

    
    

     
    print(a[x])
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
 
     
    
  
 

  

   

    

     

    
    

     

      #include<bits/stdc++.h>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //直接前缀和，板子都不用换
     
    
   

    

     

    
    

     

      typedef long long ll;
     
    
   

    

     

    
    

     

      const ll N=100000010;
     
    
   

    

     

    
    

     

      ll a[N],b[N];
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          ll n,m,q,l,r,x;
     
    
   

    

     

    
    

     
    scanf("%lld%lld%lld", &n, &m, &q);
     
    
   

    

     

    
    

     
    for (int i = 1; i <= m; i ++ ){
     
    
   

    

     

    
    

     
        scanf("%lld%lld", &l, &r);
     
    
   

    

     

    
    

     

              b[l]++;
     
    
   

    

     

    
    

     

              b[r+1]--;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
     
    
   

    

     

    
    

     
    for (int i = 1; i <= n; i ++ ){
     
    
   

    

     

    
    

     

              a[i]=a[i-1]+b[i];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    for (int i = 0; i < q; i ++ ){
     
    
   

    

     

    
    

     
        scanf("%lld", &x);
     
    
   

    

     

    
    

     
        printf("%lld\n",a[x]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

对于python3和c++，都可以采用前缀和的方法去解释，但是为什么这个题被RE了...还请各位多多指教

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120589964