boxmoe_header_banner_img

Hello! 欢迎来到DRheEheAM的blog！

加载中

POST
文章导读
信息学

Feb. 3rd 总结 | CDQ分治 (Chpt.3)

avatar
DRheEheAM_Gary 2026-02-03 21
0 评论

什么你问我 Chpt.2哪去了？

每日 Ad-hoc

P11145 「SFMOI Round I」Strange Homura Game

这辈子第一次写交互题…

注意到：当 x>mx > m 时，若 x mod m=ax\ \text{mod}\ m =a ，容易发现 m|(x−a)m \mid (x-a) 。
所以 (x−a−1) mod m+1=m(x-a-1)\ \text{mod}\ m +1 =m

解决问题：

#include <bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int mod=1e18;
int question (int x) {
    cout<<"? "<<x<<"\n";
    cout.flush();
    int res;
    cin>>res;
    return res;
}
void answer (int x) {
    cout<<"! "<<x<<"\n";
    cout.flush();
}
signed main(){
    Cios;
    int T;
    cin>>T;
    while(T--){
        int x=question(mod);
        int y=question(mod-x-1);
        answer(y+1);
    }
    return 0;
}

CDQ 分治

了解更多关于CDQ分治定义的信息 -> Feb. 1st 总结 | CDQ分治 (Chpt.1)

今天使用 CDQ 分治解决了一些较模版的题目：

P10281 [USACO24OPEN] Grass Segments G

这道题我们分析一下式子：
因为 li ~ ril_i \text{ \textasciitilde}\ r_i 与 lj ~ rjl_j \text{ \textasciitilde}\ r_j 之间重合部分长度 leni,jlen_{i,j} 可以使用如下式子表示，读者请自行理解：

leni,j=min⁡(ri,rj)−max⁡(li,lj)≥kilen_{i,j} = \min(r_i,r_j) -\max(l_i,l_j) \ge k_i

所以我们拆开式子：

