文章导读

Feb. 4th 总结 | CDQ 分治 (Chpt.4) & 珂朵莉树 ODT

DRheEheAM_Gary 2026-02-04 45

每日 Ad-hoc

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

这是一道~~奇妙的~~构造…

观察题面，我们发现两个特殊性质：

$m=n$
$m=2$

对于第一个，我们进行推广。
容易发现，当 $2m>n$ 时，即所有区间都有重合部分时，将 $n$ 放在中间一定最优。
代码如下：

if (m*2>n) {
    int cnt=1;
    while (cnt<=n/2) cout<<cnt++<<" ";
    cout<<n<<" ";
    while (cnt<n) cout<<cnt++<<" ";
    cout<<"\n";
}

if (m*2>n) {
    int cnt=1;
    while (cnt<=n/2) cout<<cnt++<<" ";
    cout<<n<<" ";
    while (cnt<n) cout<<cnt++<<" ";
    cout<<"\n";
}

对于第二个，我们研究后发现，
对于 $n$ 为奇数的情况，所有的排列答案恒为 $1$ 。
对于 $n$ 为偶数的情况，将每个 $[a_i,a_{i+1}]\ (i=1,3,5,…,n-1)$ 翻转变成 $[a_{i+1},a_i]$ 的排列最优，答案为 2。
代码如下：

else if (m==2) {
    if (n%2==1) {
        for (int i=1;i<=n;i++) cout<<i<<" ";
        cout<<"\n";
    }
    else {
        for (int i=1;i<=n;i++) {
            if (i%2==0) cout<<i-1<<" ";
            else cout<<i+1<<" ";
        }
        cout<<"\n";
    }
}

else if (m==2) {
    if (n%2==1) {
        for (int i=1;i<=n;i++) cout<<i<<" ";
        cout<<"\n";
    }
    else {
        for (int i=1;i<=n;i++) {
            if (i%2==0) cout<<i-1<<" ";
            else cout<<i+1<<" ";
        }
        cout<<"\n";
    }
}

从以上性质中，我们注意到以下性质：

对于给定的 $n,m$ ，最优答案为 $n$ 的所有因数中最大的，不大于 $\bold m$ 的因数

所以记答案为 $mx$ ，则对于所有的 $[mx,2mx,3mx,…,i\cdot mx,…,k\cdot mx]\ (k\cdot mx=n)$ ，填入这个数字并使其能够覆盖到最多区间，一定最优。

具体见代码实现：

%//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)
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        int n,m;
        cin>>n>>m;
        if (m*2>n) {
            int cnt=1;
            while (cnt<=n/2) cout<<cnt++<<" ";
            cout<<n<<" ";
            while (cnt<n) cout<<cnt++<<" ";
            cout<<"\n";
        }
        else {
            int mx=-1;
            for (int i=1;i<=m;i++) {
                if (n%i==0) mx=max(mx,i);
            }
            for (int i=1;i<=n/mx;i++) {
                for (int j=1;j<=mx;j++) cout<<(n/mx-i)*mx+j<<" ";
            }
            cout<<"\n";
        }
    }
    return 0;
}

%//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)
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        int n,m;
        cin>>n>>m;
        if (m*2>n) {
            int cnt=1;
            while (cnt<=n/2) cout<<cnt++<<" ";
            cout<<n<<" ";
            while (cnt<n) cout<<cnt++<<" ";
            cout<<"\n";
        }
        else {
            int mx=-1;
            for (int i=1;i<=m;i++) {
                if (n%i==0) mx=max(mx,i);
            }
            for (int i=1;i<=n/mx;i++) {
                for (int j=1;j<=mx;j++) cout<<(n/mx-i)*mx+j<<" ";
            }
            cout<<"\n";
        }
    }
    return 0;
}

CDQ 分治

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

无话可说…

所以顺便学习了一下 ODT （珂朵莉树）

ODT+CDQ 太强了…

珂朵莉树 / Old Driver Tree,ODT

~~一种存在于理论的数据结构~~
是一种解决颜色段均摊的数据结构

所以它的复杂度也是均摊复杂度…

看代码吧我不太想说…

