题目大意：
一个游戏有$n(n\le5\times10^5)$个关卡，每个关卡有一个难度系数$d_i(d_i\le10^9)$。给定一个实数$k(k\le10^9)$，表示关卡$i$依赖于关卡$\lfloor\frac ik\rfloor$，即只有当关卡通过$\lfloor\frac ik\rfloor$后，关卡$i$才会被解锁。问如何排列这些难度系数，使得$d_i\ge d_{\lfloor\frac ik\rfloor}$？求字典序最大的方案。思路：
不难发现关卡间的依赖关系构成了一个树状结构。 对于$d_i$各不相同的情况，只存在唯一的一种方案，直接贪心即可，期望得分60分。 对于$d_i$相同的情况，用权值线段树维护大于当前难度值有多少未分配的难度值，从小到大枚举$1\sim n$号点，对于第$i$号结点，将当前未分配的第$size[i]$大的难度值分配给该结点即可。考虑如何操作才能使得$d_i$之后的难度值一定分配给$i$的子树。在操作完$i$结点后，可以将前$size[i]$大的难度值在线段树上标记为已分配，当访问到$i$的第一个子结点时，再恢复这些难度值并进行分配。1 #include2 #include 3 #include 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x;10 }11 const int N=5e5+1;12 const double eps=1e-8;13 double k;14 int n,d[N],size[N],ans[N],par[N],pos[N];15 class SegmentTree {16 #define _left <<117 #define _right <<1|118 private:19 int cnt[N<<2],tag[N<<2];20 void push_up(const int &p) {21 cnt[p]=std::min(cnt[p _left],cnt[p _right]);22 }23 void push_down(const int &p) {24 tag[p _left]+=tag[p];25 tag[p _right]+=tag[p];26 cnt[p _left]+=tag[p];27 cnt[p _right]+=tag[p];28 tag[p]=0;29 }30 public:31 void build(const int &p,const int &b,const int &e) {32 cnt[p]=n-e+1;33 if(b==e) return;34 const int mid=(b+e)>>1;35 build(p _left,b,mid);36 build(p _right,mid+1,e);37 }38 void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) {39 if(b==l&&e==r) {40 cnt[p]+=x;41 tag[p]+=x;42 return;43 }44 push_down(p);45 const int mid=(b+e)>>1;46 if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x);47 if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,x);48 push_up(p);49 }50 int query(const int &p,const int &b,const int &e,const int &k) {51 if(b==e) return cnt[p]>=k?b:b-1;52 push_down(p);53 const int mid=(b+e)>>1;54 return k<=cnt[p _left]?query(p _right,mid+1,e,k):query(p _left,b,mid,k);55 }56 #undef _left57 #undef _right58 };59 SegmentTree t;60 int main() {61 scanf("%d%lf",&n,&k);62 for(register int i=1;i<=n;i++) d[i]=getint();63 std::sort(&d[1],&d[n]+1);64 t.build(1,1,n);65 for(register int i=n;i;i--) {66 pos[std::lower_bound(&d[1],&d[n]+1,d[i])-&d[0]]=i;67 size[par[i]=i/k+eps]+=++size[i];68 }69 for(register int i=1;i<=n;i++) {70 if(par[i]&&par[i-1]!=par[i]) {71 t.modify(1,1,n,1,ans[par[i]],size[par[i]]-1);72 }73 ans[i]=pos[std::lower_bound(&d[1],&d[n]+1,d[t.query(1,1,n,size[i])])-&d[0]]++;74 printf("%d%c",d[ans[i]]," \n"[i==n]);75 t.modify(1,1,n,1,ans[i],-size[i]);76 }77 return 0;78 }