文章导读

Feb. 1st 总结 | CDQ分治 (Chpt.1)

DRheEheAM_Gary 2026-02-01 40

每日 Ad-hoc

P11277 世界沉睡童话

~~谁家洛天依调这么好~~

观察到，若 $a_i=1$ ，则对于这个 $1$ ，后面的每个 $a_j\ (j\in (i,n])$ ，都能与这个 $1$ 组成一个对答案的贡献。

考虑从此处切入。
可以构造尽量多的 $1$ ，这样最优。

即为以下代码：

while (k>=n-1&&n>0) {
    cout<<"1 ";
    k-=n-1;
    n--;
}

while (k>=n-1&&n>0) {
    cout<<"1 ";
    k-=n-1;
    n--;
}

接下来，不难发现如下性质：

对于 $n\in \N$ ，对于 $i,j\in[n,2n)$ ， $\min(i,j)\ \nmid \ \max(i,j)$

所以可以从小到大枚举 $i\in\ [n,2n)$ ，计算其出现的最大次数

当 $i$ 出现 $c_i$ 次时，它对答案的贡献为

k_i=\frac{c_i(c_i-1)}{2}

最后计算

k = \sum k_i

所以不难看出，

\frac{c_i(c_i-1)}{2} \le k

所以，若

\frac{c_i(c_i-1)}{2} = k

，则：

\begin{aligned} \frac{c_i(c_i-1)}{2} &= k\\ c_i^2-c_i &= 2k \\ c_i^2-c_i-2k &=0 \\ c_i &= \frac{1\pm \sqrt{1+8k}}{2} \end{aligned}

因为总为整数，为保证性质，故：

c_i=\lfloor\frac{1+ \sqrt{1+8k}}{2} \rfloor

当 $k=0$ 但 $n \not = 0$ 时，继续向后构造，但每个数只出现一次，对答案无贡献。

这一部分的代码：

while (k>0&&n>0) {
    int x=(1+sqrt(1+8*k))/2;
    k-=x*(x-1)/2;
    n-=x;
    for (int i=1;i<=x;i++) cout<<nwt<<" ";
    nwt++;
}
while (n>0) cout<<nwt++<<" ",n--;

while (k>0&&n>0) {
    int x=(1+sqrt(1+8*k))/2;
    k-=x*(x-1)/2;
    n-=x;
    for (int i=1;i<=x;i++) cout<<nwt<<" ";
    nwt++;
}
while (n>0) cout<<nwt++<<" ",n--;

合起来就是这道题的解：

//hanser!!!!!!!
#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=2.5e5+10;
int n,k;
signed main() {
    Cios;
    cin>>n>>k;
    int nwt=n;
    while (k>=n-1&&n>0) {
        cout<<"1 ";
        k-=n-1;
        n--;
    }
    while (k>0&&n>0) {
        int x=(1+sqrt(1+8*k))/2;
        k-=x*(x-1)/2;
        n-=x;
        for (int i=1;i<=x;i++) cout<<nwt<<" ";
        nwt++;
    }
    while (n>0) cout<<nwt++<<" ",n--;
    return 0;
}

//hanser!!!!!!!
#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=2.5e5+10;
int n,k;
signed main() {
    Cios;
    cin>>n>>k;
    int nwt=n;
    while (k>=n-1&&n>0) {
        cout<<"1 ";
        k-=n-1;
        n--;
    }
    while (k>0&&n>0) {
        int x=(1+sqrt(1+8*k))/2;
        k-=x*(x-1)/2;
        n-=x;
        for (int i=1;i<=x;i++) cout<<nwt<<" ";
        nwt++;
    }
    while (n>0) cout<<nwt++<<" ",n--;
    return 0;
}

CDQ 分治

摘自 oi-wiki…

CDQ 分治是一种思想而不是具体的算法，与动态规划类似．目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

解决和点对有关的问题．

1D 动态规划的优化与转移．（未学习完）

通过 CDQ 分治，将一些动态问题转化为静态问题．（未学习）

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。（大佬orz）

接下来有道例题：

P3810 【模板】三维偏序 / 陌上花开

这题要我们求 $i,j\in[1,n]\ , \ a_i\le a_j \ ,\ b_i\le b_j\ , \ c_i\le c_j$ 的无序点对 $(i,j)$ 的数量。

考虑到我们写过的 P1908 逆序对，联想到归并排序解决二维偏序问题。

这就是 CDQ分治的主要思路。