//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)
#define itt set<node>::iterator
intc N=2e5+10;
int n,m,clcnt,qcnt,anscnt,a[N],pre[N],last[N],ans[N];
map <int,int> rf;
struct event {
    int pos,v,f,t,idx;
    event()=default;
    event(int _pos,int _v,int _f,int _t,int _idx) :pos(_pos),v(_v),f(_f),t(_t),idx(_idx) {}
}q[N*10];
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;
    }
    void clear(int x) {
        while (x<=n) {
            tr[x]=0;
            x+=lb(x);
        }
    }
}bit;
class ODT{
    struct node {
        int l,r;
        mutable int v;
        node ()=default;
        node (int _l,int _r=-1,int _v=0) :l(_l),r(_r),v(_v) {}
        bool operator < (const node &p) const {
            return l<p.l;
        }
    };
    set<node> tr;
    vector<set<node>> col;
    void ensure_col(int v) {
        if ((int)col.size()<=v) col.resize(v+1);
    }
    public:
    ODT() {
        col.reserve(1024);
    }
    itt insert (int l,int r,int v) {
        ensure_col(v);
        col[v].insert(node(l,r,v));
        return tr.insert(node(l,r,v)).first;
    }
    void erase (int l,int r,int v) {
        ensure_col(v);
        auto it2 = col[v].find(node(l,r,v));
        if (it2!=col[v].end()) col[v].erase(it2);
        tr.erase(node(l,r,v));
    }
    itt split (int x) {
        itt it=tr.lower_bound(node(x));
        if (it!=tr.end()&&it->l==x) return it;
        it=prev(it);
        int l=it->l,r=it->r,v=it->v;
        erase(l,r,v);
        insert(l,x-1,v);
        return insert(x,r,v);
    }
    int getprev (int p) {
        if (tr.empty()) return 0;
        auto ub = tr.upper_bound(node(p));
        if (ub==tr.begin()) return 0;
        itt it = prev(ub);
        if (it->l<p) return p-1;
        ensure_col(it->v);
        itt fd=col[it->v].lower_bound(node(p));
        if (fd!=col[it->v].begin()) return prev(fd)->r;
        else return 0;
    }
    void assign (int l,int r,int v,int t) {
        itt itr=split(r+1),itl=split(l);
        vector<int> vls;
        for (itt it=itl;it!=itr;it++) {
            if (it!=itl) vls.push_back(it->l);
            ensure_col(it->v);
            itt fd=col[it->v].upper_bound(*it);
            if (fd!=col[it->v].end()) vls.push_back(fd->l);
            auto it2 = col[it->v].find(*it);
            if (it2!=col[it->v].end()) col[it->v].erase(it2);
        }
        tr.erase(itl,itr);
        insert(l,r,v);
        vls.push_back(l);
        ensure_col(v);
        itt fd=col[v].upper_bound(node(l,r,v));
        if (fd!=col[v].end()) vls.push_back(fd->l);
        for (int vl:vls) {
            q[++qcnt]=event(vl,pre[vl],-1,t,-1);
            pre[vl]=getprev(vl);
            q[++qcnt]=event(vl,pre[vl],1,t,-1);
        }
    }
}odt;
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;
    for (int j=mid+1;j<=r;j++) {
        while (i<=mid&&q[i].pos<=q[j].pos) {
            if (q[i].idx==-1) bit.update(q[i].v+1,q[i].f);
            i++;
        }
        if (q[j].idx!=-1) ans[q[j].idx]+=bit.query(q[j].v+1)*q[j].f;
    }
    for (int k=l;k<i;k++) {
        if (q[k].idx==-1) bit.update(q[k].v+1,-q[k].f);
    }
    sort (q+l,q+r+1,[&](event a,event b) {
        if (a.pos!=b.pos) return a.pos<b.pos;
        return a.idx<b.idx;
    });
}
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        if (rf.count(a[i])==0) rf[a[i]]=++clcnt;
        a[i]=rf[a[i]];
        pre[i]=last[a[i]];
        last[a[i]]=i;
        q[++qcnt]=event(i,pre[i],1,0,-1);
        odt.insert(i,i,a[i]);
    }
    for (int i=1;i<=m;i++) {
        int op;
        cin>>op;
        if (op==1) {
            int l,r,v;
            cin>>l>>r>>v;
            if (rf.count(v)==0) rf[v]=++clcnt;
            v=rf[v];
            odt.assign(l,r,v,i);
        }
        else if (op==2) {
            int l,r;
            cin>>l>>r;
            anscnt++;
            q[++qcnt]=event(r,l-1,1,i,anscnt);
            q[++qcnt]=event(l-1,l-1,-1,i,anscnt);
        }
    }
    sort (q+1,q+1+qcnt,[&](event a,event b) {
        if (a.t!=b.t) return a.t<b.t;
        return a.idx<b.idx;
    });
    cdq(1,qcnt);
    for (int i=1;i<=anscnt;i++) cout<<ans[i]<<"\n";
    return 0;
}

