UOJ Logo skip2004的博客

博客

十二省联考D2T2 spring 奇怪做法

2019-04-08 18:10:44 By skip2004

讲道理我是看错题了才有这个做法(还不知道对不对,希望UOJ神仙帮我证明一下正确性或者hack掉)

我看错的题面是这样的:

对于每一条到根的链,将其上每个点的权值重新排列后至少存在一种方案可以分别塞到不同的内存段之中(我这样每个点在选取的链不同时中位置可以不同)

然后就有一个显然的多项式暴力,把每条链拉出来再排序贪心

然后我发现贪心中最重要的是包含这个点的链上最多有几个点比这个数大

然后我就把每个节点按权值从大到小排序之后一个个插入,树状数组维护到根的和来查询到根有几个数比自己大,Lct维护到叶子的链最长是多长,然后就知道最多几个数比自己大了

放考场代码(考场modify完忘splay了,下面是已经加上的):

#include<iostream>
#include<algorithm>
const int maxn = 200200;
int son[maxn][2],sum[maxn],v[maxn],fa[maxn];
inline void up(int & x,int y){if(x<y)x=y;}
inline int get(int x,int p=1){return son[fa[x]][p]==x;}
inline int is_root(int x){return !(get(x,1)||get(x,0));}
inline void up(int x){
    sum[x]=sum[son[x][0]]+sum[son[x][1]]+v[x];
}
inline void rotate(int x){
    int y=fa[x],z=fa[y],b=get(x);
    if(!is_root(y))son[z][get(y)]=x;
    son[y][b]=son[x][!b],son[x][!b]=y;
    fa[son[y][b]]=y,fa[y]=x,fa[x]=z;
    up(y);
}
inline void splay(int x){
    for(;!is_root(x);rotate(x))
        if(!is_root(fa[x]))rotate(get(x)^get(fa[x])?x:fa[x]);
    up(x);
}
inline void mdf(int x){
    splay(x),v[x]=1,up(x);
    for(;x;){
        if(fa[x])splay(fa[x]);
        else break;
        if(sum[x] <= sum[son[fa[x]][1]])break;
        son[fa[x]][1]=x,x=fa[x],up(x);
    }
}
inline int query(int x){
    splay(x);
    return sum[son[x][1]];
}
int n;
int M[maxn],rk[maxn];
int a[maxn];
int dep[maxn],dp=1;
struct T{
    int to,nxt;
}way[maxn<<1];
int h[maxn],num;
inline void adde(int x,int y){
    way[++num]={y,h[x]},h[x]=num;
    way[++num]={x,h[y]},h[y]=num;
}
int dfn[maxn],size[maxn],tot;
inline void dfs(int x){
    size[x]=1,dfn[x]=++tot;
    for(int i=h[x];i;i=way[i].nxt)if(!size[way[i].to])dfs(way[i].to),size[x]+=size[way[i].to];
}
int ta[maxn];
inline void add(int x,int v){
    while(x<maxn)
        ta[x] += v,x += x & -x;
}
inline int query2(int x){
    int ans=0;
    while(x)ans+=ta[x],x&=x-1;
    return ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(0);
    std::cin >> n;
    for(int i=1;i<=n;++i)std::cin >> M[i],rk[i]=i;
    dep[1]=1;
    for(int i=2;i<=n;++i)std::cin >> fa[i],up(dp,dep[i]=dep[fa[i]]+1),adde(i,fa[i]);
    std::sort(rk+1,rk+n+1,[](const int&a,const int&b){return M[a]>M[b];});
    dfs(1);
    for(int t=1,i,j;t<=n;){
        j=i=t;
        while(M[rk[j+1]]==M[rk[i]])++j;
        for(int k=i;k<=j;++k)mdf(rk[k]),splay(rk[k]),add(dfn[rk[k]],1),add(dfn[rk[k]]+size[rk[k]],-1);
        for(int k=i;k<=j;++k)up(a[query2(dfn[rk[k]])+query(rk[k])],M[rk[k]]);
        t=j+1;
    }
    long long ans=0;
    for(int i=dp;i>=1;--i)up(a[i],a[i+1]),ans+=a[i];
    std::cout << ans << '\n';
}

评论

mrsrz
orz
AprilGrimoire
这个做法是对的。 考虑这个算法把某个$M_i$作为第$k$大的段的条件: 把所有消耗内存大于等于它的点染黑,从根到某个点的路径上存在至少$k$个黑点,并且之前的所有点都不满足这个性质。 可以发现这个东西就是刚才的线段树做法的$g(1)$。 所以这个线段树做法也告诉我们不管每个点所属的段是不是固定的都没关系。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。