呐，我们可以转化一下题面：
把某个正整数看作位置，选择这个正整数 即 此位置取 (1) ，不选表示此位置取 (0)
然后就得到了一个 (01) 串。
所以我们可以考虑维护一个前缀和，限制条件(l-r)至少有 (k) 个数即：
[sum_r - sum_[l-1] >= k
]
但是实际上还有一个隐藏的限制条件：
[sum_{i+1} - sum_i>=0
]
且：
[sum_{i} - sum_{i+1}>=-1
]
所以都要连边，然后跑最长路 (QwQ)
#include<bits/stdc++.h>
using namespace std;
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int N = 5e5 + 5;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
int n, maxn, dis[N], S, book[N], head[N], cnt, minn, vis[N];
struct E {
int to, next, w;
} e[N * 2];
void init() {
memset( head, 0, sizeof(head) ), cnt = 0;
}
void add( int x, int y, int z ) {
e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt;
}
void input() {
n = read(); int x, y, z; minn = N;
rep( i, 1, n ) {
x = read(), y = read(), z = read();
if( x > y ) swap( x, y );
add( x - 1, y, z );
maxn = max( maxn, y );
}
rep( i, 0, maxn ) add( i, i + 1, 0 ), add( i + 1, i, -1 );
}
queue< int> q;
void spfa( int x ) {
while( !q.empty() ) q.pop();
memset( dis, -63, sizeof(dis) ), memset( vis, 0, sizeof(vis) );
memset( book, 0, sizeof(book) );
dis[x] = 0, q.push(x);
while( !q.empty() ) {
int u = q.front(); q.pop();
book[u] = 0, vis[u] = 1;
Next( i, u ) {
int v = e[i].to;
if( dis[v] < dis[u] + e[i].w ) {
if( !book[v] ) q.push(v), book[v] = 1;
dis[v] = dis[u] + e[i].w;
}
}
}
}
signed main()
{
int T = read();
while( T-- ) {
init(), input();
spfa(S), printf("%d
", dis[maxn]);
if(T) puts("");
}
return 0;
}