{ri−li≥kiri−lj≥kirj−li≥kirj−lj≥ki\begin{cases} r_i-l_i\ge k_i \\ r_i-l_j\ge k_i \\ r_j-l_i\ge k_i \\ r_j-l_j\ge k_i\\ \end{cases}

去掉第一个式子（题目保证）后变形：

{lj≤ri−kirj≥li+kirj−lj≥ki\begin{cases} l_j\le r_i-k_i \\ r_j\ge l_i+k_i \\ r_j-l_j\ge k_i\\ \end{cases}

注意到这类似三维偏序的不等式式子，于是定义结构 {xi,yi,zi}\{ x_i,y_i,z_i\}，

对于每个区间 ii ，拆分为 {ri−ki,li+ki,ki}\{ r_i-k_i ,l_i+k_i,k_i\} 与 {li,ri,ri−li}\{l_i,r_i,r_i-l_i\} 两种类型的区间，前者用于查询，后者用于被查询。

随后三维偏序，使用 CDQ 分治思路即可。

#include <bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
intc N=2e5+10;
int n,ans[N*2];
struct node {
    int l,r,k,len,id,x,y;
    static bool cmpk (node a,node b) {
        if (a.k==b.k) return a.id<b.id;
        return a.k<b.k;
    }
    static bool cmpx (node a,node b) {
        if (a.x==b.x) return a.id<b.id;
        return a.x>b.x;
    }
    static bool cmpr (node a,node b) {
        if (a.r==b.r) return a.id<b.id;
        return a.r>b.r;
    }
};
node a[N*2];
class Fenwick {
    int tr[N*2];
    int maxn;
    int lowbit (int x) {return x&(-x);}
public:
    void init(int sz) {
        maxn = sz;
        memset(tr,0,sizeof(tr));
    }
    void update (int x,int v) {
        while (x<=maxn) {
            tr[x]+=v;
            x+=lowbit(x);
        }
    }
    int query (int x) {
        int res=0;
        while (x) {
            res+=tr[x];
            x-=lowbit(x);
        }
        return res;
    }
}bit;
void cdq (int l,int r) {
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int i=l,j=mid+1;
    sort(a+l,a+mid+1,node::cmpx);
    sort(a+mid+1,a+r+1,node::cmpr);
    for (;i<=mid;i++) {
        while (j<=r && a[j].r>=a[i].x) {
            if (a[j].id>n) bit.update(a[j].l,1);
            j++;
        }
        if (a[i].id<=n) ans[a[i].id]+=bit.query(a[i].y);
    }
    for (int i=mid+1;i<j;i++) {
        if (a[i].id>n) bit.update(a[i].l,-1);
    }
}
vector <int> s;
signed main(){
    Cios;
    cin>>n;
    for (int i=1;i<=n;i++) {
        int l,r,k;
        cin>>l>>r>>k;
        a[i]={l,r,k,r-l,i,l+k,r-k};
        s.push_back(a[i].l);
        s.push_back(a[i].y);
    }
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    int m = (int)s.size();
    for (int i=1;i<=n;i++) {
        a[i].l=lower_bound(s.begin(),s.end(),a[i].l)-s.begin()+1;
        a[i].y=lower_bound(s.begin(),s.end(),a[i].y)-s.begin()+1;
        a[i+n]=a[i];
        a[i+n].k=a[i].len;
        a[i+n].id+=n;
    }
    bit.init(m);
    sort (a+1,a+1+n*2,node::cmpk);
    cdq(1,n*2);
    for (int i=1;i<=n;i++) cout<<ans[i]-1<<"\n";
    return 0;
}

P4390 [BalkanOI 2007] Mokia 摩基亚

这道题其实只要理解将查询拆成四个，按时间，横坐标，纵坐标三维偏序即可，不过多赘述。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+5,M=2e6+5;
int w,op,tot,qcnt,ans[N];
struct Node {
    int time,type,x,y,val,id;
    bool operator < (const Node &p) const {
        if(time!=p.time) return time<p.time;
        if(x!=p.x) return x<p.x;
        if(y!=p.y) return y<p.y;
        return type<p.type;
    }
}q[N],tmp[N];
class BIT {
    int node[M];
    int lowbit(int x) {return x&-x;}
    public:
    void add(int pos,int val) {
        while(pos<=w) {
            node[pos]+=val;
            pos+=lowbit(pos);
        }
    }
    int ask(int pos) {
        int res=0;
        while(pos) {
            res+=node[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
    void clear(int pos) {
        while(pos<=w) {
            if(!node[pos]) break;
            node[pos]=0;
            pos+=lowbit(pos);
        }
    }
}bit;
bool cmpX(const Node &a,const Node &b) {
    if(a.x!=b.x) return a.x<b.x;
    if(a.y!=b.y) return a.y<b.y;
    return a.type<b.type;
}
void cdq(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(q+l,q+mid+1,cmpX);
    sort(q+mid+1,q+r+1,cmpX);
    int i=l,j=mid+1;
    while(j<=r) {
        while(i<=mid&&q[i].x<=q[j].x) {
            if(q[i].type==1) bit.add(q[i].y,q[i].val);
            i++;
        }
        if(q[j].type==2) ans[q[j].id]+=q[j].val*bit.ask(q[j].y);
        j++;
    }
    for(int k=l;k<i;k++) {
        if(q[k].type==1) bit.clear(q[k].y);
    }
}
signed main() {
    Cios;
    cin>>op>>w;
    w++;
    int time=0;
    while(cin>>op&&op!=3) {
        time++;
        if(op==1) {
            int x,y,val;
            cin>>x>>y>>val;
            x++;
            y++;
            q[++tot]={time,1,x,y,val,0};
        } 
        else {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            x1++; 
            y1++; 
            x2++; 
            y2++;
            qcnt++;
            q[++tot]={time,2,x2,y2,1,qcnt};
            q[++tot]={time,2,x1-1,y2,-1,qcnt};
            q[++tot]={time,2,x2,y1-1,-1,qcnt};
            q[++tot]={time,2,x1-1,y1-1,1,qcnt};
        }
    }
    sort(q+1,q+tot+1);
    cdq(1,tot);
    for(int i=1;i<=qcnt;i++) cout<<ans[i]<<'\n';
    return 0;
}

接下来是 CDQ 分治的其他应用，比如说解决带修莫队板子（？

P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列

这道题…我很难说

等我再理解一下（qwq

其实就是和 P1972 [SDOI2009] HH 的项链 差不多相同的思路

对于一个颜色 ii ，记录它的前一个颜色 preipre_i 。

对于一次查询 lq→rql_q \rightarrow r_q，其实就是查询 lql_q 到 rqr_q 间有多少个 prei<lqpre_i < l_q 。

用这个思路 CDQ 分治即可。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef set<int>::iterator iit;
intc N=1e6+10;
int n,m,tot,a[N],pri[N],ans[N]
struct node {
    int op,x,y,id,k;
}q[N],tmp[N];
set<int> s[N];
class Fenwick {
    int tr[N];
    int lb (int x) {return x&(-x);}
    public:
    void update (int x,int v) {
        while (x<=n) {
            tr[x]+=v;
            x+=lb(x);
        }
    }
    int query (int x) {
        int res=0;
        while (x) {
            res+=tr[x];
            x-=lb(x);
        }
        return res;
    }
}bit;
void cdq (int l,int r) {
    if (l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int i=l,j=mid+1,t=l-1;
    while (i<=mid&&j<=r) {
        if (q[i].y<q[j].y) {
            if (!q[i].op) bit.update(q[i].x,q[i].k);
            tmp[++t]=q[i];
            i++;
        }
        else {
            if (q[j].op) ans[q[j].id]+=q[j].k*bit.query(q[j].x);
            tmp[++t]=q[j];
            j++;
        }
    }
    while (i<=mid) {
        if (!q[i].op) bit.update(q[i].x,q[i].k);
        tmp[++t]=q[i];
        i++;
    }
    while (j<=r) {
        if (q[j].op) ans[q[j].id]+=q[j].k*bit.query(q[j].x);
        tmp[++t]=q[j];
        j++;
    }
    for (i=l;i<=mid;i++) {
        if (!q[i].op) bit.update(q[i].x,-q[i].k);
    }
    for (i=l;i<=r;i++) q[i]=tmp[i];
}
inline int pre (int x,int y) {
    iit it=s[x].lower_bound(y);
    if (it==s[x].begin()) return 0;
    return *(--it);
}
inline int nxt (int x,int y) {
    iit it=s[x].upper_bound(y);
    if (it==s[x].end()) return 0;
    return *it;
}
signed main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        s[a[i]].insert(i);
        q[++tot]=node({0,i,pre(a[i],i),0,1});
        pri[i]=pre(a[i],i);
    }
    char op;
    int cnt=0,l,r,opt;
    for (int i=1;i<=m;i++) {
        cin>>op>>l>>r;
        if (op=='Q') {
            cnt++;
            q[++tot]=node{1,r,l,cnt,1};
            q[++tot]=node{1,l-1,l,cnt,-1};
        }
        else {
            q[++tot]=node{0,l,pri[l],0,-1};
            q[++tot]=node{0,l,pre(r,l),0,1};
            opt=nxt(a[l],l);
            if (opt) {
                q[++tot]=node{0,opt,pri[opt],0,-1};
                q[++tot]=node{0,opt,pre(a[l],l),0,1};
                pri[opt]=pre(a[l],l);
            }
            opt=nxt(r,l-1);
            if (opt) {
                q[++tot]=node{0,opt,pri[opt],0,-1};
                q[++tot]=node{0,opt,l,0,1};
                pri[opt]=l;
            }
            s[a[l]].erase(l);
            a[l]=r;
            s[a[l]].insert(l);
            pri[l]=pre(r,l);
        }
    }
    cdq(1,tot);
    for (int i=1;i<=cnt;i++) cout<<ans[i]<<"\n";
    return 0;
}
Ad-hoc CDQ分治 交互题 离线算法

评论（0）

查看评论列表

暂无评论

发表评论

表情 颜文字
插入代码
DRheEheAM_Gary Blog