A10 差分 二维差分

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10; 
int d[N],a[N],s[N];
int main()
{
    int n,m;scanf("%d%d", &n, &m);
    memset(d,0, sizeof(d));
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        d[x]++;
        d[y+1]--; //此时的d[i]表示从第i个小朋友开始，往后每个小朋友加d[i]糖果
    }
    a[0]=0;for(int i=1;i<=n;i++)a[i]=a[i-1]+d[i];//此时的a[i]表示从第i个小朋友最后手里的糖果数
    s[0]=0;for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];//s[i]表示第1个小朋友至第i个小朋友糖果数的总数
    int Q;scanf("%d", &Q);
    for(int i=1,x,y;i<=Q;i++)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n",s[y]-s[x-1]);
    }
    return 0;
}