洛谷 U122679 题解

原题链接

题解：

把点按x排序，f[i]表示前i个点（必须包含i）的最大团点数f[i]=max(f[j])+1（xi-xj>=wi+wj => xi-wi>=xj+wj）把xi+wi离散化后线段树优化（这里用了zkw线段树常数比较小）

#include
#include
#include
#include
using namespace std;
const int N=200000+10;
inline void getint(int&num){
    char c;int flag=1;num=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
    while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
    num*=flag;
}
int n,siz,tep,M;
long long Max[N<<3];
int x[N],w[N],tmp[N],id[N],f[N];
void insert(int pos,int val){
    long long a;
    val-=f[pos];
    Max[pos+M]+=val;
    for(pos=pos+M;pos;pos>>=1){
        a=max(Max[pos<<1],Max[pos<<1|1]);
        Max[pos<<1]-=a,Max[pos<<1|1]-=a,Max[pos]+=a;
    }
}
long long getmax(int s,int t){
    if(t>=1;
        return res;
    }
    for(s=s+M,t=t+M;s^t^1;s>>=1,t>>=1){
        L+=Max[s],R+=Max[t];
        if(~s&1)    L=max(L,Max[s^1]);
        if(t&1) R=max(R,Max[t^1]);
    }
    res=max(L+Max[s],R+Max[t]);
    while(s)    res+=Max[s>>=1];
    return res;
}
bool cmp(int a,int b){
    return x[a]tep+1) continue ;
        insert(p,tep+1);
        f[p]=tep+1;
    }
    cout<