初见 | 数据结构 | ODT

2023-11-18 15:53:07

「启」

  • 关于为啥我要学这个？

    • 闲的。

本篇中所有 Code 的缺省源使用 「V5.2」.

「关于 ODT」

  • ODT 用处？

    • （大多数是）在有区间赋值操作的 DS 题里面骗分，因为好像专门为 ODT 设计的题不多吧？反正我只知道 CF896C.

  • 时间复杂度？

    • ODT 的复杂度正确建立在数据随机上，这点一定牢记。

    • 对于所有的基础操作（如 \(Assign\) 和 \(Add\) 等），使用 set 实现的 ODT 的复杂度为 \(O(n \log\log n)\)，而链表实现的复杂度为 \(O(n \log n)\)，不过我目前只会用 set 实现就是了（

  • 注意事项？

    • ODT 的复杂度正确建立在数据随机上，ODT 的复杂度正确建立在数据随机上，ODT 的复杂度正确建立在数据随机上。不然的话出题人很容易构造数据让你 T 掉。

    • 别被没有区间赋值的部分分卡了。

「实现」

先是核心思想：把值相同的区间合并成结点，存到 set 里面。

于是就有了以下的结构体来存结点：

「结点 Node」

struct Node
{
    LL l,r;
    mutable LL v;

    Node(LL l,LL r=0,LL v=0) : l(l),r(r),v(v) {}

    I bool operator < (const Node &co) const
    {
        Heriko l<co.l;
    }
};

set<Node> s;

这里的 mutable 是为了突破 const 的限制，便于我们后面直接修改 set 中的值，而不是拿出来改完再扔进去。

「分裂 Split」

\(Split\) 算是 ODT 中最重要的操作了，简单来说就是把区间 \([l,r]\) 分成 \([l,pos-1]\) 和 \([pos,r]\) 两段，便于我们操作。

实现也很简单，我们先用 set 自带的 lower_bound 确定 \(pos\) 对应位置，然后删除原区间分成两半插入。

I auto Split(LL pos)
{
    auto it(s.lower_bound(Node(pos)));

    if(it!=s.end() and it->l==pos)
        Heriko it;

    --it;

    if(it->r<pos)
        Heriko s.end();

    LL l(it->l),r(it->r),v(it->v);
    s.erase(it);
    s.insert(Node(l,pos-1,v));

    Heriko s.insert(Node(pos,r,v)).first;
}

这样的话所有的区间 \([l,r]\) 上的操作都可以转化为 \([Split(l),Split(r+1)].\)

「推平 Assign」

\(Assign\) 也是很重要操作，主要就是完成缩点的任务，实现起来也很简单，找到区间之后删除插入新的就行。

I void Assign(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));
    s.erase(itl,itr);
    s.insert(Node(l,r,x));
}

实际上最基本的操作也就上面这俩了，下面再扩展一点常用的操作。

「区间加 Add」

如何区间加呐？暴力。

嗯，没错就是暴力，找到对应区间之后暴力加就是了（

I void Add(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));

    for(auto it(itl);it!=itr;++it)
        it->v+=x;
}

「排名 Rank」

查询区间排名的话，我们先声明一个结构体或者 pair 便于对相同的数操作。

struct Rank
{
    LL val,cnt;

    Rank(LL val,LL cnt) : val(val),cnt(cnt) {}

    I bool operator < (const Rank &co) const
    {
        Heriko val<co.val;
    }
};

然后我们就用最好想的思路，先找到对应区间，然后把所有的数排序，直接去找要求排名即可。

I LL QueryRank(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));
    vector<Rank> v;
    
    for(auto it(itl);it!=itr;++it)
        v.push_back(Rank(it->v,it->r-it->l+1));

    sort(v.begin(),v.end());
    LL i(0);

    for(;i<(LL)v.size();++i)
        if(v[i].cnt<x)
            x-=v[i].cnt;
        else
            Heriko v[i].val;

    Heriko v[i].val;
}

「其它 Other」

其实观察上面的也能发现在 ODT 上的操作，先找到对应区间之后就很好办了，所有大概的代码框架都是这个样子：

I auto Function(int l,int r,...)
{
    auto itr(Split(r+1)),itl(Split(l));
    
    ...
}

