并不对劲的复健训练-bzoj5249:loj2472:p4364[2018多省联考]IIIDX

心已赠人 2023-08-17 16:46 13阅读 0赞

##### 题目大意 #####

给出\\(n,k,d\_1,...,d\_n\\)(\\(n\\leq 5\\times 10^5,1<k\\leq 10^9,d\\leq 10^9,k\\in R\\))。有一个满足 对于每个点\\(i\\)它的父亲是\\(\\lfloor\\frac\{i\}\{d\}\\rfloor\\)（若为0则没父亲）的森林，将\\(d\_1,...,d\_n\\)分配给森林中的每个点，设第\\(i\\)号点分配的权值为\\(w\_i\\)，满足\\(w\_i\\)不超过子树中所有点的点权，且使\\(w\_1\\)尽量大，\\(w\_1\\)相同时使\\(w\_2\\)尽量大……以此类推。

##### 题解 #####

###### subtask 1/2：\\(d\\)互不相同，55pts ######

先将\\(d\\)从大到小排序，把树建出来，设点\\(i\\)的字数大小为\\(siz\_i\\)。  
从1号点考虑：\\(w\_1\\)越大越好，而有\\(siz\_1\\)个\\(w\\)是必须大于等于\\(w\_1\\)的，那么\\(w\_1\\)取\\(d\_\{siz\_1\}\\)最好。  
考虑完一号点之后，发现一号点子树里的点只能取\\(d\_i,i\\in\[1,siz\_1-1\]\\)。  
就可以对于每个点维护\\(\[l\_i,r\_i\]\\)表示当前这个点的子树中的点只能在该区间中取。  
每考虑一个点\\(x\\)，就令\\(w\_x=d\_\{l\_\{fa\_x\}+siz\_x-1\}\\)，并将\\(\[l\_x,r\_x\]\\)更新为\\(\[l\_\{fa\_x\},l\_\{fa\_x\}+siz\_x-2\]\\)，将\\(\[l\_\{fa\_x\},r\_\{fa\_x\}\]\\)更新为\\(\[l\_\{fa\_x\}+siz\_x,r\_\{fa\_x\}\]\\)。

###### subtask 2/2：无特殊限制，45pts ######

