牛客周赛11TG B弹钢琴

链接：https://ac.nowcoder.com/acm/contest/941/B
来源：牛客网

题目描述

春希想听和纱弹钢琴！
为了阻止异变的发生，Pi将钢琴魔改了
钢琴上有 N 个键，每个键有音高、音色、春希度三种属性
和纱需要依次敲击若干个键，这些键的春希度之和越大，春希就越满意
然而由于Pi的魔改，一个键被敲下后，该键和所有音高或音色小于它的键都会坏掉（坏掉即不能再被敲击）
Pi想知道在这种情况下，和纱能弹琴的最大春希度之和

输入描述:

第一行一个数，为按键个数 N
接下来 N 行每行三个数，分别表示第 i 个键的音高、音色、春希度

输出描述:

一行一个数，为最大的春希度和

示例1

输入

复制

输出

复制

备注:

20%

N≤10N\leq 10N≤10

50%

N≤1000N\leq 1000N≤1000

90%  $N≤105N\leq 10^5N≤105100% N≤106N\leq 10^6N≤106, 输入中所有数均为正整数且 ≤108\leq 10^8≤108emm这题正解树状数组？？？（但是我永远喜欢线段树并且永远讨厌离散化所以就用动态开点线段树写了qvq最简单的动态开点线段树单点修改区间查值操作改到最后还是90pts emmm线段树的常数还是大了而且1000000乘上logINF也不太遭得住注意的是那个根一开始是取0的emmmm$

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define int long long
using namespace std;

const int maxn=1000005;
const int INF=2147483647;

struct node{
    int w;
    signed son[2];
}tr[maxn<<3];

struct qvq{
    int x,y,w;
}a[maxn];
inline int max(int x,int y) {
    return x>y?x:y;
}

inline bool cmp(qvq x,qvq y) {
    if (x.x==y.x) return x.y<y.y;
    return x.x<y.x;
}

int cnt;
inline void add(signed &now,int l,int r,int loc,int w) {
    if (!now) now=++cnt;
    tr[now].w=max(w,tr[now].w);
    if (l==r) return;
    int mid=l+r>>1;
    if (loc<=mid) add(tr[now].son[0],l,mid,loc,w);
    if (mid+1<=loc) add(tr[now].son[1],mid+1,r,loc,w);
}

inline int query(signed now,int l,int r,int x,int y) {
    if (!now) return 0;
    if (x<=l && r<=y) return tr[now].w;
    int ans=0,mid=l+r>>1;
    if (x<=mid) ans=max(ans,query(tr[now].son[0],l,mid,x,y));
    if (mid+1<=y) ans=max(ans,query(tr[now].son[1],mid+1,r,x,y));
    return ans;
}

signed main(){
    int n;
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) 
        scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for (int i=1;i<=n;i++) {
        signed rt=0;
        if (i>1) rt=1;
        int val=query(rt,1,INF,1,a[i].y)+a[i].w;
        ans=max(ans,val);
        add(rt,1,INF,a[i].y,val);
    }
    printf("%lld",ans);
}