Phân chia CDQ

Phương pháp phân chia CDQ thường được sử dụng để thay thế các cấu trúc dữ liệu phức tạp, giúp giải quyết các vấn đề liên quan đến thứ tự đa chiều và tối ưu hóa quá trình chuyển trạng thái quy hoạch động. Ý tưởng chính là chia nhỏ bài toán thành các cặp điểm và xử lý theo ba loại: \(\mathbf{\small{1}}\le i<j\le mid\), \(\mathbf{\small{1}}\le i\le mid<j\le n\), \(mid<i<j\le n\). Sau đó sử dụng thời gian \(O(logn)\) bổ sung để tính toán loại thứ hai, thường thông qua cây BIT hoặc cây đoạn.

Bài tập minh họa

P3810 【Mẫu】Thứ tự ba chiều (Hoa nở trên đường)

Đầu tiên sắp xếp theo khóa \(a\), loại bỏ phần tử trùng lặp, sau đó thực hiện phân chia. Trong quá trình phân chia, ta cần giải quyết vấn đề thứ tự hai chiều \(b,c\), sử dụng cây BIT để tìm nghiệm. Sắp xếp hai dãy theo khóa \(b\), dùng kỹ thuật hai con trỏ để duy trì và thống kê kết quả trong cây BIT. Vì chỉ duyệt qua một lần nên độ phức tạp là \(O(nlogn)\). Khi tính kết quả cuối cùng, lưu ý rằng giá trị thực tế của mỗi \(i\) là \(ans_i+cnt_i-\mathbf{\small{1}}\).

Mã nguồn Xem mã nguồn

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX_N=2*114514,MAX_M=1919810;

struct Item{
    ll x,y,z,count,result;
    bool operator !=(const Item &other)const{
        return x!=other.x || y!=other.y || z!=other.z;
    }
}data[MAX_N];

ll n,m,fenwick_tree[MAX_N],final_result[MAX_N];

ll get_lowbit(ll x){return x&-x;}

void fenwick_update(ll pos,ll value){
    while(pos<=m){
        fenwick_tree[pos]+=value;
        pos+=get_lowbit(pos);
    }
}

ll fenwick_query(ll pos){
    ll total=0;
    while(pos){
        total+=fenwick_tree[pos];
        pos-=get_lowbit(pos);
    }
    return total;
}

bool sort_by_xyz(Item a,Item b){
    return a.x==b.x ? (a.y==b.y ? a.z<b.z : a.y<b.y) : a.x<b.x;
}

bool sort_by_yz(Item a,Item b){
    return a.y==b.y ? a.z<b.z : a.y<b.y;
}

void process_range(ll left,ll right){
    if(left==right) return;
    
    ll middle=left+right>>1;
    process_range(left,middle);
    process_range(middle+1,right);
    
    sort(data+left,data+middle+1,sort_by_yz);
    sort(data+middle+1,data+right+1,sort_by_yz);
    
    ll pointer=left;
    for(int idx=middle+1;idx<=right;++idx){
        while(data[idx].y>=data[pointer].y && pointer<=middle){
            fenwick_update(data[pointer].z,data[pointer].count);
            ++pointer;
        }
        data[idx].result+=fenwick_query(data[idx].z);
    }
    
    for(int idx=left;idx<pointer;++idx) 
        fenwick_update(data[idx].z,-data[idx].count);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;++i) 
        cin>>data[i].x>>data[i].y>>data[i].z;
    
    sort(data+1,data+n+1,sort_by_xyz);
    
    ll unique_count=0,current_count=0;
    for(int i=1;i<=n;++i){
        ++current_count;
        if(data[i]!=data[i+1]){
            data[++unique_count]=data[i];
            data[unique_count].count=current_count;
            current_count=0;
        }
    }
    
    process_range(1,unique_count);
    
    for(int i=1;i<=unique_count;++i) 
        final_result[data[i].result+data[i].count-1]+=data[i].count;
    
    for(int i=0;i<n;++i) 
        cout<<final_result[i]<<'\n';
    
    return 0;
}

P2487 [SDOI2011] Chặn tên lửa

Trước tiên xem xét thuật toán cơ bản: câu hỏi đầu tiên có thể giải trực tiếp bằng quy hoạch động \(O(n^{\mathbf{\small{2}}})\), câu hỏi thứ hai yêu cầu thêm vài mảng phụ trợ: \(f\mathbf{\small{2}}_i\) biểu thị độ dài dãy con không tăng bắt đầu từ vị trí \(i\), thêm hai mảng \(g\mathbf{\small{1}},g\mathbf{\small{2}}\) để đếm số lượng dãy con không tăng kết thúc và bắt đầu tại \(i\). Những vị trí \(i\) thỏa mãn \(f\mathbf{\small{1}}_i+f\mathbf{\small{2}}_i-\mathbf{\small{1}}=ans\) sẽ có kết quả là \(\dfrac{g\mathbf{\small{1}}_i\times g\mathbf{\small{2}}_i}{total}\), với \(total\) là tổng số phương án. Việc tính kết quả bắt đầu từ \(i\) có thể thực hiện bằng cách đảo ngược dãy và đổi dấu giá trị rồi áp dụng quy hoạch động bình thường.

Để tối ưu hóa, nhận thấy rằng dãy không giảm dài nhất thực chất là vấn đề thứ tự ba chiều. Tuy nhiên cần chú ý thứ tự tính toán: trước tiên xử lý đoạn trái, sau đó đoạn giữa, rồi mới đến đoạn phải, nếu không quá trình chuyển trạng thái quy hoạch động sẽ sai lệch. Trong quá trình phân chia, yêu cầu duy trì trở thành cập nhật điểm và truy vấn đoạn, nhưng do không còn nhớ rõ cách dùng cây BIT nên đã sử dụng cây đoạn. Có thể sử dụng kỹ thuật xóa toàn bộ cây đoạn \(O(n)\) để tránh phải mở thêm mảng lưu trữ. Ngoài ra cần sử dụng kiểu long double.