然后知道了这些就可以去把 CF896C 干掉了。

「CF896C Code」


CI MXX(1e5+1),MOD(1e9+7);

LL n,m,seed,vmax,a[MXX];

I LL GetData()
{
    LL res(seed);
    seed=(seed*7+13)%MOD;

    Heriko res;
}

I LL FstPow(LL x,LL y,LL p)
{
    LL res(1);
    x%=p;

    while(y)
    {
        if(y&1)
            (res*=x)%=p;

        (x*=x)%=p;
        y>>=1;
    }

    Heriko res;
}

struct Node
{
    LL l,r;
    mutable LL v;

    Node(LL l,LL r=0,LL v=0) : l(l),r(r),v(v) {}

    I bool operator < (const Node &co) const
    {
        Heriko l<co.l;
    }
};

set<Node> s;

I auto Split(LL pos)
{
    auto it(s.lower_bound(Node(pos)));

    if(it!=s.end() and it->l==pos)
        Heriko it;

    --it;

    if(it->r<pos)
        Heriko s.end();

    LL l(it->l),r(it->r),v(it->v);
    s.erase(it);
    s.insert(Node(l,pos-1,v));

    Heriko s.insert(Node(pos,r,v)).first;
}

I void Assign(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));
    s.erase(itl,itr);
    s.insert(Node(l,r,x));
}

I void Add(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));

    for(auto it(itl);it!=itr;++it)
        it->v+=x;
}

struct Rank
{
    LL val,cnt;

    Rank(LL val,LL cnt) : val(val),cnt(cnt) {}

    I bool operator < (const Rank &co) const
    {
        Heriko val<co.val;
    }
};

I LL QueryRank(LL l,LL r,LL x)
{
    auto itr(Split(r+1)),itl(Split(l));
    vector<Rank> v;
    
    for(auto it(itl);it!=itr;++it)
        v.push_back(Rank(it->v,it->r-it->l+1));

    sort(v.begin(),v.end());
    LL i(0);

    for(;i<(LL)v.size();++i)
        if(v[i].cnt<x)
            x-=v[i].cnt;
        else
            Heriko v[i].val;

    Heriko v[i].val;
}

I LL QueryVal(LL l,LL r,LL x,LL y)
{
    auto itr(Split(r+1)),itl(Split(l));
    LL res(0);
    
    for(auto it(itl);it!=itr;++it)
        res=(res+FstPow(it->v,x,y)*(it->r-it->l+1)%y)%y;

    Heriko res;
}

S main()
{
    Files();

    fr(n),fr(m),fr(seed),fr(vmax);

    for(int i(1);i<=n;++i)
        a[i]=(GetData()%vmax)+1,s.insert(Node(i,i,a[i]));

    while(m--)
    {
        LL opt((GetData()%4)+1),l((GetData()%n)+1),r((GetData()%n)+1),x,y;

        if(l>r)
            swap(l,r);

        if(opt==3)
            x=(GetData()%(r-l+1))+1;
        else
            x=(GetData()%vmax)+1;

        if(opt==4)    
            y=(GetData()%vmax)+1;

        if(opt==1)
            Add(l,r,x);
        else if(opt==2)
            Assign(l,r,x);
        else if(opt==3)
            fw(QueryRank(l,r,x),1);
        else
            fw(QueryVal(l,r,x,y),1);
    }

    Heriko Deltana;
}

「其它例题」

调了三天 CF896C 最后发现是快速幂少了 x%=p 之后就做了一点简单 ODT 板子题。

「HAOI2014 贴海报」

这个题巨大显然了吧，贼板子吧。

只需要区间推平，最后开个桶记录一下就行了，直接切了对吧。

CI MXX(1001);

struct Node
{
    int l,r;
    mutable int val;

    Node(int l,int r=0,int val=0) : l(l),r(r),val(val) {}

    I bool operator < (const Node &co) const
    {
        Heriko l<co.l;
    }
};

set<Node> s;

I auto Split(int pos)
{
    auto it(s.lower_bound(Node(pos)));

    if(it!=s.end() and it->l==pos)
        Heriko it;

    --it;

    if(it->r<pos)
        Heriko s.end();

    int l(it->l),r(it->r),v(it->val);
    s.erase(it);
    s.insert(Node(l,pos-1,v));

    Heriko s.insert(Node(pos,r,v)).first;
}

