Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P4556 【[Vani有约会]雨天的尾巴】

posted on 2019-05-17 19:19:02 | under 题解 |

分享一个不写任何数据结构就能++过去的方法。


原理同线段树合并解法,可以移步其它大佬题解。

这里讲一下怎么不写线段树合并过这道题。

可以发现在线段树合并解法中,我们需要维护的信息其实是一个二元组(种类,数量),放到线段树上,就是(位置,值),而位置在线段树上固定了下来,所以在子节点维护值,上层阶点维护最大的值和对应的位置。然后卡一卡空间就好了。

但是对于(位置,值)这个二元组,换用平衡树维护显然也是完全可以的,而且空间复杂度要更优。

写平衡树是不可能的,能不写平衡树就不写平衡树的,只有用stl才能水题的样子,里面的东西都超好用的,我超喜欢stl的。

问题是stl里的平衡树显然没法拓展,那么我们怎么用它维护答案呢。

stl的map可以很方便的维护(位置,值)这个二元组,却不支持根据第二维维护答案。

其实我们用线段树的话,是可以查出任意(l,r)的答案的,不过这道题只需要(1,n)的答案。

那有没有什么只能查出(1,n)的答案,代码更简单的写法呢。

假如现在有了所有的二元组(位置,值),且没有相同的值,那么只需要按照第二维进行排序。

如果有相同的值,那只要让第二维升序,第二维相同时第一维降序,排序后最大的一个就是答案了。

然后我们需要让这个有序序列带修,所以用set维护。

现在总结一下,就有实现思路了:

  1. map维护(位置,值)二元组

  2. set维护(值,位置)二元组,即set维护map的翻转

  3. 当修改一个值的时候,map中查找到位置对应的二元组,在set中删除翻转后的二元组,修改map的二元组,在set中插入翻转的新二元组。

至于合并,就是标准的启发式合并。

所以这题可以出成noip题。

时间复杂度大概O(nlog^2n)的样子。

吸口氧就过了。

跑的和我吸氧的线段树合并差不多,都在4300ms左右。(均为树剖lca)

倍增lca+stl代码:(倍增短一些)

#include <cstdio>
#include <map> 
#include <vector>
#include <set>
using namespace std;
const int kmaxn=100000+5;
const int kmaxlog=20;
vector<int> head[kmaxn];
int n,m;
int lg[kmaxn];
int fa[kmaxn][kmaxlog];
int dep[kmaxn];
void init()
{
    for(int i=1;i<=n;++i)
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
}
void dfs(int now,int f)
{
    dep[now]=dep[(fa[now][0]=f)]+1;
    for(int i=1;i<lg[dep[now]];++i)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    vector<int>& e=head[now];
    for(int t=0,len=e.size();t<len;++t)
        if(e[t]!=f)dfs(e[t],now);
}
inline int lca(int a,int b)
{
    if(dep[a]<dep[b])swap(a,b);
    while(dep[a]>dep[b])
        a=fa[a][lg[dep[a]-dep[b]]-1];
    if(a==b)return a;
    for(int i=lg[dep[a]]-1;i>=0;--i)
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
struct unit
{
    int a,b;
    unit(int _a=0,int _b=0):a(_a),b(_b){}
    const bool operator<(const unit& u)const{return a==u.a?b>u.b:a<u.a;}
};
class data_struct
{
    public:
        map<int,int> mp;
        map<int,int>::iterator itr;
        set<unit> st;
        inline void add(int pos,int k)
        {
            itr=mp.insert(make_pair(pos,0)).first;
            if(itr->second!=0)
                st.erase(unit(itr->second,itr->first));
            itr->second+=k;
            if(itr->second!=0)
                st.insert(unit(itr->second,itr->first));
            else
                mp.erase(itr);
        }
        void _merge(map<int,int>& tmp,set<unit>& tst,map<int,int>::iterator t)
        {
            if(tmp.size()>mp.size()){
                swap(tmp,mp);
                swap(tst,st);
            }
            t=tmp.begin();
            while(t!=tmp.end()){
                add(t->first,t->second);
                ++t;
            }
            tmp.clear();
            tst.clear();
        }
        inline void merge(data_struct& ds){_merge(ds.mp,ds.st,ds.itr);}
}trees[kmaxn];
inline void mod(int x,int y,int z)
{
    trees[x].add(z,1);
    trees[y].add(z,1);
    int a=lca(x,y);
    trees[a].add(z,-1);
    trees[fa[a][0]].add(z,-1);
}
void solve(int now)
{
    vector<int> &e=head[now];
    int t=0,len=e.size();
    while(t<len){
        if(e[t]!=fa[now][0]){
            solve(e[t]);
            trees[now].merge(trees[e[t]]);
        }
        ++t;
    }
    if(trees[now].st.empty())
        dep[now]=0;
    else
        dep[now]=(--trees[now].st.end())->b;
}
int a,b,c;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        head[a].push_back(b);
        head[b].push_back(a); 
    }
    init();
    dfs(1,0);
    while(m--){
        scanf("%d%d%d",&a,&b,&c);
        mod(a,b,c);
    }
    solve(1);
    for(int i=0;i<=n;)
        printf("%d\n",dep[i++]);
    return 0;
}

众所周知set和map不是数据结构【大误