Mã nguồn Xem mã nguồn

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define LEFT_CHILD now<<1
#define RIGHT_CHILD now<<1|1
const ll MAX_N=2*114514,MAX_M=1919810;

ll n,m,values[MAX_N];

struct Point{
    ll time;
    ld height,speed;
}original[MAX_N],temp_array[MAX_N],auxiliary[MAX_N];

struct State{
    ld value,count;
}dp_forward[MAX_N],dp_backward[MAX_N];

bool compare_time(Point a,Point b){
    return a.time<b.time;
}

bool compare_height_speed(Point a,Point b){
    return a.height==b.height ? a.speed>b.speed : a.height>b.height;
}

State merge_states(State x,State y){
    return x.value==y.value ? 
        (State){x.value,x.count+y.count} : 
        (x.value>y.value ? x : y);
}

struct SegmentTree{
    ll left,right;
    State node_value;
}tree[4*MAX_N];

void propagate_up(ll now){
    tree[now].node_value=merge_states(tree[LEFT_CHILD].node_value,tree[RIGHT_CHILD].node_value);
}

void construct_tree(ll now,ll l,ll r){
    tree[now].left=l,tree[now].right=r;
    tree[now].node_value=(State){0,0};
    if(l==r) return;
    
    ll mid=l+r>>1;
    construct_tree(LEFT_CHILD,l,mid);
    construct_tree(RIGHT_CHILD,mid+1,r);
}

void modify_tree(ll now,ll target,State new_val){
    if(tree[now].left==tree[now].right){
        tree[now].node_value=merge_states(tree[now].node_value,new_val);
        return;
    }
    
    ll mid=tree[now].left+tree[now].right>>1;
    if(target<=mid) modify_tree(LEFT_CHILD,target,new_val);
    else modify_tree(RIGHT_CHILD,target,new_val);
    propagate_up(now);
}

State query_tree(ll now,ll x,ll y){
    if(tree[now].left>=x && tree[now].right<=y) 
        return tree[now].node_value;
    
    ll mid=tree[now].left+tree[now].right>>1;
    State result=(State){0,0};
    
    if(x<=mid) result=merge_states(result,query_tree(LEFT_CHILD,x,y));
    if(y>mid) result=merge_states(result,query_tree(RIGHT_CHILD,x,y));
    
    return result;
}

void clear_node(ll now,ll target){
    tree[now].node_value=(State){0,0};
    if(tree[now].left==tree[now].right) return;
    
    ll mid=tree[now].left+tree[now].right>>1;
    if(target<=mid) clear_node(LEFT_CHILD,target);
    else clear_node(RIGHT_CHILD,target);
}

void divide_conquer(ll l,ll r,State *dp_array){
    if(l==r){
        if(!dp_array[(ll)temp_array[l].time].value)
            dp_array[(ll)temp_array[l].time]=(State){1,1};
        return;
    }
    
    ll mid=l+r>>1;
    divide_conquer(l,mid,dp_array);
    
    for(int i=mid+1;i<=r;++i) auxiliary[i]=temp_array[i];
    sort(auxiliary+mid+1,auxiliary+r+1,compare_height_speed);
    
    ll j=l;
    for(int i=mid+1;i<=r;++i){
        while(temp_array[j].height>=auxiliary[i].height && j<=mid){
            modify_tree(1,temp_array[j].speed,dp_array[(ll)temp_array[j].time]);
            ++j;
        }
        
        State query_result=query_tree(1,auxiliary[i].speed,m);
        if(query_result.value){
            ++query_result.value;
            dp_array[(ll)auxiliary[i].time]=merge_states(dp_array[(ll)auxiliary[i].time],query_result);
        }
    }
    
    for(int i=l;i<=j;++i) clear_node(1,temp_array[i].speed);
    divide_conquer(mid+1,r,dp_array);
    sort(temp_array+l,temp_array+r+1,compare_height_speed);
}

void execute_solution(bool reverse_flag){
    for(int i=1;i<=n;++i) temp_array[i]=original[i],values[i]=original[i].speed;
    
    sort(temp_array+1,temp_array+n+1,compare_time);
    sort(values+1,values+n+1);
    m=unique(values+1,values+n+1)-values-1;
    
    for(int i=1;i<=n;++i) 
        temp_array[i].speed=lower_bound(values+1,values+m+1,temp_array[i].speed)-values;
    
    construct_tree(1,1,m);
    if(!reverse_flag) divide_conquer(1,n,dp_forward);
    else divide_conquer(1,n,dp_backward);
}

ld max_length,total_ways;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) 
        cin>>original[i].height>>original[i].speed,original[i].time=i;
    
    execute_solution(0);
    
    for(int i=1;i<=n;++i) 
        original[i]=(Point){n-i+1,-original[i].height,-original[i].speed};
    
    execute_solution(1);
    
    for(int i=1;i<=n;++i) 
        max_length=max(max_length,dp_forward[i].value);
    
    for(int i=1;i<=n;++i) 
        if(max_length==dp_forward[i].value) 
            total_ways+=dp_forward[i].count;
    
    printf("%Ld\n",(ll)max_length);
    
    for(int i=1;i<=n;++i){
        if(dp_forward[i].value+dp_backward[n-i+1].value-1==max_length) 
            printf("%0.5Lf ",(dp_forward[i].count*1.0*dp_backward[n-i+1].count*1.0/total_ways));
        else 
            printf("0.00000 ");
    }
    
    return 0;
}