题解 P4556 【[Vani有约会]雨天的尾巴】
_虹_
2019-05-17 19:19:02
分享一个**不写任何数据结构**就能++过去的方法。
------------
原理同线段树合并解法，可以移步其它大佬题解。
这里讲一下怎么不写线段树合并过这道题。
可以发现在线段树合并解法中，我们需要维护的信息其实是一个二元组(**种类，数量**)，放到线段树上，就是(**位置，值**)，而位置在线段树上固定了下来，所以在子节点维护值，上层阶点维护最大的值和对应的位置。~~然后卡一卡空间就好了。~~
但是对于（**位置，值**）这个二元组，换用平衡树维护显然也是完全可以的，而且空间复杂度要更优。
~~写平衡树是不可能的，能不写平衡树就不写平衡树的，只有用stl才能水题的样子，里面的东西都超好用的，我超喜欢stl的。~~
问题是stl里的平衡树显然没法拓展，那么我们怎么用它维护答案呢。
stl的map可以很方便的维护(**位置,值**)这个二元组，却不支持根据第二维维护答案。
其实我们用线段树的话，是可以查出任意(l,r)的答案的，不过这道题只需要(1,n)的答案。
那有没有什么只能查出(1,n)的答案，代码更简单的写法呢。
假如现在有了所有的二元组(**位置，值**)，且没有相同的值，那么只需要按照第二维进行排序。
如果有相同的值，那只要让第二维升序，第二维相同时第一维降序，排序后最大的一个就是答案了。
然后我们需要让这个有序序列带修，所以用set维护。
现在总结一下，就有实现思路了：
1. map维护（位置，值）二元组
1. set维护（值，位置）二元组，即set维护map的翻转
1. 当修改一个值的时候，map中查找到位置对应的二元组，在set中删除翻转后的二元组，修改map的二元组，在set中插入翻转的新二元组。
至于合并，就是标准的启发式合并。
~~所以这题可以出成noip题。~~
时间复杂度大概O(nlog^2n)的样子。
~~吸口氧就过了。~~
跑的和我吸氧的线段树合并差不多，都在4300ms左右。（均为树剖lca）
## 倍增lca+stl代码：（倍增短一些）
```cpp
#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不是数据结构【大误~~
## 也分享一个普通的的线段树合并做法。
```cpp
#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了~~