Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5290 【[十二省联考2019]春节十二响】

posted on 2019-04-08 17:23:02 | under 题解 |

D2唯一看懂的题

而且考场上没看懂为啥1可能不是链端点

大力观察题意,这题可以贪心,直接合并子节点的priority_queue,上界n^2logn,虽然上界很松,还是怂了。

可以发现两个序列合并后,序列依然是有序的,没有必要用排序,所以可以直接用vector维护。

然后随机数据考场电脑随便跑

然后就没写启发式合并变成60分

加上启发式合并就过了QAQ。。。。

下面是比较暴力的vector做法:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define reg register
typedef long long vt;
const int kmaxn=200000+5;
struct edge
{
    int d;
    edge* nxt;
};
edge mempool[kmaxn];
int mpt;
edge* head[kmaxn];
void add_edge(int s,int d)
{
    mempool[mpt].nxt=head[s];
    head[s]=&mempool[mpt++];
    head[s]->d=d;
}
vector<vt> q[kmaxn];
vt value[kmaxn];
int pos[kmaxn]; 
void merge(int& a,int& b)
{
    if(a==0)
    {
        a=b;
        return;
    }
    if(q[a].size()<q[b].size())
    {
        swap(a,b);
    }
    vt t=0;
    reg int i=0,L=min(q[a].size(),q[b].size());
    for(i=0;i<L;++i)
    {
        t=max(q[a][i],q[b][i]);
        q[a][i]=t;
    }
    for(L=q[b].size();i<L;++i)
    {
        q[a].push_back(q[b][i]);
    }
    vector<vt> vec;
    swap(vec,q[b]);
}
int lb(int num)
{
    vt v=value[num];
    num=pos[num];
    reg int l=0,r=q[num].size();
    reg int mid=0,ans=0;
    if(q[num].empty()||q[num][0]<=v)
        return 0;
    else if(q[num].back()>v)
        return r;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(q[num][mid]<=v)
        {
            r=mid;
            ans=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return ans;
}
void dfs(int now)
{
    edge* t=head[now];
    while(t)
    {
        dfs(t->d);
        merge(pos[now],pos[t->d]);
        t=t->nxt;
    }
    if(!head[now])
    {
        pos[now]=now;
    }
   /* reg int p=pos[now];
    for(reg int i=0,j=q[p].size();i<j;++i)
    {
        if(q[p][i]<=value[now])
        {
            q[p].insert(q[p].begin()+i,value[now]);
            return;
        }
    }
    q[p].push_back(value[now]);*///链会超时
    q[pos[now]].insert(q[pos[now]].begin()+lb(now),value[now]);
}
int n;
int fa;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(reg int i=1;i<=n;++i){
        cin>>value[i];
    }
    for(reg int i=2;i<=n;++i)
    {
        cin>>fa;
        add_edge(fa,i);
    }
    dfs(1);
    vt ans=0;
    for(reg int i=q[pos[1]].size()-1;i>=0;--i)
    {
        ans+=q[pos[1]][i];
    }
    cout<<ans<<endl;
    return 0;
}

vector做法依然可以卡,因为对序列插入每个节点权值时,上界依旧是n,不过平衡树中序遍历+启发式合并就卡不掉了

但是vector能过写什么平衡树

依旧偷懒,记吃不记打