CDQ 분할 학습 노트
CDQ ？
CDQ ， ，
CDQ ？<1>
1. ， ， n ， m ，
/ ，
？
insert query
， insert query
query insert
， ，
예제 1 [사고]: 우 리 는 삽입, 조회 의 조작 을 어떻게 처리 하 는 지 먼저 고려 할 수 있 습 니 다. 앞의 분석 을 통 해 우 리 는 삽입 이 반드시 뒤의 조회 에 영향 을 줄 것 이라는 것 을 알 수 있 습 니 다. 그러면 우 리 는 구간 을 어떻게 실현 해 야 합 니까?현재 구간 을 두 점 [l, r] 으로 나 누 면 대응 하 는 접두사 와 sum [r] - sum [l - 1] 로 구조 문 제 를 처리 할 수 있 습 니 다.
struct NODE{
int type, idx;
ll val;
///type ： ， r， l
/// 1 3 2
///idx
///val ，
} CDQ ， ？
type ， ， idx idx
sum
void CDQ(int l, int r){
if(l + 1 < r){
return ;
}///
int mid = (l + r) >> 1;
CDQ(l, mid);
CDQ(mid, r);
int p, q;
p = l, q = r;
long long sum = 0;
vectorvec;
while(p < mid && q < r)/// [)
{
if(arr[p] < arr[q]){
sum += arr[p].val;
vec.push_back(arr[p]);
p ++;
}
else{
if(arr[q].type == 2) ans[arr[q].val] -= sum;
else if(arr[q].type == 3) ans[arr[q].val] += sum;
vec.push_back(arr[q]);
q ++;
}
}
while(p < mid){
vec.push_back(arr[p ++]);
}
while(q < r){
if(arr[q].type == 2) ans[arr[q].val] -= sum;
else if(arr[q].type == 3) ans[arr[q].val] += sum;
vec.push_back(arr[q]);
q ++;
}
for(int i = 0; i < vec.size(); i ++){
arr[l + i] = vec[i];
}
/**
*
*
*
*
* 1 1
*
* O(nlogn)
* **/
} 코드 첨부:
#include
using namespace std;
/*
CDQ
*/
const int MAXN = 50000 + 5;
int n, m;
typedef long long LL;
struct query {
int type, idx;
LL val;
friend bool operator> 1;
CDQ(l, mid);
CDQ(mid, r);
int p = l, q = mid, tot = 0;
LL sum = 0;
while(p < mid && q < r){
if(arr[p] < arr[q]){
if(arr[p].type == 1) sum += arr[p].val;
temp[tot ++] = arr[p ++];
}
else{
if(arr[q].type == 2) ans[arr[q].val] -= sum;
else if(arr[q].type == 3) ans[arr[q].val] += sum;
temp[tot ++] = arr[q ++];
}
}
while(p < mid){
temp[tot ++] = arr[p ++];
}
while(q < r){
if(arr[q].type == 2) ans[arr[q].val] -= sum;
else if(arr[q].type == 3) ans[arr[q].val] += sum;
temp[tot ++] = arr[q ++];
}
for(int i = 0; i < tot; i ++){
arr[l + i] = temp[i];
}
}
vectorvec;
int main() {
ios::sync_with_stdio(false);
int T, cnt = 0;
cin >> T;
int cases = 0;
while(T --){
memset(ans, 0, sizeof(ans));
vec.clear();
int n;
cin >> n;
cnt = 0;
for(int i = 1; i <= n; i ++){
int num;
cin >> num;
arr[cnt].idx = i, arr[cnt].type = 1, arr[cnt ++].val = num;
}
int ans_num = 0;
while(1){
string str;
cin >> str;
if(str == "Query"){
int l, r;
cin >> l >> r;
vec.push_back(ans_num);
arr[cnt].idx = r, arr[cnt].type = 3, arr[cnt ++].val = ans_num;
arr[cnt].idx = l - 1, arr[cnt].type = 2, arr[cnt ++].val = ans_num ++;
}
else if(str == "Add"){
int c, value;
cin >> c >> value;
arr[cnt].idx = c, arr[cnt].type = 1, arr[cnt ++].val = value;
}
else if(str == "Sub"){
int c, value;
cin >> c >> value;
arr[cnt].idx = c, arr[cnt].type = 1, arr[cnt ++].val = -value;
}
else{
break;
}
}
CDQ(0, cnt);
cout << "Case " << ++cases << ":
";
for(int i = 0; i < vec.size(); i ++){
cout << ans[vec[i]] << endl;
}
}
return 0;
}
<2>
2. ， CDQ
예제 2 [사고]: 이 문 제 는 오프라인 + 선분 트 리 + 이산 화 를 사용 하여 ac 문 제 를 처리 할 수 있 습 니 다. 그러나 우 리 는 CDQ 분 치 를 사용 하여 문 제 를 처리 하 는 것 을 고려 할 수 있 습 니 다. 우 리 는 이 를 3 차원 으로 바 꾸 는 것 을 고려 할 수 있 습 니 다. 게다가 하나의 차원 type 대표 가 삽입 인지 조회 인지 고려 할 수 있 습 니 다. 하 나 를 삽입 하면 하 나 를 조회 하기 때문에 점 의 개 수 는 * 2 입 니 다. 그 다음 에 먼저 따라
friend bool operator ， ， [l,mid) x [mid,r) ，
， [mid, r) ？
， ， [mid, r)
CDQ ， y ， type，
y ， type == 1 ， query(l, r)
type == 0 ， add(y, 1)
， ， ，
[l, mid) add ， [l, mid) add(y, -1)
：#include
#pragma GCC optimize(2)
using namespace std;
int n, m;
const int MAXN = 3e5 + 5;
struct tree_arr{
int tree[MAXN];
inline int lowbit(int x){
return x & -x;
}
inline void add(int k, int val){
while(k <= n + m){
tree[k] += val;
k += lowbit(k);
}
}
inline int sum(int k){
int sum = 0;
while(k){
sum += tree[k];
k -= lowbit(k);
}
return sum;
}
inline int query(int l, int r){
return sum(r) - sum(l - 1);
}
}t_a;
struct NODE{
int x, y, type, idx;
friend bool operatorvec;
int ans[MAXN];
bool cmp(const NODE &a, const NODE &b){
if(a.y != b.y) return a.y < b.y;
if(a.type != b.type) return a.type < b.type;
return a.x < b.x;
}
NODE temp[MAXN];
void CDQ(int l, int r){
if(l + 1 >= r) return;
int mid = (l + r) >> 1;
CDQ(l, mid);
CDQ(mid, r);
int cnt = 0;
int p, q;
p = l, q = mid;
while(p < mid && q < r){
if(arr[p].y <= arr[q].y){
if(arr[p].type == 0)
t_a.add(lower_bound(vec.begin(), vec.end(), arr[p].y) - vec.begin() + 1, 1);
temp[cnt ++] = arr[p];
p ++;
}
else{
if(arr[q].type == 1)
ans[arr[q].idx] += t_a.query(1, lower_bound(vec.begin(), vec.end(), arr[q].y) - vec.begin() + 1);
temp[cnt ++] = arr[q];
q ++;
}
}
while(p < mid){
if(arr[p].type == 0)
t_a.add(lower_bound(vec.begin(), vec.end(), arr[p].y) - vec.begin() + 1, 1);
temp[cnt ++] = arr[p];
p ++;
}
while(q < r){
if(arr[q].type == 1)
ans[arr[q].idx] += t_a.query(1, lower_bound(vec.begin(), vec.end(), arr[q].y) - vec.begin() + 1);
temp[cnt ++] = arr[q];
q ++;
}
for(int i = l; i < mid; i ++){
if(arr[i].type == 0)
t_a.add(lower_bound(vec.begin(), vec.end(), arr[i].y) - vec.begin() + 1, -1);
}
for(int i = 0; i < cnt; i ++){
arr[l + i] = temp[i];
}
return ;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++){
scanf("%d%d", &arr[i].x, &arr[i].y);
vec.push_back(arr[i].y);
arr[i].type = 0;
}
for(int i = 0; i < m; i ++){
scanf("%d%d", &arr[n + i].x, &arr[n + i].y);
arr[n + i].type = 1;
arr[n + i].idx = i;
vec.push_back(arr[i].y);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
sort(arr, arr + (n + m));
CDQ(0, n + m);
for(int i = 0; i < m; i ++){
printf("%d
", ans[i]);
}
return 0;
} < 3 > CDQ 분할 처리 3 차원 편향 문제
예제 3. 3 차원 편차 가 무엇 입 니까?3 차원 편향 순 서 는 3 차원 공간 에서 구간 안의 점 의 개수 나 점 의 총화 가 치 를 묻 는 것 이다. 시간 복잡 도 는 O (nlog (n) log (n) log (n) 이다. 먼저 우 리 는 한 가지 점 을 고려 해 야 한다. 먼저 우 리 는 두 구간 으로 나 누 어 왼쪽 의 x 가 오른쪽 x 보다 작 으 면 우 리 는 왼쪽 의 점 이 오른쪽 점 에 기여 하 는 것 을 고려 해 야 한다.y 의 크기 를 판단 할 때 대응 하 는 z 구조 로 인 한 선분 트 리 나 트 리 배열 을 업데이트 하면 다른 것 은 위 와 비슷 합 니 다.
#include
using namespace std;
const int MAXN = 50005;
const int MAXM = 100005;
struct Point{
int x, y, z, id;
friend bool operator> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
return ;
}
void update(int root, int cnt, int val){
if(tree[root].l == tree[root].r){
tree[root].sum += val;
return ;
}
int mid = (tree[root].l + tree[root].r) >> 1;
if(cnt <= mid){
update(root << 1, cnt, val);
}
else{
update(root << 1 | 1, cnt, val);
}
tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
return ;
}
int query(int root, int l, int r){
if(tree[root].l >= l && tree[root].r <= r){
return tree[root].sum;
}
int mid = (tree[root].l + tree[root].r) >> 1;
if(r <= mid){
return query(root << 1, l, r);
}
else if(l > mid){
return query(root << 1 | 1, l, r);
}
else{
return query(root << 1, l, mid) + query(root << 1 | 1, mid + 1, r);
}
}
}seg;
void CDQ(int l, int r){///[)
if(l + 1 >= r){
return ;
}
int mid = (l + r) >> 1;
int p, q;
p = l, q = mid;
CDQ(l, mid);
CDQ(mid, r);
sort(arr + l, arr + mid, cmp);
sort(arr + mid, arr + r, cmp);
while(p < mid && q < r){
if(arr[p].y <= arr[q].y){
seg.update(1, arr[p].z, 1);
p ++;
}
else{
ans[arr[q].id] += seg.query(1, 1, arr[q].z);
q ++;
}
}
while(p < mid){
seg.update(1, arr[p].z, 1);
p ++;
}
while(q < r){
ans[arr[q].id] += seg.query(1, 1, arr[q].z);
q ++;
}
for(int i = l; i < mid; i ++){
seg.update(1, arr[i].z, -1);
}
return ;
}
int main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> arr[i].x >> arr[i].y >> arr[i].z;
arr[i].id = i;
}
seg.build(1, 1, 100001);
sort(arr + 1, arr + n + 1);
CDQ(1, n + 1);
for(int i = 1; i <= n; i ++){
cout << ans[i] << endl;
}
return 0;
} 다음으로 전송:https://www.cnblogs.com/qq136155330/p/11570075.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