对于第一维 $a_i$ ，进行排序。

对于第二维 $b_i$ 与第三维 $c_i$ ，分别使用归并排序与树状数组处理，并统计答案即可。

详细见代码，~~毕竟这是一道板子~~

//hanser!!!!!!!
#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=1e6+10;
int n,m,d[N];
struct node {
    int a,b,c,cnt,s;
    bool operator == (const node &p) const {
        return a==p.a&&b==p.b&&c==p.c;
    }
    static bool cmp1 (node p,node q) {
        if (p.a==q.a&&p.b==q.b) return p.c<q.c;
        if (p.a==q.a) return p.b<q.b;
        return p.a<q.a;
    }
    static bool cmp2 (node p,node q) {
        return p.b<q.b;
    }
}a[N];
class BIT {
    int tr[N<<1];
    int lowbit (int x) {return x&(-x);}
    public:
    void update (int x,int k) {
        while (x<=N<<1) {
            tr[x]+=k;
            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;
    while (i<=mid&&j<=r) {
        if (a[i].b<=a[j].b) bit.update(a[i].c,a[i].cnt),i++;
        else a[j].s+=bit.query(a[j].c),j++;
    }
    while (i<=mid) bit.update(a[i].c,a[i].cnt),i++;
    while (j<=r) a[j].s+=bit.query(a[j].c),j++;
    for (j=l;j<=mid;j++) bit.update(a[j].c,-a[j].cnt);
    sort(a+l,a+1+r,node::cmp2);
}
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i].a>>a[i].b>>a[i].c;
        a[i].cnt=1;
    }
    sort(a+1,a+1+n,node::cmp1);
    int t=1;
    for (int i=2;i<=n;i++) {
        if (a[t]==a[i]) a[t].cnt++;
        else a[++t]=a[i];
    }
    cdq(1,t);
    for (int i=1;i<=t;i++) d[a[i].s+a[i].cnt-1]+=a[i].cnt;
    for (int i=0;i<n;i++) cout<<d[i]<<"\n";
    return 0;
}

//hanser!!!!!!!
#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=1e6+10;
int n,m,d[N];
struct node {
    int a,b,c,cnt,s;
    bool operator == (const node &p) const {
        return a==p.a&&b==p.b&&c==p.c;
    }
    static bool cmp1 (node p,node q) {
        if (p.a==q.a&&p.b==q.b) return p.c<q.c;
        if (p.a==q.a) return p.b<q.b;
        return p.a<q.a;
    }
    static bool cmp2 (node p,node q) {
        return p.b<q.b;
    }
}a[N];
class BIT {
    int tr[N<<1];
    int lowbit (int x) {return x&(-x);}
    public:
    void update (int x,int k) {
        while (x<=N<<1) {
            tr[x]+=k;
            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;
    while (i<=mid&&j<=r) {
        if (a[i].b<=a[j].b) bit.update(a[i].c,a[i].cnt),i++;
        else a[j].s+=bit.query(a[j].c),j++;
    }
    while (i<=mid) bit.update(a[i].c,a[i].cnt),i++;
    while (j<=r) a[j].s+=bit.query(a[j].c),j++;
    for (j=l;j<=mid;j++) bit.update(a[j].c,-a[j].cnt);
    sort(a+l,a+1+r,node::cmp2);
}
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i].a>>a[i].b>>a[i].c;
        a[i].cnt=1;
    }
    sort(a+1,a+1+n,node::cmp1);
    int t=1;
    for (int i=2;i<=n;i++) {
        if (a[t]==a[i]) a[t].cnt++;
        else a[++t]=a[i];
    }
    cdq(1,t);
    for (int i=1;i<=t;i++) d[a[i].s+a[i].cnt-1]+=a[i].cnt;
    for (int i=0;i<n;i++) cout<<d[i]<<"\n";
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[填写昵称邮箱后可以评论]

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 1st 总结 | CDQ分治 (Chpt.1)

每日 Ad-hoc

P11277 世界沉睡童话

CDQ 分治

P3810 【模板】三维偏序 / 陌上花开

评论（0）

发表评论取消回复

插入代码

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 1st 总结 | CDQ分治 (Chpt.1)

每日 Ad-hoc

P11277 世界沉睡童话

CDQ 分治

P3810 【模板】三维偏序 / 陌上花开

评论（0）

发表评论 取消回复

插入代码

DRheEheAM_Gary Blog

发表评论取消回复