I void Assign(int l,int r,int v)
{
    auto itr(Split(r+1)),itl(Split(l));
    s.erase(itl,itr);
    s.insert(Node(l,r,v));
}

int n,m,x,y,tot,ans(-1);

bitset<MXX> vis;

S main()
{
    Files();

    fr(n),fr(m);
    s.insert(Node(1,n+1));

    while(m--)
        fr(x),fr(y),Assign(x,y,++tot);

    for(auto it(s.begin());it!=s.end();++it)
        if(!vis[it->val])
            ++ans,vis[it->val]=1;

    fw(ans,1);

    Heriko Deltana;
}

「CF343D Water Tree」

这个题是个树上问题，比较板的树剖（

不过我们不写线段树，我们直接上 ODT，在两边 DFS 处理出来 id 序之后按照普通的序列操作即可。

第二个操作就需要我们在 DFS 的时候记录一下 top，修改的时候不断跳 top 进行 \(Assign\) 即可。

CI MXX(5e5+5);

struct ODT
{
    int l,r;
    mutable int v;

    ODT(int l,int r=0,int v=0) : l(l),r(r),v(v) {}

    I bool operator < (const ODT &co) const
    {
        Heriko l<co.l;
    }
};

set<ODT> s;

I auto Split(int pos)
{
    auto it(s.lower_bound(ODT(pos)));

    if(it!=s.end() and it->l==pos)
        Heriko it;

    --it;

    if(it->r<pos)
        Heriko s.end();

    int l(it->l),r(it->r),val(it->v);
    s.erase(it);
    s.insert(ODT(l,pos-1,val));
    
    Heriko s.insert(ODT(pos,r,val)).first;
}

I void Assign(int l,int r,int x)
{
    auto itr(Split(r+1)),itl(Split(l));
    s.erase(itl,itr);
    s.insert(ODT(l,r,x));
}

struct Node
{
    int nex,to;
}

r[MXX<<1];

int rcnt,head[MXX];

I void Add(int x,int y)
{
    r[++rcnt]=(Node){head[x],y},head[x]=rcnt;
    r[++rcnt]=(Node){head[y],x},head[y]=rcnt;
}

int n,m,sz[MXX],dep[MXX],id[MXX],top[MXX],fa[MXX],son[MXX],tot;

void DFS1(int x,int fath)
{
    sz[x]=1,fa[x]=fath,dep[x]=dep[fath]+1;

    for(int i(head[x]);i;i=r[i].nex)
    {
        int y(r[i].to);

        if(y==fath)
            continue;

        DFS1(y,x);
        sz[x]+=sz[y];

        if(sz[y]>sz[son[x]])
            son[x]=y;
    }
}

void DFS2(int x,int tp)
{
    top[x]=tp,id[x]=++tot;

    if(son[x])
        DFS2(son[x],tp);

    for(int i(head[x]);i;i=r[i].nex)
    {
        int y(r[i].to);

        if(y==fa[x] or y==son[x])
            continue;

        DFS2(y,y);
    }
}

I void ModifyZero(int x)
{
    int tp(top[x]);

    while(tp!=1)
    {
        Assign(id[tp],id[x],0);
        x=fa[tp],tp=top[x];
    }

    Assign(id[1],id[x],0);
}

S main()
{
    Files();

    fr(n);

    for(int i(1);i<n;++i)
    {
        int x,y;
        fr(x),fr(y);
        Add(x,y);
    }

    DFS1(1,0);
    DFS2(1,1);
    s.insert(ODT(0,MXX));
    fr(m);

    while(m--)
    {
        int opt,x;
        fr(opt),fr(x);

        if(opt==1)
            Assign(id[x],id[x]+sz[x]-1,1);
        else if(opt==2)
            ModifyZero(x);
        else
            fw(Split(id[x])->v,1);
    }

    Heriko Deltana;
}

「终」

那么就写这些吧。

上一篇：JZ56 数组中只出现一次的两个数字


下一篇：【并发编程】支持按优先级排序的*阻塞队列PriorityBlockingQueue