bzoj 3262 (cdq 분할 + 트 리 배열)

(진지 한 문 제 는 뒤에 풀 려 있 습 니 다) 기울 임 말 은 모두 1 년 전에 cdq 를 분명하게 풀 지 않 은 상태 에서 대처 한 것 입 니 다. 지금 은 cdq 를 진정 으로 이해 하 더 라 도 이 말 들 을 여기에 남 겨 두 었 습 니 다. 왜냐하면 꽃 은 다시 피 는 날 이 없고 사람 은 더 이상 소년 이 없습니다.
RunID
User
Problem
Result
Memory
Time
Language
Code_Length
Submit_Time
2374693
2711694897
3262
Accepted
6376 kb
1632 ms
C++/Edit
1851 B
2017-10-23 19:52:20
2374687
2711694897
3262
Accepted
6376 kb
3160 ms
C++/Edit
1852 B
2017-10-23 19:50:45
먼저 문제 외 화 를 말 하 세 요. 한 장의 그림 은 함수 비용 이 얼마나 많은 지 알려 주 고 다시 싣 는 것 을 사용 합 니 다. "
 
문제 풀이:
템 플 릿 화 된 3 차원 편 서 를 비교 하 다.
1 차원 정렬, 2 차원 cdq 분할, 3 차원 트 리 배열.
매번 [l, mid] 가 [mid + 1, r] 에 미 치 는 영향 을 처리 할 때마다 2 차원 을 비교 하고 3 차원 (l, mid] 구간 의 x 는 [mid + 1, r] 구간 의 x 보다 작 기 때문에 3 차원 은 트 리 배열 로 조건 을 만족 시 키 는 개 수 를 유지 합 니 다) 을 조회 합 니 다. 2 차원 이 요구 에 부합 할 때 트 리 배열 에 넣 습 니 다. [mid + 1, r] 구간 의 ans (처리 후 트 리 배열 을 복원 하 는 것 을 기억 합 니 다) 를 업데이트 할 때마다.
————————————————————————————————————————————————————————
정 해: cdq 분할 + 트 리 배열
먼저 1 차원 a 에 대해 순 서 를 매기 기 때문에 이 1 차원 뒤 에는 먼저 상관 하지 않 아 도 된다.
2 차원 b 를 cdq 로 나 누 어 구간 [l, r] 2 를 [l, mid] 와 [mid + 1, r] 로 나 누 어 좌우 구간 을 두 바늘 로 쓸 고 i 는 왼쪽 구간 을 쓸 고 j 는 오른쪽 구간 을 쓸 었 다.(메모: 모든 add 가 이동 할 때마다 j 지침 을 빼 야 합 니 다).
두 바늘 은 한 번 쓸 때마다 O (n) 이 고, 재 귀 각 층 을 계산 하면 logn 회 를 쓸 었 기 때문에 총 복잡 도 는 O (nlogn) 이다.
엄격 하고 자신 보다 크 지 않 은 요 소 는 i 개 입 니 다. 이런 요 소 는 몇 개 입 니까?
 
주의: 먼저 cdq 함수 에서 좌우 하위 구간 을 재 귀적 으로 처리 하고 현재 구간 을 처리 해 야 합 니 다. 2 차원 b 로 정렬 하면 원래 1 차원 a 의 오름차 순 서 를 흐 트 러 뜨 릴 수 있 기 때 문 입 니 다!!그 층 을 어떻게 배열 하 는 지, 현재 층 의 1 차원 a 는 여전히 왼쪽 구간 이 오른쪽 구간 보다 작 다 는 것 을 만족 시 켜 야 안심 하고 대담 하 게 후 2 차원 을 조작 할 수 있다.

#include
#include
#include
#include
using namespace std;
const int N=1e5+4;
int c[N<<1],n,nn=0,lim,f[N];
struct Node {
	int a,b,c,rep,ans;
	friend bool operator '9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
inline void add(int x,int val) {
	for (int i=x;i<=lim;i+=i&-i) c[i]+=val;
}
inline int query(int x) {
	int ret=0;
	for (int i=x;i;i-=i&-i) ret+=c[i];
	return ret;
}
void cdq(int l,int r) {
	if (l==r) return ;
	int mid=l+r>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(p+l,p+mid+1);//cmpb
	sort(p+mid+1,p+r+1);//cmpb
	int i=l,j=mid+1;
	while (j<=r) {
		while (i<=mid&&p[i].b<=p[j].b) add(p[i].c,p[i].rep),++i;
		p[j].ans+=query(p[j].c),++j;
	}
	for (int k=l;k