//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)
#define itt set<node>::iterator
intc N=2e5+10;
int n,m,clcnt,qcnt,anscnt,a[N],pre[N],last[N],ans[N];
map <int,int> rf;
struct event {
    int pos,v,f,t,idx;
    event()=default;
    event(int _pos,int _v,int _f,int _t,int _idx) :pos(_pos),v(_v),f(_f),t(_t),idx(_idx) {}
}q[N*10];
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;
    }
    void clear(int x) {
        while (x<=n) {
            tr[x]=0;
            x+=lb(x);
        }
    }
}bit;
class ODT{
    struct node {
        int l,r;
        mutable int v;
        node ()=default;
        node (int _l,int _r=-1,int _v=0) :l(_l),r(_r),v(_v) {}
        bool operator < (const node &p) const {
            return l<p.l;
        }
    };
    set<node> tr;
    vector<set<node>> col;
    void ensure_col(int v) {
        if ((int)col.size()<=v) col.resize(v+1);
    }
    public:
    ODT() {
        col.reserve(1024);
    }
    itt insert (int l,int r,int v) {
        ensure_col(v);
        col[v].insert(node(l,r,v));
        return tr.insert(node(l,r,v)).first;
    }
    void erase (int l,int r,int v) {
        ensure_col(v);
        auto it2 = col[v].find(node(l,r,v));
        if (it2!=col[v].end()) col[v].erase(it2);
        tr.erase(node(l,r,v));
    }
    itt split (int x) {
        itt it=tr.lower_bound(node(x));
        if (it!=tr.end()&&it->l==x) return it;
        it=prev(it);
        int l=it->l,r=it->r,v=it->v;
        erase(l,r,v);
        insert(l,x-1,v);
        return insert(x,r,v);
    }
    int getprev (int p) {
        if (tr.empty()) return 0;
        auto ub = tr.upper_bound(node(p));
        if (ub==tr.begin()) return 0;
        itt it = prev(ub);
        if (it->l<p) return p-1;
        ensure_col(it->v);
        itt fd=col[it->v].lower_bound(node(p));
        if (fd!=col[it->v].begin()) return prev(fd)->r;
        else return 0;
    }
    void assign (int l,int r,int v,int t) {
        itt itr=split(r+1),itl=split(l);
        vector<int> vls;
        for (itt it=itl;it!=itr;it++) {
            if (it!=itl) vls.push_back(it->l);
            ensure_col(it->v);
            itt fd=col[it->v].upper_bound(*it);
            if (fd!=col[it->v].end()) vls.push_back(fd->l);
            auto it2 = col[it->v].find(*it);
            if (it2!=col[it->v].end()) col[it->v].erase(it2);
        }
        tr.erase(itl,itr);
        insert(l,r,v);
        vls.push_back(l);
        ensure_col(v);
        itt fd=col[v].upper_bound(node(l,r,v));
        if (fd!=col[v].end()) vls.push_back(fd->l);
        for (int vl:vls) {
            q[++qcnt]=event(vl,pre[vl],-1,t,-1);
            pre[vl]=getprev(vl);
            q[++qcnt]=event(vl,pre[vl],1,t,-1);
        }
    }
}odt;
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;
    for (int j=mid+1;j<=r;j++) {
        while (i<=mid&&q[i].pos<=q[j].pos) {
            if (q[i].idx==-1) bit.update(q[i].v+1,q[i].f);
            i++;
        }
        if (q[j].idx!=-1) ans[q[j].idx]+=bit.query(q[j].v+1)*q[j].f;
    }
    for (int k=l;k<i;k++) {
        if (q[k].idx==-1) bit.update(q[k].v+1,-q[k].f);
    }
    sort (q+l,q+r+1,[&](event a,event b) {
        if (a.pos!=b.pos) return a.pos<b.pos;
        return a.idx<b.idx;
    });
}
signed main() {
    Cios;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
        if (rf.count(a[i])==0) rf[a[i]]=++clcnt;
        a[i]=rf[a[i]];
        pre[i]=last[a[i]];
        last[a[i]]=i;
        q[++qcnt]=event(i,pre[i],1,0,-1);
        odt.insert(i,i,a[i]);
    }
    for (int i=1;i<=m;i++) {
        int op;
        cin>>op;
        if (op==1) {
            int l,r,v;
            cin>>l>>r>>v;
            if (rf.count(v)==0) rf[v]=++clcnt;
            v=rf[v];
            odt.assign(l,r,v,i);
        }
        else if (op==2) {
            int l,r;
            cin>>l>>r;
            anscnt++;
            q[++qcnt]=event(r,l-1,1,i,anscnt);
            q[++qcnt]=event(l-1,l-1,-1,i,anscnt);
        }
    }
    sort (q+1,q+1+qcnt,[&](event a,event b) {
        if (a.t!=b.t) return a.t<b.t;
        return a.idx<b.idx;
    });
    cdq(1,qcnt);
    for (int i=1;i<=anscnt;i++) cout<<ans[i]<<"\n";
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

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

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 4th 总结 | CDQ 分治 (Chpt.4) & 珂朵莉树 ODT

每日 Ad-hoc

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

CDQ 分治

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

珂朵莉树 / Old Driver Tree,ODT

评论（0）

发表评论取消回复

插入代码

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 4th 总结 | CDQ 分治 (Chpt.4) & 珂朵莉树 ODT

每日 Ad-hoc

P11132 【MX-X5-T4】「GFOI Round 1」epitaxy

CDQ 分治

P4690 [Ynoi Easy Round 2016] 镜中的昆虫

珂朵莉树 / Old Driver Tree,ODT

评论（0）

发表评论 取消回复

插入代码

DRheEheAM_Gary Blog

发表评论取消回复