刚入门四维偏序的小白求助
查看原帖
刚入门四维偏序的小白求助
102709
zjy1412楼主2020/11/24 16:23

自己码了一下35分,对着题解修修补补,还是35分,只能举起小白旗求助了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
#include<vector>
#include<cstdlib>
using namespace std;
#define int long long
#define R register
#define debug printf("zjy ")
#define ld double
#define pii pair<int,int> 
#define pil pair<int,double> 
#define lp (p<<1)
#define rp (p<<1|1)
int read(){
	int a=0,b=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')b=-1;c=getchar();}
	while(isdigit(c)){a=a*10+c-'0';c=getchar();}
	return a*b;
}
void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x<=9){putchar(x+'0');return;}
	write(x/10);putchar(x%10+'0');
}
void writesp(int x){
	write(x);putchar(' ');
}
void writeln(int x){
	write(x);putchar('\n');
}
const int N=5e4+50,inf=4e18;
int n,lsh[N],h;
struct AC{
	int a,b,c,d,val,ans,id,ok;
	void init(){
		a=read();b=read();c=read();
		d=lsh[++h]=read();val=read();
	}
//	bool operator ==(const AC x)const{
//		return (a==x.a)&&(b==x.b)&&(c==x.c)&&(d==x.d);
//	}
}e[N],tmp[N];
bool cmpa(AC x,AC y){
	return x.a<y.a;
}
bool cmpb(AC x,AC y){
	return x.b<y.b;
}
bool cmpc(AC x,AC y){
	return x.c<y.c;
}
namespace bit{
	int s[N];
	#define lowbit(x) (x&-x)
	void add(int x,int z){
		for(;x<=h;x+=lowbit(x))s[x]=max(s[x],z);
	}
	int query(int x){
		int val=-inf;
		for(;x;x-=lowbit(x))val=max(val,s[x]);
		return val;
	}
	void clear(int x){
		for(;x<=h;x+=lowbit(x))s[x]=0;
	}
}
int pos1[N],pos2[N];
void cdq2(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq2(l,mid);
	sort(e+l,e+mid+1,cmpc);
	sort(e+mid+1,e+r+1,cmpc);
	int j=l;
	for(R int i=mid+1;i<=r;i++){
		while(j<=mid&&e[j].c<=e[i].c){
			if(e[j].ok)bit::add(e[j].d,e[j].ans);
			j++;
		}
		if(!e[i].ok)e[i].ans=max(e[i].ans,bit::query(e[i].d)+e[i].val);
	}
	for(R int i=l;i<j;i++)if(e[i].ok)bit::clear(e[i].d);
	for(R int i=l;i<=r;i++)tmp[pos2[e[i].id]]=e[i];
	for(R int i=l;i<=r;i++)e[i]=tmp[i];
	cdq2(mid+1,r);
}
void cdq1(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq1(l,mid);
	for(R int i=l;i<=mid;i++)e[i].ok=1;
	for(R int i=mid+1;i<=r;i++)e[i].ok=0;
	sort(e+l+1,e+r+1,cmpb);
	for(R int i=l;i<=r;i++)pos2[e[i].id]=i;
	cdq2(l,r);
	for(R int i=l;i<=r;i++)tmp[pos1[e[i].id]]=e[i];
	for(R int i=l;i<=r;i++)e[i]=tmp[i];
	cdq1(mid+1,r);
}
signed main(){
	n=read();
	for(R int i=1;i<=n;i++){
		e[i].init();
	}
	sort(lsh+1,lsh+h+1);
	h=unique(lsh+1,lsh+h+1)-lsh-1;
	for(R int i=1;i<=n;i++){
		e[i].d=lower_bound(lsh+1,lsh+h+1,e[i].d)-lsh;
	}
	sort(e+1,e+n+1,cmpa);
	for(R int i=1;i<=n;i++)pos1[i]=e[i].id=i,e[i].ans=e[i].val;
	cdq1(1,n);
	int ans=-inf;
	for(R int i=1;i<=n;i++){
		ans=max(ans,e[i].ans);
	}
	writeln(ans);
	return 0;
}
2020/11/24 16:23
加载中...