发现上一个subtask的方法的问题在于，当\\(d\\)排序后长成“!!!!!@@@@@\#\#”（相同的符号表示相同的数）时，如果 \\(siz\_1=7\\)，那么分配给1号点的子树的数就是“!!!!!@@”，如果2号点不在1号点的子树中，把“!!@@@@@”给1号点的子树，2号点就有机会分到“!”。  
也就是说，这个时候考虑每一个点时，选的位置应满足：1.左边的可用的数的个数大于等于\\(siz\_i\\)；2.在去重后的序列中尽可能靠左；3.在同色段中尽可能靠右。  
这时还有一个小问题：因为选的点在同色段中尽可能靠右，所以它左边可用的数的个数可能会大于\\(siz\_i\\)，这个时候不好规定它的子树中的点具体取哪个区间（或哪些）数。  
但是可以把它转化成一些形如“对于\\(i\\in\[1,x\]\\)，有\\(siz\_p\\)个\\(d\\)已经被取了”的事件，和形如“求还可以取\\(siz\_q\\)个的、在去重后的序列中最靠左、在同色段中最靠右的位置”的询问。  
可以维护\\(a\_j\\)表示对于\\(i\\in\[1,j\]\\)还有\\(a\_j\\)个\\(d\_i\\)没有被取。  
对于一个“事件”，\\(j\\in\[x,n\]\\)的部分肯定都有\\(a\_j-=siz\_p\\)。  
另一部分之所以难求，是因为不知道具体取了哪\\(siz\_p\\)个数。这部分可以这样处理：按编号从小到大考虑每个点，这样先考虑的点一定比后考虑的点更需要更大的\\(d\\)。这样这部分的\\(a\_j\\)就变成了“当每个事件都尽可能往后取时，对于\\(i\\in\[1,j\]\\)还有\\(a\_j\\)个\\(d\_i\\)没有被取”。记每个事件只处理\\(j\\in\[x,n\]\\)得到的数为\\(a'\_j\\)，那么就有\\(a\_j=min\\\{a‘\_c|c\\in\[j,n\]\\\}\\)。  
直接维护\\(a\\)很麻烦，考虑维护\\(a'\\)：这样每个查询就变成了求最靠前的不少于\\(siz\_q\\)后缀最小值，可以在线段树上二分；每个事件就变成了把\\(\[x,n\]\\)区间减\\(siz\_p\\)。  
还要注意一个小问题：考虑到一个点时，应将它父亲为它父亲的子树留出的（不包括它父亲本身）部分去掉，即将\\(\[x,n\]\\)加\\(siz\_p-1\\)。这样也不用担心考虑别的子树时算到这部分，因为点\\(i\\)的父亲是\\(\\lfloor\\frac\{i\}\{d\}\\rfloor\\)，所以同层（即父亲相同）的点是连着考虑的，在考虑到别的子树中的点时已经把这部分又减回去了。

##### 代码 #####

##### 一些感想 #####

上面有一句话是“这时还有一个小问题：因为选的点在同色段中尽可能靠右，所以它左边可用的数的个数可能会大于\\(siz\_i\\)，这个时候不好规定它的子树中的点具体取哪个区间（或哪些）数。”  
然而在做题的时候只想到了上面举的例子和样例，就觉得应该把\\(i\\)子树中的数无脑选为可选范围内最大的一段。  
于是就用平衡树维护安排给每个点的数，每考虑一个点，就是从它的父亲中先找出第\\(siz\_i\\)大的数，然后找一个数\\(d\_x\\)使\\(d\_x\\)在\\(fa\_i\\)中，且\\(fa\_i\\)的平衡树中在区间\\(\[第siz\_i大的数,d\_x\]\\)的个数大于\\(siz\_i\\)，且\\(d\_x\\)尽可能小。  
然后把\\(fa\_i\\)的平衡树在\\(\[第siz\_i大的数,d\_x\]\\)这个区间的数都给\\(i\\)的平衡树，注意\\(d\_x\\)有多个时可能只需要给一部分。  
令\\(w\_i=\\)点\\(i\\)平衡树中最大的数，并从平衡树中删掉这个数。  
这样并不是正确的，因为当\\(d\\)排序后一部分为“!!!!!@@@@@”时，如果\\(siz\_1=6,siz\_2=4\\)，分给1的子树的是“!@@@@@”，分给2的子树的是“!!!!”，那么\\(w\_1=\\)@,\\(w\_2=\\)!，但是如果把“!!@@@@”给1号点的子树，“!!!@”给2号点的子树，就能有\\(w\_1=\\)@,\\(w\_2=\\)@。  
不过先留着代码吧，万一哪天出题用上了？

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(int i=(x);i>=(y);--i)
    #define maxn 500007
    #define maxm 1000007
    #define D double
    #define ls son[u][0]
    #define rs son[u][1]
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar(' ');return;}int f=0;char ch[20];if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;while(f)putchar(ch[f--]);putchar(' ');return;
    }
    D K;
    int n,d[maxn],sz[maxn],now,anc[maxn];
    int son[maxm][2],fa[maxm],cntnd,siz[maxm],key[maxm],num[maxm],rt[maxm];
    void pu(int u){if(!u)return;siz[u]=num[u];if(ls)siz[u]+=siz[ls];if(rs)siz[u]+=siz[rs];}
    int getso(int u){return son[fa[u]][0]!=u;}
    void rot(int u)
    {
        int fu=fa[u],ffu=fa[fu],l=getso(u),fl=getso(fu),r=l^1,rson=son[u][r];
        son[u][r]=fu,son[fu][l]=rson;if(ffu)son[ffu][fl]=u;if(rson)fa[rson]=fu;fa[fu]=u,fa[u]=ffu;
        pu(fu),pu(u);
    }
    void splay(int u,int k,int & root)
    {
        while(fa[u]!=k){if(fa[fa[u]]!=k)rot(getso(u)^getso(fa[u])?u:fa[u]);rot(u);}
        if(!k)root=u;
    }
    void fnd(int k,int & root)
    {
        int u=root;
        while(k!=key[u]&&son[u][k>key[u]])u=son[u][k>key[u]];
        splay(u,0,root);
    }
    int nxt(int k,int f,int & root)
    {
        fnd(k,root);int u=root;
        if((key[u]<k&&!f)||(key[u]>k&&f))return u;
        u=son[u][f];if(!u)return u;
        while(son[u][f^1])u=son[u][f^1];
        return u;
    }
    int build(int l,int r)
    {
        int u=l+r>>1;
        if(l<=u-1)ls=build(l,u-1),fa[ls]=u;
        if(r>=u+1)rs=build(u+1,r),fa[rs]=u;
        pu(u);return u;
    }
    int getp(int k,int & root)
    {
        int u=root;
        while(son[u][1])u=son[u][1];
        splay(u,0,root);
        while(1)
        {
            if(siz[rs]>=k)u=rs;
            else if(siz[rs]+num[u]<k)k-=siz[rs]+num[u],u=ls;
            else {/*cout<<"p:"<<u<<endl;*/return u;}
        }
        return -1;
    }
    int getrt(int k,int & root)
    {
        int u=getp(k,root),lk=nxt(key[u],0,root),tpk=k;
        //cout<<"lk:"<<lk<<endl;
        if(lk)splay(lk,0,root),u=son[lk][1];
        else u=root;//cout<<u<<endl;
        while(1)
        {
            if(siz[ls]>=k)u=ls;
            else if(siz[ls]+num[u]<k)k-=siz[ls]+num[u],u=rs;
            else break;
        }
        splay(u,lk,root);k=tpk;
        if(siz[ls]+num[u]==k)
        {
            if(rs)fa[rs]=lk;if(lk)son[lk][1]=rs;else root=rs;
            fa[u]=0,rs=0;
            pu(u),pu(lk);
            return u;
        }
        int res=ls;ls=0;
        int nu=++cntnd;key[nu]=key[u],num[nu]=k-siz[res],num[u]-=k-siz[res],son[nu][key[res]>key[nu]]=res;if(res)fa[res]=nu;
        pu(nu),pu(u);if(lk)pu(lk);
        return nu;
    }
    int del(int & root)
    {
        int u=root;
        while(son[u][0])u=son[u][0];
        splay(u,0,root);
        if(num[u]==1)root=rs,fa[rs]=0;
        else num[u]--,pu(u);
        return key[u];
    }
    int main()
    {
        scanf("%d%lf",&n,&K);
        rep(i,1,n)d[i]=read();
        sort(d+1,d+n+1);int now=0;
        rep(i,1,n)
        {
            now++;
            if(i==n||d[i]!=d[i+1])cntnd++,key[cntnd]=d[i],num[cntnd]=now,now=0;
        }
        rt[0]=build(1,cntnd);
        rep(i,1,n)anc[i]=(D)i/K;
        dwn(i,n,1)sz[i]++,sz[anc[i]]+=sz[i];
        rep(i,1,n)
        {
            rt[i]=getrt(sz[i],rt[anc[i]]);
            write(del(rt[i]));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/xzyf/p/11579830.html