DongDong跳一跳

题目连接：https://ac.nowcoder.com/acm/contest/904/C

　　题意很好理解，思路想歪了，本来一道很简单的题，写了好久没写出来。

　　思路就是找每一个高度最大值的时候就是找“  当前的小鱼干数量+（高度-允许差值到高度+允许差值中鱼干的最大数量）  ”，复杂度为m*n*2，但我感觉复杂度爆炸了，所以我用线段树维护区间最大值，复杂度为n*logn

　　AC代码：（感觉线段树会爆内存，可能牛客的评测姬比较友好吧）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+510;
typedef long long ll;
typedef struct W_W{
    int left;
    int right;
    ll weight;
}miao;
ll maxx(ll a,ll b){
    if(a>b) return a;
    return b;
}
miao x[maxn*4];
void build(int l,int r,int dang){
    if(l==r){
        x[dang].left=l;
        x[dang].right=r;
        x[dang].weight=0;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,dang*2);
    build(mid+1,r,dang*2+1);
    x[dang].left=l;
    x[dang].right=r;
    x[dang].weight=0;
}
ll query(int l,int r,int dang){
    //printf("%d %d %d
",dang,x[dang].left,x[dang].right);
    if(l<=x[dang].left&&r>=x[dang].right){
        return x[dang].weight;
    }
    if(l>x[dang].right){
        return 0;
    }
    if(r<x[dang].left){
        return 0;
    }
    //int mid=(l+r)/2;
    ll a=query(l,r,dang*2);
    ll b=query(l,r,dang*2+1);
    return maxx(a,b);
}
void update(int a,ll b,int dang){
    if(x[dang].left>a) return;
    if(x[dang].right<a) return;
    if(x[dang].left==a&&x[dang].right==a){
        x[dang].weight=b;
        return;
    }
    update(a,b,dang*2);
    update(a,b,dang*2+1);
    x[dang].weight=maxx(x[dang*2].weight,x[dang*2+1].weight);
}
int main()
{

    int m,n;
    scanf("%d %d",&m,&n);
    build(0,1000500,1);
    //printf("1111111111
");
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        ll sum=query(max(0,a-n),min(a+n,1000010),1);
        //printf("111111
");
        update(a,sum+b,1);
    }
    printf("%lld
",query(0,1000010,1));
    return 0;
}