1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10; struct node{ int x,y,val; bool operator <(const node& t)const{ return x < t.x; } }a[maxn]; int T,n,tot; int bit[maxn],dp[maxn]; int lowbit(int x){ return x&-x; } void update(int x,int val){ for(int i=x;i<=tot;i+=lowbit(i)) bit[i] = max(bit[i],val); } int query(int x){ int s = 0; for(int i=x;i;i-=lowbit(i)){ s = max(s,bit[i]); } return s; } int main(){ #ifdef LOCAL freopen("2.in","r",stdin); #endif scanf("%d",&T); while(T--){ vector<int> v; memset(bit,0,sizeof(bit)); scanf("%d",&n); rep(i,0,n){ int x,y,v;scanf("%d%d%d",&x,&y,&v); a[i].x = x;a[i].y = y;a[i].val = v; } rep(i,0,n) v.push_back(a[i].y); sort(v.begin(),v.end()); sort(a,a+n); v.erase(unique(v.begin(),v.end()),v.end()); tot = v.size(); rep(i,0,n) a[i].y = lower_bound(v.begin(),v.end(),a[i].y) - v.begin() + 1; rep(i,0,n) dp[i] = a[i].val; int ans = 0;int pos = 0; rep(i,0,n){ while(pos < i && a[pos].x < a[i].x){ update(a[pos].y,dp[pos]); pos ++; } dp[i] = query(a[i].y-1) + a[i].val; ans = max(ans,dp[i]); } printf("%d\n",ans); } return 0; }
|