学步园

事实证明线段树是可以过的。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 1e5+10;

long long grid[maxn<<2];
long long cov[maxn<<2];
long long newleaf[maxn];
int n, m;

void pushdown(int l, int r, int rt)
{
    if(cov[rt])
    {
        int m = (l + r) >> 1;
        cov[rt<<1] += cov[rt];
        cov[rt<<1|1] += cov[rt];
        grid[rt<<1] += (m - l + 1) * cov[rt];
        grid[rt<<1|1] += (r - m) * cov[rt];
        cov[rt] = 0;
    }
}

void pushup(int rt)
{
    grid[rt] = grid[rt<<1] + grid[rt<<1|1];
}

void update(int L, int R, long long d, int l, int r, int rt)
{
    if(L <= l && R >= r)
    {
        grid[rt] += (r - l + 1) * d;
        cov[rt] += d;
        return ;
    }
    pushdown(l, r, rt);
    int m = (l + r) >> 1;
    if(L <= m) update(L, R, d, l, m, rt<<1);
    if(R > m) update(L, R, d, m+1, r, rt<<1|1);
    pushup(rt);
}

void query(int l, int r, int rt)
{
    if(l == r)
    {
        newleaf[l] = grid[rt];
        return ;
    }
    pushdown(l, r, rt);
    int m = (l + r) >> 1;
    query(l, m, rt<<1);
    query(m+1, r, rt<<1|1);
}

template <class T>

char read_int(T *x)
{
    (*x) = 0;
    char ch = getchar();
    while(ch < 48 || ch > 57)
    {
        ch = getchar();
    }
    while(ch > 47 && ch < 58)
    {
        (*x) *= 10;
        (*x) += ch - '0';
        ch = getchar();
    } 
    return ch;
}

int main()
{
    //freopen("1011.in", "r", stdin);
    while(read_int(&n) && n)
    {
        memset(grid, 0, sizeof(grid));
        memset(cov, 0, sizeof(cov));
        memset(newleaf, 0, sizeof(newleaf));
        read_int(&m);
        int l, r, k, x;
        long long d, h;
        for(int i = 0; i < m; i++)
        {
            read_int(&l);
            read_int(&r);
            read_int(&d);
            update(l, r, d, 1, n, 1);
        }
        query(1, n, 1);
        for(int i = n-1; i > 0; i--)
            newleaf[i] += newleaf[i+1];
        read_int(&k);
        int sum = 0;
        for(int i = 0; i < k; i++)
        {
            read_int(&h);
            read_int(&x);
            if(h > newleaf[x])
                sum++;
        }
        printf("%d\n", sum);
    }

    return 0;
}