学步园

再一次被智商题碾压，正解用的trick很巧妙，因为区间有可能是交叉重叠的，所以在stone[l]处+d，stone[r+1]处-d，从左到右扫描，如果某一点还停留在区间内，则会类加上stone[l],如果在区间外，扫描就穿过了区间，+d,-d没有影响。所以从头到尾扫描得出的就是经过某一点时减少的value。然后从该点往后遍历就得到了x to N减少的value，但是因为要求出所有点，从后往前遍历就是O(N)。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
using namespace std;
//hdu 4970

const int maxn=100010;
long long  stone[maxn];
long long  sum[maxn];
long long H[maxn];
int X[maxn];
int K;
int N;
int M;
int main()
{
    freopen("input.txt","r",stdin);
   //  freopen("data.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    while(true)
    {
        scanf("%d",&N);
        if(N==0) break;
        scanf("%d",&M);
        memset(stone,0,sizeof(stone));
        memset(sum,0,sizeof(sum));
        int l,r=0;
        long long d=0;
        int ans=0;
        for(int i=0;i<M;i++)
        {
            scanf("%d %d %I64d",&l,&r,&d);
            stone[l]+=d;//注意不能直接赋值，可能有区间重合，并且stone[i]最大值为10W*1000,所以要用long long 存
            stone[r+1]-=d;
        }
        scanf("%d",&K);
        for(int i=0;i<K;i++)
        {
            scanf("%I64d %d",&H[i],&X[i]);
        }
        sum[0]=stone[0];
        for(int i=1;i<N;i++)
        {
            sum[i]+=sum[i-1]+stone[i];
        }
        for(int i=N-1;i>=0;i--)
        {
            sum[i]+=sum[i+1];
        }
        for(int i=0;i<K;i++)
        {
            if(H[i]>sum[X[i]]) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}