求好的hack
查看原帖
求好的hack
1394167
li00000000a楼主2025/6/19 18:47
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+10;
int n,dp[N];
pii qj[N];
bool cmp(pii x,pii y){
	return x.second<y.second;
}
int cnt,root;
struct Node{
	int val,ls,rs;
}tr[N*4];
/*void add_a_tag(int k,int l,int r,int newval){
	tr[k].val += 
}*/
void update(int k){
	tr[k].val = max(tr[tr[k].ls].val, tr[tr[k].rs].val);
}
void build(int &k,int l,int r){
	k = ++cnt;
	if(l == r){
		tr[k].val = 0;
		return;
	}
	int mid = (l+r)>>1;
	build(tr[k].ls, l, mid);
	build(tr[k].rs, mid+1, r);
	update(k);
}
void modify(int k,int pl,int l,int r,int newval){
	if(l == r){
		tr[k].val = newval;
		return;
	}
	int mid = (l+r)>>1;
	if(pl <= mid) modify(tr[k].ls, pl, l, mid, newval);
	else modify(tr[k].rs, pl, mid+1, r, newval);
	update(k);
}
int query(int k,int ql,int qr,int l,int r){
	if(ql<=l && r<=qr) return tr[k].val;
	if(r<ql || qr<l) return 0;
	int mid = (l+r)>>1;
	return max(query(tr[k].ls, ql, qr, l, mid),query(tr[k].rs, ql, qr, mid+1, r));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>qj[i].first>>qj[i].second;
		if(qj[i].first > qj[i].second) swap(qj[i].first,qj[i].second);
	} 
	sort(qj+1,qj+n+1,cmp);
	build(root,1,2*n);
	//int jj = 1;
	for(int i=1;i<=n;i++){
		dp[i] = query(root, qj[i].first, qj[i].second, 1, 2*n) + 1;
		modify(root, qj[i].first, 1, 2*n, dp[i]);
	}
	//for(int i=1;i<=n;i++){
	//	printf("[ %d , %d ] : %d\n",qj[i].first, qj[i].second, dp[i]);
	//}
	/*for(int i=1;i<=n;i++){
		modify(root, i, 1, n, dp[i]);
	}*/
	int ans = 0;
	for(int i=1;i<=n;i++){
		int tmp = query(root, qj[i].second+1, 2*n, 1, 2*n);
		if(tmp<0) tmp = 0;
		ans = max(ans, dp[i]+tmp);
	}
	cout<<ans<<"\n";
	return 0;
}
2025/6/19 18:47
加载中...