标签：线段树
题目
题目背景
Osu 听过没？那是Konano 最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司KONMAI 内工作，离他的梦想也越来越近了。
这款音乐游戏内一般都包含了许多歌曲，歌曲越多，玩家越不易玩腻。同时，为了使玩家在游戏上氪更多的金钱花更多的时间，游戏一开始一般都不会将所有曲目公开，有些曲目你需要通关某首特定歌曲才会解锁，而且越晚解锁的曲目难度越高。
题目描述
这一天，Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目 的解锁顺序。游戏内共有n 首曲目，每首曲目都会有一个难度d，游戏内第i 首曲目会在玩家Pass 第\(\lfloor \frac{i}{k} \rfloor\) 首曲目后解锁（\(\lfloor x \rfloor\) 为下取整符号）若\(\lfloor \frac{i}{k} \rfloor\) = 0，则说明这首曲目无需解锁
举个例子：当k = 2 时，第1 首曲目是无需解锁的（\(\lfloor \frac{1}{2} \rfloor\) = 0），第7 首曲目需要玩家Pass 第\(\lfloor \frac{7}{2} \rfloor\) = 3 首曲目才会被解锁。
Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个i 满足
\[d_i \geq d_{\lfloor \frac{i}{k} \rfloor}\]当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你，你会怎么解决这份任务呢？
输入输出格式
输入格式
从文件iiidx.in 中读入数据。
第1 行1 个正整数n 和1 个小数k，n 表示曲目数量，k 其含义如题所示。
第2 行n 个用空格隔开的正整数d，表示这n 首曲目的难度。
输出格式
输出到文件iiidx.out 中。
输出1 行n 个整数，按顺序输出安排完曲目顺序后第i 首曲目的难度。
若有多解，则输出d1 最大的；若仍有多解，则输出d2最大的，以此类推。
输入输出样例
输入样例#1
4 2.0
114 514 1919 810
输出样例#1
114 810 514 1919
说明
分析
题意可以抽象成：给出一棵树，使得树上每个节点的权值都小于其子树内点的权值，并使字典序最大
首先考虑\(d_i\)不相同的情况将权值从大到小排序，把长度为子树大小的一段按子树编号从小到大丢给它们，递归下去得到答案
将情况扩展，考虑\(d_i\)相同的做法
可以将编号x子树里一个大的权值与编号\(x+1\)的子树根的权值替换，使得x的权值依然是能取得的最大数且子树内的数都比x的权值大，同时\(x+1\)子树内的点也还能标满\(\geq x+1\)权值的权值
先把给定的权值从大到小排序，用线段树维护每个权值左边（包括自己）还能选取的权值的个数\(C_i\)
即每次取一个点x的权值时候，需要“预留”操作，在线段树上找到一个尽可能靠右的满足条件的\(C_i\geq size[x]\) 如果一个点有父亲，那么在查询的时候要把它父亲为子树预留的大小去掉（仅去掉一次即可），具体看代码实现
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define mid ((l+r)>>1)
#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=5e5+6,inf=1e9;
struct Seg_Tree{int mn,val;}tree[maxn<<2];
int n;double k;
int a[maxn],b[maxn],ans[maxn],size[maxn],fa[maxn],cnt[maxn];
inline bool cmp(int a,int b){return a>b;}
void pushup(int x){tree[x].mn=min(tree[lson].mn,tree[rson].mn);}
void pushdown(int x){
tree[lson].val+=tree[x].val;tree[lson].mn+=tree[x].val;
tree[rson].val+=tree[x].val;tree[rson].mn+=tree[x].val;
tree[x].val=0;
}
void build(int x,int l,int r){
if(l==r){tree[x].mn=l;return;}
build(lson,l,mid);build(rson,mid+1,r);
pushup(x);
}
inline int query(int x,int l,int r,int k){
if(l==r)return tree[x].mn>=k?l:l+1;
pushdown(x);
if(k<=tree[rson].mn)return query(lson,l,mid,k);
else return query(rson,mid+1,r,k);
}
void modify(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){tree[x].mn+=val;tree[x].val+=val;return;}
pushdown(x);
if(ql<=mid)modify(lson,l,mid,ql,qr,val);
if(qr>mid)modify(rson,mid+1,r,ql,qr,val);
pushup(x);
}
int main()
{
n=read();scanf("%lf",&k);
rep(i,1,n)a[i]=read();
sort(a+1,a+1+n,cmp);
dep(i,n-1,1)
if(a[i]==a[i+1])cnt[i]=cnt[i+1]+1;else cnt[i]=0;
rep(i,1,n)fa[i]=(int)floor(i/k),size[i]=1;
dep(i,n,1)size[fa[i]]+=size[i];
build(1,1,n);
rep(i,1,n){
if(fa[i]&&fa[i]!=fa[i-1])modify(1,1,n,ans[fa[i]],n,size[fa[i]]-1);
int x=query(1,1,n,size[i]);
x+=cnt[x];cnt[x]++;x-=(cnt[x]-1);ans[i]=x;
modify(1,1,n,x,n,-size[i]);
}
rep(i,1,n)printf("%d ",a[ans[i]]);
return 0;
}
