调
查看原帖
调
722313
Whiking楼主2023/10/3 11:29
#include<bits/stdc++.h>
#define Genshin_Impact_starts ios::sync_with_stdio( false )
#define int long long
using namespace std;
int max( int a, int b) { return a>b?a:b; }
int min( int a, int b) { return a<b?a:b; }
void swap( int &a,int &b) { a=a^b,b=a^b,a=a^b; }
const int N=1e6+100;
int n,tot=1;
int ind[N],tr[N];
struct node {
	int a,b,c,d,id,cnt,sum,col;
} p[N],q[N];
int cmp1(node x,node y) {
	return x.a==y.a?(x.b==y.b?(x.c==y.c?x.d<y.d:x.c<y.c):x.b<y.b):x.a<y.a;
}
int cmp2(node x,node y){
	return x.b==y.b?(x.a==y.a?(x.c==y.c?x.d<y.d:x.c<y.c):x.a<y.a):x.b<y.b;
}
int cmp3(node x,node y){
	return x.c==y.c?(x.a==y.a?(x.b==y.b?x.d<y.d:x.b<y.b):x.a<y.a):x.c<y.c;
}
void add( int x, int v) {
	for (; x<=n; x+=x&-x) tr[x]=max(v,tr[x]);
}
int ask( int x) {
	int res=0; for (; x; x-=x&-x) res=max(res,tr[x]);
	return res;
}
void Starrail( int l, int r) {
	if (l==r) return ;
	int mid=l+r>>1;
	Starrail(l,mid);
	vector<node>las;
	for ( int i=l; i<=r; i++) las.push_back(q[i]);
	sort(q+l,q+mid+1,cmp3);
	sort(q+mid+1,q+r+1,cmp3);
	int j=l;
	for ( int i=mid+1; i<=r; i++) {
		while (j<=mid&&q[j].c<=q[i].c) {if (!q[j].col) add(q[j].d,q[j].sum);j++;}
		if (q[i].col) q[i].sum=max(ask(q[i].d)+q[i].cnt,q[i].sum);
	}for(int i=l;i<=mid;i++)for(int j=q[i].d;j<=n;j+=j&-j)tr[j]=0; 
	for ( int i=0; i<las.size(); i++) q[i+l]=las[i];
	Starrail(mid+1,r);
}
void Genshin( int l, int r)  {
	if (l==r) return ;
	int mid=l+r>>1;
	Genshin(l,mid);
	vector<node>las;
	for ( int i=l; i<=r; i++) las.push_back(q[i]);
	for ( int i=l; i<=mid; i++) q[i].col=0;
	for ( int i=mid+1; i<=r; i++) q[i].col=1;
	sort(q+l,q+r+1,cmp2);
	Starrail(l,r);
	for ( int i=0; i<las.size(); i++) q[i+l]=las[i];
	Genshin(mid+1,r);
}
signed main() {
    Genshin_Impact_starts;
    cin.tie(0),cout.tie(0);
	cin>>n;
	for ( int i=1; i<=n; i++) {
		cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d;
		ind[i]=p[i].d;
	}
	sort(ind+1,ind+n+1);
	int len=unique(ind+1,ind+n+1)-ind-1;
	for ( int i=1; i<=n; i++) p[i].d=lower_bound(ind+1,ind+1+len,p[i].d)-ind;
	sort(p+1,p+n+1,cmp1);
	q[tot]=p[tot];
	q[tot].cnt=1;
	for ( int i=2; i<=n; i++) {
		if (p[i].a==p[i-1].a&&p[i].b==p[i-1].b&&p[i].c==p[i-1].c&&p[i].d==p[i-1].d) q[tot].cnt++;
		else q[++tot]=p[i],q[tot].cnt=1;
	}
	for ( int i=1; i<=tot; i++) q[i].id=i,q[i].sum=q[i].cnt;
	Genshin(1,tot);
	int ans=0;
	for ( int i=1; i<=tot; i++) ans=max(ans,q[i].sum);
	cout<<ans;
}	
/*
4
1 2 3 4
2 4 5 3
2 45 4 43
3 434 23 324
*/
2023/10/3 11:29
加载中...