3 차원 편향 CDQ

이런 문제 보 겠 습 니 다.
(bzoj 낯 선 백합)
설명: n 개의 점 (x, y, z) 을 제시 합 니 다. 가장 긴 상승 서브 시퀀스, 즉 선택 시퀀스 중의 i xi < = xj, yi < = yj, zi < = zj 를 찾 으 십시오.출력 최 장 상승 서브 시퀀스 의 길이 와 방안 수.입력: 첫 번 째 줄 에는 정수 n 다음 n 줄 이 포함 되 어 있 습 니 다. 각 줄 에는 3 개의 정수 xi, yi, zi 출력: 출력 길이 와 방안 수 (방안 수 대 2 ^ 30 취 mod) 입 출력 사례 가 있 습 니 다. cdq. in cdq. out 3 2 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 2 3 3 3 2 데이터 범위: x, y, z < 100000000 대 20% 데이터 n < = 1000 대 100% 데이터 n < = 100000
이것 이 바로 전형 적 인 3 차원 편차 이다.
3 차원 편 서 는 점 을 정렬 한 후에 구 할 수 있다.
먼저 2 차원 편차: (x, y)
만약 우리 가 x 에 대해 정렬 을 한다 면, y 를 구 하 는 lis 로 바 꿀 것 이다.
마찬가지 로 우리 도 약간의 전환 이 필요 하 다.
cdq 에 따라 기본 사상, 1 차원 정렬, 2 차원 분할, 3 차원 트 리 배열 (데이터 구조)
-----------------------------------------------------------------------------------------------
다음은 이 문 제 를 예 로 들 어 cdq 분 치 사상 에 대하 여 말씀 드 리 겠 습 니 다.
만약 에 우리 가 1 차원 좌표 에 따라 순 서 를 배열 했다 고 가정 하면 우 리 는 x 배열 의 점 대 (y, z) 에서 2 차원 편 서 를 찾 아야 한다.
이전에 순서 (x) 를 배열 하 였 기 때문에 직접 정렬 하 는 것 은 문제 가 있 습 니 다. 여기에 트 리 유지 보 수 를 쓸 수 있 습 니 다.
나무 커버 나무의 사이즈 가 좀 크 고 쓰기 가 쉽 지 않 아서 말 하지 않 겠 습 니 다.
실제 적 인 것 을 이야기 하 다.
우 리 는 이미 x 라 는 1 차원 에 대해 순 서 를 정 했다. 그러면 우 리 는 [l, r] 의 점 대 를 두 구간 [l, mid] 과 [mid + 1, r] 로 나 누 었 다.
그 다음 에 순서대로 호출 하고 [l, mid] 의 정 보 를 처리 한 다음 에 [l, mid] 가 [mid + 1, r] 에 미 친 영향 을 처리 하고 마지막 으로 [mid + 1, r] 의 정 보 를 처리 합 니 다.
(왜 그 랬 을 까? 이 문 제 는 3 차원 lis 를 구 하 는 것 이기 때문에 왼쪽 구간 은 오른쪽 에 영향 을 줄 수 있다.)
아까 의 분 치 를 계속 하 세 요. 만약 에 우리 가 두 구간 의 정 보 를 얻 었 다 면 3 차원 에 대한 정 보 를 유지 할 수 있 습 니 다.
모 르 시 겠 지만 구체 적 인 것 을 말씀 드 리 겠 습 니 다.
(다음은 [l, mid] 가 [mid + 1, r] 에 미 친 영향 계산)
우 리 는 2 분 의 구간 을 각각 y 로 정렬 합 니 다. (1 차원 의 앞줄 이 순서 가 있 기 때문에 [mid + 1, r] 의 모든 x > = [l, mid] 의 x. 왼쪽 구간 이 오른쪽 구간 에 미 치 는 영향 을 고려 하기 때문에 구간 내부 정 보 를 고려 하지 않 아 도 됩 니 다)
2 위도 질서 가 있 었 다.
그 다음 에 [mid + 1, r] 각 요 소 를 매 거 하고 왼쪽 구간 의 지침 i 를 유지 합 니 다. 현재 매 거 진 요소 j 의 y 가 있 으 면 왼쪽 구간 의 모든 i. y < = j. y 의 정 보 를 트 리 배열 에 업데이트 합 니 다 (우 리 는 y 의 단조 성 을 보장 하기 때문에 복잡 도 는 대체적으로 구간 이 길 고 새로운 단일 시간 입 니 다)
나무 모양 의 배열 은 무엇 에 쓰 입 니까?우 리 는 오른쪽 구간 의 j 를 매 거 하여 왼쪽 구간 의 모든 i. y < = j. y (첫 번 째 정렬 은 i. x < = j. x) 의 z 가 트 리 배열 에 대응 하 는 위치 에 있 는 dp 값 을 max (dp [i]) 로 업데이트 합 니 다.           그래서 트 리 배열 은 3 차원 dp 값 을 유지 하 는 데 사 용 됩 니 다.
매 거 진 j 에 대해 i. y < = j. y 의 i 정 보 를 모두 업데이트 한 후 dp [j] = query ([1, j. z]) (이 구간 의 최대 dp 값) + 1;
그리고 모든 dp 값 을 max 로 구하 면 답 을 얻 을 수 있 습 니 다.
그럼 어떻게 방안 을 구 합 니까?
나 도 사실 매우 막막 하지만 각종 자 료 를 참고 한 후에 하나의 배열 저장 방안 만 유지 하면 된다 는 것 을 알 게 되 었 다.
dp 값 을 업데이트 할 때 if (dp [j] getmax (1, j. z). cnt;
                              if(dp[j]==getmax(1,j.z).dp)cnt[j]+=getmax(1,j.z).cnt;
됐어!
잘 모 르 는 것 이 있 으 면 다시 한 번 자세히 생각해 보 세 요!
AC 코드:

#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
const LL M=1<<30;
using namespace std;
double st,ft;
const int maxn=100000+20;
struct xnode
{
	int x,y,z,id;
}q[maxn],tl[maxn],tr[maxn];
int dp[maxn];
LL c[maxn];
int n;
bool cmpx(xnode a,xnode b)
{
	if(a.x!=b.x)return a.x>1;
	int t1,t2;
	t1=t2=0;
	for(int i=l;i<=mid;i++)tl[++t1]=q[i];
	for(int i=mid+1;i<=r;i++)tr[++t2]=q[i];
	sort(tl+1,tl+t1+1,cmpy);
	sort(tr+1,tr+t2+1,cmpy);
	for(int i=1,j=1;j<=t2;j++)
	{
		while(tl[i].y<=tr[j].y&&i<=t1)
		{
			updata(tl[i].z,dp[tl[i].id],c[tl[i].id]);
			i++;
		}
		Ans sum=query(tr[j].z);
		sum.dp++;
		if(dp[tr[j].id]>1;
	cal(l,mid);
	work(l,r);
	cal(mid+1,r);
}
int main()
{
	freopen("cdq.in","r",stdin);
	freopen("cdq.out","w",stdout);
	cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		q[i].id=i;
		dp[i]=1;
		c[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
		det[++cnt]=q[i].z;
	}
	sort(det+1,det+cnt+1);
	m=unique(det+1,det+cnt+1)-det-1;
	for(int i=1;i<=n;i++)q[i].z=find(q[i].z);	
	sort(q+1,q+n+1,cmpx);
	cal(1,n);
	int ans=0;
	LL sum=0;
	for(int i=1;i<=n;i++)
	{
		if(dp[i]>ans)
		{
			ans=dp[i];
			sum=c[i]%M;
		}
		else if(dp[i]==ans)
		{
			sum+=c[i];
			sum%=M;
		}
	}
	printf("%d %I64d
",ans,sum);
	return 0;
}