也分享一个普通的的线段树合并做法。

#include <cstdio>
#include <vector>
using namespace std;
enum SONS
{
    ls,rs
};
class node;
class autoptr
{
    static node* bpos;
    public:
    int offset;
    inline node& operator*();
    inline node* operator->();
    inline const autoptr& operator=(const autoptr& a)
    {
        offset=a.offset;
        return *this;
    }
    inline const autoptr& operator=(const int o)
    {
        offset=o;
        return *this;
    }
    inline operator node*()const;
    inline operator bool()const
    {
        return offset;
    }
    inline operator int()const
    {
        return offset;
    }
};
class node
{
    public:
        int v;
        int pos;
        autoptr son[2];
        node()
        {
            v=0;
            son[ls]=son[rs]=0;
        }
        inline void clear()
        {
            v=0;
            son[ls]=son[rs]=0;
        }
        inline void update()
        {
            v=0;
            if(!(son[ls]||son[rs]))
                return;
            if(!son[ls]||!son[rs])
            {
                pos=son[(bool)son[rs]]->pos;
                v=son[(bool)son[rs]]->v;
            }
            else
            {
                bool dir=!(son[ls]->v>=son[rs]->v);
                v=son[dir]->v;
                pos=son[dir]->pos;
            }
        }
};
inline node& autoptr::operator*()
{
    return *(bpos+offset);
}
inline node* autoptr::operator->()
{
    return (bpos+offset);
}
inline autoptr::operator node*()const
{
    return bpos+offset;
}
const int kmaxpool=100000*50;
int npt;
node mpool[kmaxpool];
node* autoptr::bpos=mpool;
inline int alloc_node()
{
    return ++npt;
}
const int kmaxz=100000+5;
class segment_tree
{
    static const int L,R;
    public:
    autoptr root;
    autoptr _merge(int l,int r,autoptr a,autoptr b)
    {
        if(!a||!b)
            return a?a:b;
        if(l==r)
        {
            a->v+=b->v;
            return a;
        }
        int mid=(l+r)>>1;
        a->son[ls]=_merge(l,mid,a->son[ls],b->son[ls]);
        a->son[rs]=_merge(mid+1,r,a->son[rs],b->son[rs]);
        a->update();
        return a;
    }
    segment_tree merge(segment_tree& st)
    {
        root=_merge(L,R,root,st.root);
        return *this;
    }
    void _add(int l,int r,int pos,int k,autoptr& p)//add
    {
        if(!p)
            p=alloc_node();
        if(l==r)
        {
            p->v+=k;
            p->pos=l;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)
            r=mid;
        else
            l=mid+1;
        _add(l,r,pos,k,p->son[pos>mid]);
        p->update();
    }
    void add(int pos,int k)
    {
        _add(L,R,pos,k,root);
    }
};
const int segment_tree::L=1;
const int segment_tree::R=kmaxz;
struct edge
{
    int d;
    edge *nt;
};
const int kmaxn=100000+5;
vector<int> head[kmaxn];
void add_edge(int s,int d)
{
    head[s].push_back(d);
}
int top[kmaxn],fa[kmaxn],dep[kmaxn],hs[kmaxn],size[kmaxn];
void dfs1(int now,int f)
{
    fa[now]=f;
    dep[now]=dep[f]+1;
    size[now]=1;
    vector<int> &e=head[now];
    int t=0,len=e.size();
    int ms=0;
    while(t<len)
    {
        if(e[t]!=f)
        {
            dfs1(e[t],now);
            size[now]+=size[e[t]];
            if(size[e[t]]>size[ms])
                ms=e[t];
        }
        ++t;
    }
    hs[now]=ms;
}
void dfs2(int now,int tp)
{
    top[now]=tp;
    if(!hs[now])return;
    dfs2(hs[now],tp);
    vector<int> &e=head[now];
    int t=0,len=e.size();
    while(t<len)
    {
        if(e[t]!=hs[now]&&e[t]!=fa[now])
            dfs2(e[t],e[t]);
        ++t;
    }
}
inline int lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]])
            swap(a,b);
        a=fa[top[a]];
    }
    return dep[a]<dep[b]?a:b;
}
segment_tree trees[kmaxn];
inline void mod(int x,int y,int z)
{
    trees[x].add(z,1);
    trees[y].add(z,1);
    int a=lca(x,y);
    trees[a].add(z,-1);
    trees[fa[a]].add(z,-1);
}
void solve(int now)
{
    vector<int> &e=head[now];
    int t=0,len=e.size();
    while(t<len)
    {
        if(e[t]!=fa[now])
        {
            solve(e[t]);
            trees[now].merge(trees[e[t]]);
        }
        ++t;
    }
    if(trees[now].root&&trees[now].root->v>0)
        hs[now]=trees[now].root->pos;
    else
        hs[now]=0;
}
int n,m;
int a,b,c;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs1(1,0);
    dfs2(1,1);
    ++m;
    while(--m)
    {
        scanf("%d%d%d",&a,&b,&c);
        mod(a,b,c);
    }
    solve(1);
    for(int i=0;i<=n;)
    {
        printf("%d\n",hs[i++]);
    }
    return 0;
}

线段树指针被卡内存了所以写了个autoptr

然而哪里auto了