codevs3037 라인 덮어쓰기 5 이산화 DP

제목.

codevs3037 라인 덮어쓰기 5

문제풀이

어떤 사람들은 왜 BIT = 을 쓰는지 모르겠다.이러면 애들 망가지잖아.그런데 네가 억지로 로그를 넣으면 느릴 거야. 야, 하물며 이 문제의 로그는 대략 20이야.사실 저도 잘 못 써요.
dp[i]는 이산화 후의 단점 i까지 최대 가치를 나타낸다.그리고 선분을 오른쪽 단점에 따라 정렬한 다음에 방정식을 옮기는 것은 이렇다
dp[i]=max( dp[ i - 1 ] , dp[ l [ k ] ] + val[ k ])
l 은 왼쪽 단점 val 은 가치 이것 은 누드 가방 이 아닌가???가방을 쓸 때 최대치로 BIT를 쓴다고요?비판할 뜻은 없는데각 라인은 오른쪽 끝점에서 한 번만 열거되기 때문에 dp의 시간 복잡도는 O(이산화 백엔드 포인트 + 라인 수)이다.그래서 이 문제의 주요 복잡도는 이산화에 있다.

코드

//QWsin
#include
#include
#include
#include
using namespace std;
const int maxn=1000000+10;
typedef long long ll;
inline ll read()
{
    ll ret=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}

ll x[maxn*2],dp[maxn*2];
struct Line{
    ll l,r,val;
    bool operator < (const Line &rhs)const{
        return rinline void input(){l=read();r=read();val=read();}
}l[maxn];

int main()
{
    int n=read();
    for(int i=1;i<=n;i++) l[i].input(),x[i*2-1]=l[i].l,x[i*2]=l[i].r;
    sort(x+1,x+2*n+1);
    int m=unique(x+1,x+2*n+1)-x-1;
    for(int i=1;i<=n;i++) 
        l[i].l=lower_bound(x+1,x+m+1,l[i].l)-x,
        l[i].r=lower_bound(x+1,x+m+1,l[i].r)-x;
    sort(l+1,l+n+1);

    int p=0;
    ll ans=0;
    for(int i=1;i<=m;i++)
    {
        dp[i]=dp[i-1];
        while(p+1<=n&&l[p+1].r==i) 
        {
            p++;
            dp[i]=max(dp[i],dp[l[p].l]+l[p].val);
            ans=max(ans,dp[i]);
        }
    }

    cout<return 0;
}