bzoj 3289 Mato 의 파일 관리 (모 팀 알고리즘 + 구간 역순 수)

전송 문: bzoj 3289
제목 대의: 구간 역 서수 구하 기.
선행 기술:
1. 나무 모양 배열 로 역순 수 를 구한다.그 사고방식 은 트 리 배열 의 각 노드 에 대응 하 는 구간 이 있 고 각 노드 는 표 시 된 아래 표 시 된 구간 안의 숫자 (또는 노드 아래 표 시 된 숫자 보다 작은 숫자) 가 나타 나 는 횟수 를 나타 낸다.i 번 째 숫자 a [i] 를 삽입 할 때 이전에 삽 입 된 것 보다 큰 수 와 역순 수 를 형성 하기 때문에 이 수 를 삽입 하면 발생 하 는 역순 수 는 구간 길이 - 이미 삽 입 된 것 보다 작은 수 입 니 다.이미 삽 입 된 이 수 보다 작은 수, 즉 아래 표 시 된 a [i] 노드 가 표시 하 는 구간 내 수의 개수 입 니 다.
2. 모 팀 알고리즘.가 화성 이 없 는 구간 문 제 를 처리 할 수 있다.이것 은 모형 을 직접 사용 할 수 없다. 왜냐하면 모 팀 알고리즘 은 하나의 사상 이기 때문이다.쉽게 말 하면 오프라인 으로 처리 할 수 있 는 모든 문의 순 서 를 지난번 구간 에서 작은 범위 로 현재 조회 구간 으로 옮 기 는 것 이다.이렇게 하면 많은 중복 계산 을 피 할 수 있 기 때문에 시간 복잡 도 는 매우 낙관적이다.
정렬 할 때 는 일반적으로 블록 (각 크기 는 근호 n) 사상 에 따라 한다 (최소 맨 해 튼 거리 에 따라 할 수도 있다). 구체 적 인 방법 은 구간 에 속 하 는 블록 을 묻 는 것 과 같은 것 에 대해 구간 오른쪽 점 의 오름차 순 으로 배열 하고 구간 왼쪽 점 에 따라 배열 하 는 것 이다.구체 적 인 소 개 는 모 팀 거 신 이 추천 한 글 이다.
그 기본 적 인 절 차 는 입력 데이터 - > 블록 - > 블록 별로 정렬 합 니 다 - > 작은 범위 로 지난번 구간 을 이동 하여 현재 구간 의 결 과 를 얻 을 수 있 습 니 다.  -> 질문 을 번호 순 으로 원래 의 순서 로 되 돌려 줍 니 다. - > 출력 결 과 를 되 돌려 줍 니 다.모 팀 알고리즘 에 대해 서 는 문 제 를 찾 아 다른 사람의 코드 에 따라 한 번 두 드 리 면 알 수 있 습 니 다.
생각:
다음은 본 문제 의 사 고 를 살 펴 보고 나무 모양 의 배열 로 역순 수 와 모 팀 알고리즘 을 어떻게 풀 어야 하 는 지 알 게 되 었 으 니 사실은 문제 가 없다.유일한 난점 은 좌우 단점 이 이동 할 때 구간 역순 수의 증감 상황 을 확정 하 는 것 이다.
구간 [L, R] 내의 역순 수 를 이미 알 고 있다 고 가정 하면 오른쪽 단점 이 한 칸 앞으로 이동 할 때 R = R + 1 일 때 새로 추 가 된 수 를 x 로 설정 하면 x 와 그 전에 삽 입 된 것 보다 큰 수 는 역순 수 를 형성한다. 이 수량 은 전에 말 했 듯 이 구간 길이 - 삽 입 된 것 보다 작은 수 이다.오른쪽 점 에서 한 칸 뒤로 물 러 날 때 상황 이 비슷 해서 더 이상 토론 하지 않 는 다.
왼쪽 점 에서 한 칸, 즉 L = L + 1 을 전진 할 때 구간 이 작 아 지고 역순 수가 감소 하 며 감소 하 는 수량 은 아래 표 시 된 L 의 수 와 그 뒤의 작은 수 에서 발생 하 는 역순 수로 query (a [L] - 1) 이다.왼쪽 점 이 한 칸 뒤로 물 러 났 을 때 상황 은 비슷 하고 더 이상 토론 하지 않 았 다.
코드:

//       
#include
#include
#include
#include
#define N 50010
using namespace std;

int n,ans,a[N],b[N],T[N];
int blk[N]; //     

struct node
{ //   
	int l,r,x,ans; //l,r     ，x     ，ans      
} q[N];

int cmp1(node x,node y)
{ //                  ，        
	if(blk[x.l]==blk[y.l]) return x.rq[i].r)
			{
				add(a[r],-1);
				ans-=r-l-query(a[r]);
				r--;
			}
			while(lq[i].l)
			{
				l--;
				add(a[l],1);
				ans+=query(a[l]-1);
			}
			q[i].ans=ans;
		}
		sort(q+1,q+m+1,cmp2); //            
		for(i=1;i<=m;i++) printf("%d
",q[i].ans);
	}
	return 0;
}