福州大学算法作业题 - 加法运算

★实验任务 

小学一年级的期末考试上，老师出了这样一道题：给出一排数字，选择其中 位置连续的若干个数字，计算它们的和，要求这些数字的和满足大于等于 a，小 于等于 b 的条件。快速统计出子序列数量的同学，可以得到满分！ 
小明回家之后，请教了他正在读研究生的表哥 mcginn，mcginn 大手一挥， 写下了一段代码，快速高效地解决了这个问题，从此小明立志成为一名码农！ 

★数据输入

输入一个 n 表示数字个数，以及 a 和 b(|a|,|b| <= 100000) 输入一个数组 nums[]，(|nums[i]| <= 100000)表示数字

★数据输出

输出一个数字表示满足条件的连续子序列有几种 

注意：统计结果不包括空序列 

★数据范围

80%的得分点，n<=1000 其余 20%的得分点，n<=100000 

代码1：

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
#include <math.h>  
#include <stdlib.h>  
#include <vector>  
#include <queue>  
  
using namespace std;  
  
class search {  
public:  
    int mergesort(vector<long>& sum, int left, int right, int lo, int hi)  
    {  
        if(hi-lo <= 1) return 0;  
        int mid = (lo+hi)/2, m = mid, n = mid, count =0;  
        count = mergesort(sum,left,right,lo,mid) + mergesort(sum,left,right,mid,hi);  
        for(int i =lo; i< mid; i++)  
        {  
            while(m < hi && sum[m] - sum[i] < left) m++;  
            while(n < hi && sum[n] - sum[i] <= right) n++;  
            count += n - m;  
        }  
        inplace_merge(sum.begin()+lo, sum.begin()+mid, sum.begin()+hi);  
        return count;  
    }  
   
    int countrangesum(vector<int>& nums, int left, int right) {  
        int len = nums.size();  
        vector<long> sum(len + 1, 0);  
        for(int i =0; i< len; i++) sum[i+1] = sum[i]+nums[i];  
        return mergesort(sum, left, right, 0, len+1);  
    }  
}s;  
  
  
  
int main(){  
    int n,a,b,i;  
    scanf("%d %d %d",&n,&a,&b);  
    vector<int> nums(n,0);  
    for(i=0;i<n;i++){  
        scanf("%d",&nums[i]);  
    }   
    int count=s.countrangesum(nums,a,b);  
    printf("%d",count);  
    return 0;  
}