bzoj2131: 免费的馅饼（树状数组）

Description

Input

第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。　　接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。

Output

一个数，表示游戏者获得的最大总得分。

Sample Input

3 4
1 2 3
5 2 3
6 3 4
1 1 5

Sample Output

12
【数据规模】
对于100%的数据，1<=w,t[i]<=10^8,1<=n<=100000。

 

首先不难得到转移方程$dp[i]=max{dp[j]}+val[i](|p_i-p_j|leq 2t_i-2t_j)$

考虑怎么转换限制条件，$p_i-p_jleq 2t_i-2t_j$且$p_j-p_ileq 2t_i-2t_j$，则有$2t_i-p_igeq 2t_j-p_j$且$2t_i+p_igeq 2t_j+p_j$

那么就是一个二维偏序问题了，先排序消除第一维的影响，然后用树状数组维护第二维就好了

//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
ll read(){
    #define num ch-'0'
    char ch;bool flag=0;ll res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
const int N=5e5+5;
int n,w;ll c[N];
inline void add(int x,ll y){
    for(;x<=n+1;x+=x&-x) cmax(c[x],y);
}
ll query(int x){
    ll res=0;for(;x;x-=x&-x) cmax(res,c[x]);return res;
}
struct node{
    int x,y;ll v;
    inline bool operator <(const node &b)const
    {return x==b.x?y<b.y:x<b.x;}
}a[N];int b[N];
int main(){
//    freopen("testdata.in","r",stdin);
    w=read(),n=read();
    for(int i=1;i<=n;++i){
        int t=read(),p=read();a[i].v=read();
        a[i].x=2*t+p,a[i].y=2*t-p,b[i]=a[i].y;
    }
    sort(a+1,a+1+n),sort(b+1,b+n+1);
    for(int i=1;i<=n;++i){
        ll res=0;int pos=lower_bound(b+1,b+1+n,a[i].y)-b;
        res=query(pos)+a[i].v,add(pos,res);
    }
    printf("%lld
",query(n+1));
    return 0;
}