洛谷 4364 [九省联考2018]IIIDX

【题解】

　　一眼可以想到一个类似二叉树后序遍历的贪心做法，然而这个做法在有相同数字的情况下是错误的。最简单的反例就是n=4,d={1,1,1,2}，正解是1,1,2,1，而贪心是1,1,1,2. 所以这个贪心被叉掉了。

　　我们先把d从大到小排序，然后我们用f[i]表示第i个位置之前（包括i位置）还能取的数的个数。第一个节点显然去第size[1]大的数字就好，如果有多个相等的，那么就取最右边的，因为这可以为后面的节点预留更大的数。当取好一个点的值之后，需要给它的子树预留数字；我们并不能确定子树中的每个节点分别取什么值，但是我们知道子树取的数字一定大于当前节点的数值，所以子树取的值一定在当前节点的数字前面。我们只需要把当前位置及其右边的f[i]减去size即可。每次需要确定一个节点i的取值时，我们只需要找到最大的数值val满足val所在位置右边的c[j]都大于size[i]，如果有多个相等的val，我们还是取最右边的那个。要找到这样的val，我们在线段树上二分就可以了。

　　需要注意的是，在计算到某个父亲的第一个孩子时，我们需要把父亲预留的位置加回来。

 #include<cstdio>

 #include<algorithm>

 #define N 500010

 #define rg register

 #define ls (u<<1)

 #define rs (u<<1|1)

 using namespace std;

 int n,m,d[N],siz[N],pos[N],cnt[N];

 double k;

 struct tree{

     int l,r,del,mn;

 }a[N<<];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 inline int min(int x,int y){return x<y?x:y;}

 inline bool cmp(int x,int y){return x>y;}

 void build(int u,int l,int r){

     a[u].l=l; a[u].r=r; int mid=(l+r)>>;

     if(l<r) build(ls,l,mid),build(rs,mid+,r),a[u].mn=min(a[ls].mn,a[rs].mn);

     else a[u].mn=l;

 }

 inline void pushdown(int u){

     int d=a[u].del; a[u].del=;

     a[ls].del+=d; a[rs].del+=d;

     a[ls].mn+=d; a[rs].mn+=d;

 }

 void update(int u,int l,int d){

     if(l<=a[u].l){

         a[u].mn+=d; a[u].del+=d; return;

     }

     if(a[u].del) pushdown(u);

     update(rs,l,d);

     if(l<=((a[u].l+a[u].r)>>)) update(ls,l,d);

     a[u].mn=min(a[ls].mn,a[rs].mn);

 }

 int find(int u,int l,int r,int v) {

     if (l==r) {

         if (a[u].mn>=v) return l; return l+;

     }

     if (a[u].del) pushdown(u);

     int mid=(l+r)>>;

     if (a[rs].mn>=v) return find(ls,l,mid,v);

     return find(rs,mid+,r,v);

 }

 int fa(int x) {return x/k;}

 int main(){

     n=read(); scanf("%lf",&k); build(,,n);

     for(rg int i=;i<=n;i++) d[i]=read();

     sort(d+,d++n,cmp);

     for(rg int i=n-;i;i--) if(d[i]==d[i+]) cnt[i]=cnt[i+]+;

     for(rg int i=n;i;i--) siz[fa(i)]+=++siz[i];

     for(rg int i=;i<=n;i++){

         if(fa(i)&&fa(i)!=fa(i-)) update(,pos[fa(i)],siz[fa(i)]-);

         pos[i]=find(,,n,siz[i]); pos[i]+=cnt[pos[i]]; pos[i]-=cnt[pos[i]]++;

         update(,pos[i],-siz[i]);

     }

     for(rg int i=;i<=n;i++) printf("%d ",d[pos[i]]);

     return ;

 }

巴特西

洛谷 4364 [九省联考2018]IIIDX

最新文章

热门文章