HDU 5126 (stars) 4 차원 편향, cdq 분할
해법: 조작 번호 도 순서 쌍 에 넣 고 4 차원 순서 쌍 을 구성 하 며 문 제 는 4 차원 편차 문제 로 전환 합 니 다.첫 번 째 글 씨 는 cdq 세트 cdq 세트 트 리 배열 의 방법 만 썼 습 니 다. 나중에 cdq 세트 트 리 등 방법 을 시도 하여 이 블 로 그 를 업데이트 하 겠 습 니 다.다음은 인내심 을 가지 고 첫 번 째 방법 을 말씀 드 리 겠 습 니 다.
저 희 는 4 차원 순서 쌍 (i, a, b, c), a, b, c 를 입력 하 는 변수 로 정의 합 니 다. i 는 현재 작업 번호 입 니 다.
예비 처 리 는 4 차원 (c) 을 이산 화하 고 일련의 초기 화 작업 (약) 을 진행한다.4 차원 짝 에 1 차원 변수 k (단 복잡 도 를 증가 하지 않 음), 즉 (i, a, b, c, k), k = 0 은 이 짝 이 첫 번 째 조작의 짝, 즉 삽 입 된 짝 임 을 나타 낸다.k = - 1 또는 1 시 에 이 순서 쌍 을 표시 할 때 두 번 째 작업 의 순서 쌍, 즉 조회 의 순서 쌍 을 나타 낸다.첫 번 째 조작 은 순서 쌍 (i, a, b, c, 0) 이다.두 번 째 조작, 순서 쌍 은 (i, a1, b1, c1, k1), (i, a2, b2, c2, k2) 이다.이 두 차례 의 짝 을 8 개의 짝 으로 나 누 면 (i, a2, b22, c2, c2, + 1), (i, a1 - 1, b11 - 1, b22, c2, c2, c2, c2, - 1), (i, a2, b12, c2, c1 - 1, 1 - 1, 1 - 1 - 1, 1 - 1, b21 - 1, c1 - 1, c1 - 1, + 1), (i, a1 - 1, b21 - 1, b21, c1 - 1, c1 - 1, c1 - 1, 1 - 1, + 1), (i, a1 - 1 - 1, b11 - 1, c1 - 1, c1 - 1, c1 - 1, c1 - 1, c1 - 1, c1 - 1, 1 - 1;세 심하게 보면 이 8 개의 서 우 는 실제로 용 척 원 리 를 하고 통계 조작 2 를 위해 만 든 것 임 을 알 수 있다.
1. 먼저 i 를 작은 것 에서 큰 것 으로 정렬 합 니 다 (사실은 입력 에 따라 정렬 되 었 습 니 다). 이것 은 첫 번 째 입 니 다.p1 에 n 개의 순서 쌍 (i, a, b, c, k) 을 저장 합 니 다.
2. p1 을 병합 하고 [1, n] 1, 병합 [l, r]: l < r, mid = (l + r) > 1 을 설정 하면 재 귀 진행 절차 1, 병합 [l, mid] 을 하고 2 절 차 를 진행한다.그렇지 않 으 면 중지 합 니 다.2. [l, mid] 에서 k = 0 의 순서 쌍 을 차례대로 p2 에 넣 고 [mid + 1, r] 에서 k = - 1 또는 k = 1 의 순서 쌍 을 차례대로 p2 에 넣 습 니 다. 이때 p2 는 n2 개의 순서 쌍 이 있 습 니 다.p2 를 정렬 (x 우선, i 우선) 한 다음 에 3 을 조작 하고 p2 를 병합 하여 [1, n2] 합 니 다.마지막 진행 단계 3.3. 진행 절차 1, 병합 [mid + 1, r].
3. p2 를 병합 하고 [1, n2] 1, 병합 [l, r]: l < r, mid = (l + r) > 1 을 설정 하면 재 귀 진행 절차 1, 병합 [l, mid] 을 하고 2 절 차 를 진행한다.그렇지 않 으 면 중지 합 니 다.2. [l, mid] 에서 k = 0 의 순서 쌍 을 s1 에 순서대로 넣 고 ns1 개가 설치 되 어 있 습 니 다.[mid + 1, r] 에서 k = - 1 또는 k = 1 의 순서 쌍 을 s2 에 순서대로 넣 고 ns2 개가 설치 되 어 있 습 니 다.s1 과 s2 를 각각 정렬 (y 우선) 하고 이 지침 법 으로 모든 s2 의 순서 쌍 을 업데이트 하기 전에 s1 에서 모든 y 값 이 현재 순서 쌍 의 y 값 보다 크 지 않 은 순서 쌍 은 모두 트 리 배열 에 가입 되 었 음 을 보증 합 니 다.트 리 배열 은 접두사 와...현재 s2 의 순서 쌍 을 (i, a, b, c, k) 로 설정 하면 ans [i] + = k * query (c), query (c) 는 트 리 배열 을 조회 하고 c 보다 크 지 않 은 요소 가 몇 개 있 는 지 표시 합 니 다.s2 모든 순서 쌍 이 업 데 이 트 된 후 트 리 배열 에서 s1 순서 쌍 이 업 데 이 트 된 값 을 비 웁 니 다.마지막 진행 단계 3.3. 진행 절차 1, 병합 [mid + 1, r].
소결: cdq 분 치 는 1 차원 씩 내 려 갈 때마다 log 의 복잡 도 를 사용 하여 cdq 분 치 를 반복 적 으로 음미 하고 cdq 분 치 를 많이 하 는 문제 가 cdq 를 이해 하 는 왕도 입 니 다.
배경 그림 이 없어 서 잘 설명 되 지 않 습 니 다. 주로 코드 를 봅 니 다 (g + + 를 선택 한 후 제출 합 니 다)
//Hello. I'm Peter.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define peter cout<<"i am peter"<<endl
#define fuck(x) cerr << #x << " <- " << x << endl
typedef long long ll;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int Q;
struct Pair{
int x, y, z, k, id;
Pair(){}
Pair(int x1,int y1,int z1,int k1,int id1){
x = x1, y = y1, z = z1, k = k1, id = id1;
}
};
bool cmpxid(const Pair a, const Pair b){
if(a.x != b.x) return a.x < b.x;
else return a.id < b.id;
}
bool cmpy(const Pair a, const Pair b){
return a.y < b.y;
}
#define N 50010
Pair p1[N*8],s1[N*8],s2[N*8],p2[N*8];
int np1;
int li[N*2],nli,ans[N];
namespace bit{
int bit[N*2];
void clear(){
for(int i = 1; i <= nli; i++) bit[i] = 0;
}
void update(int x,int val){
for(int i = x; i <= nli; i += i&-i){
bit[i] += val;
}
}
int query(int x){
int ans = 0;
for(int i = x; i > 0; i -= i&-i){
ans += bit[i];
}
return ans;
}
void clear(int x){
for(int i = x; i <= nli; i += i&-i){
bit[i] = 0;
}
}
};
void cdq2(int l,int r){
if(r <= l) return;
int mid = (l + r) >> 1;
cdq2(l, mid);
int ns1 = 0, ns2 = 0;
for(int i = l; i <= mid; i++) if(!p2[i].k) s1[++ns1] = p2[i];
for(int i = mid + 1; i <= r; i++) if(p2[i].k) s2[++ns2] = p2[i];
sort(s1 + 1, s1 + 1 + ns1, cmpy);
sort(s2 + 1, s2 + 1 + ns2, cmpy);
int t1 = 1;
for(int t2 = 1; t2 <= ns2; t2++){
while(t1 <= ns1 && s1[t1].y <= s2[t2].y) bit::update(s1[t1].z, +1), t1++;
ans[s2[t2].id] += s2[t2].k * bit::query(s2[t2].z);
}
for(int i = 1; i < t1; i++) bit::clear(s1[i].z);
cdq2(mid + 1, r);
}
void cdq1(int l,int r){
if(r <= l) return;
int mid = (l + r) >> 1;
cdq1(l, mid);
int np2 = 0;
for(int i = l; i <= mid; i++) if(!p1[i].k) p2[++np2] = p1[i];
for(int i = mid + 1; i <= r; i++) if(p1[i].k) p2[++np2] = p1[i];
sort(p2 + 1, p2 + 1 + np2, cmpxid);
cdq2(1, np2);
cdq1(mid + 1, r);
}
bool isque[N];
int main(){
int T = read();
for(int kase = 1; kase <= T; kase++){
Q = read();
np1 = nli = 0;
for(int i = 1; i <= Q; i++){
int A = read();
isque[i] = A == 2? 1: 0;
if(A == 1){
int x, y, z;
x = read(), y = read(), z = read();
p1[++np1] = Pair(x, y, z, 0, i);
li[++nli] = z;
}
else{
int x1,y1,z1,x2,y2,z2;
x1=read(),y1=read(),z1=read(),x2=read(),y2=read(),z2=read();
p1[++np1] = Pair(x2, y2, z2, 1, i);
p1[++np1] = Pair(x1 - 1, y2, z2, -1, i);
p1[++np1] = Pair(x2, y1 - 1, z2, -1, i);
p1[++np1] = Pair(x2, y2, z1 - 1, -1, i);
p1[++np1] = Pair(x1 - 1, y1 - 1, z2, 1, i);
p1[++np1] = Pair(x2, y1 - 1, z1 - 1, 1, i);
p1[++np1] = Pair(x1 - 1, y2, z1 - 1, 1, i);
p1[++np1] = Pair(x1 - 1, y1 - 1, z1 - 1, -1, i);
li[++nli] = z2;
li[++nli] = z1 - 1;
}
}
sort(li + 1, li + 1 + nli);
nli = (int)(unique(li + 1, li + 1 + nli) - (li + 1));
for(int i = 1; i <= np1; i++) p1[i].z = (int)(lower_bound(li + 1, li + 1 + nli, p1[i].z) - li);
bit::clear();
for(int i = 1; i <= Q; i++) ans[i] = 0;
cdq1(1, np1);
for(int i = 1; i <= Q; i++) if(isque[i]) printf("%d
",ans[i]);
}
return 0;
}좋은 웹페이지 즐겨찾기
