题意：给你一个序列，求对于任意i，都有$a_i\ge a_{\lfloor \frac{i}{k} \rfloor}$的字典序最大的序列

 

1、30分暴力（对于当时连dfs都不会的我最多也就只能拿这些分了QAQ）

　  枚举全排列判断（真TM暴力）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define int long long#define olinr return#define _ 0#define love_nmr 0#define DB doubleinline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}inline void put(int x){ if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0');}int n;double k;int a[505050];int ans[505050];signed main(){ n=read(); scanf("%lf",&k); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); do { for(int i=1;i<=n;i++) if(a[i]
           
          
         
        
       
      

2、60分贪心（WA）

　   对于多个$i$，他们的$\lfloor \frac{i}{k} \rfloor$可能是相同的

　　很容易（?）可以想到树,

　　以$\lfloor \frac{i}{k} \rfloor$作为父亲，而前者相同的作为儿子　　

　　那么我们只需保证对于所有的点，儿子的点权小于等于父亲的点权即可了

　　开一个大根堆存入每一个数

　　从小到大连边（先遍历序号小的点）

　　一旦到叶子就弹出堆顶赋值

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define int long long#define olinr return#define _ 0#define love_nmr 0#define DB doubleinline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}inline void put(int x){ if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0');}int n;double k;int ans[505050];priority_queue
             
              q;struct node{ int to; node *nxt;};typedef node* nod;nod head[505050];int root;inline void add(int from,int to){ nod t=new node(); t->to=to; t->nxt=head[from]; head[from]=t;}inline void dfs(int x){ for(nod i=head[x];i!=NULL;i=i->nxt) dfs(i->to); if(x!=root) ans[x]=q.top(),q.pop();}signed main(){ n=read(); scanf("%lf",&k); for(int i=1;i<=n;i++) q.push(read()); root=n+1; for(int i=n;i;i--) //链式前向星要倒着！！！ { int fa=(double)i/k; if(!fa) fa=root; add(fa,i); } dfs(root); for(int i=1;i<=n;i++) put(ans[i]),putchar(' '); olinr ~~(0^_^0)+love_nmr;}
             
            
           
          
         
        
       
      

3、正解：线段树？？？？？？？？？

　　首先说为什么贪心是错的

　　比如一个序列1 2 1 1

　　贪心的结果是1 1 1 2，而正解是1 1 2 1

　　额，貌似处理不了元素重复的情况（怪不得WA）

　　那么应该怎么处理呢?

　　1、将所有元素从大到小排序

　　2、处理size（子树大小）和一个cnt（维护每个相同的数最右的位置）

　　　　（貌似跟线段树沾不上边啊QAQ）

　　3、从1--n依次取点，对于i,给子树留下size[i]-1个点

　　　  定义f[i]为i左边（包括自己）最多还能放多少点，那么f一定是单调不递减的

　　　　所以可以用线段树维护f，区间的最小值

　　　栗子：9 9 9 8 8 7 7 6 6 6 5（已经sort好了）

　　　　　　我们假设当前size[i]=8　　

　　　　　　找到一个最靠左的位置（字典序最大QAQ）使得有7个数大于等于它

　　　　　　因此我们找到了pos=8的6，然后让pos+=cnt把pos=10的6给它

　　　　　　这样可以留出更多的数给后面的点用，保证i最优的同时尽量使与i同层的点更优

　　　　　　为什么呢？

　　　　　　因为我们这棵树，对于i，同层的点的编号一定是小于i子树内点的编号的，

　　　　　　所以，要想最优，我们要保证的是同层的而不是子树！！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define int long long#define olinr return#define _ 0#define love_nmr 0#define DB doubleinline int read(){    int x=0,f=1;    char ch=getchar();    while(!isdigit(ch))    {        if(ch=='-')            f=-f;        ch=getchar();    }    while(isdigit(ch))    {        x=(x<<1)+(x<<3)+(ch^48);        ch=getchar();    }    return x*f;}inline void put(int x){    if(x<0)    {        x=-x;        putchar('-');    }    if(x>9)        put(x/10);    putchar(x%10+'0');}int n;double k;struct node{    int val;    int tag;    int l;    int r;    node *ls;    node *rs;};typedef node* nod;int a[505050];int ans[505050];int siz[505050];int fa[505050];bool vis[505050];int cnt[505050];inline bool cmp(int a,int b){    return a>b;}inline void update(nod now){    now->val=min(now->ls->val,now->rs->val);}inline void build(nod now,int l,int r){    now->l=l;    now->r=r;    now->tag=0;    if(l==r)    {        now->val=l;  //初始啥也没选        return;    }    now->ls=new node();    now->rs=new node();    int mid=(l+r)>>1;    build(now->ls,l,mid);    build(now->rs,mid+1,r);    update(now);}inline void push_down(nod now){    if(now->tag)    {        now->ls->tag+=now->tag;        now->rs->tag+=now->tag;        now->ls->val+=now->tag;        now->rs->val+=now->tag;        now->tag=0;    }}inline void lazy(nod now,int x,int y,int k){    if(now->l>y||now->r
           
            l&&now->r<=y) { now->tag+=k; now->val+=k; return; } push_down(now); lazy(now->ls,x,y,k); lazy(now->rs,x,y,k); update(now);}inline int query(nod now,int k){ if(now->l==now->r) return now->val>=k? now->l:now->l+1; //在底下的if中rs==x时我们也是往左边选的 可能会漏掉最小值在相邻的右区间这种情况所以在这里判一下 push_down(now); if(k>now->rs->val) //尽量往左 return query(now->rs,k); return query(now->ls,k);}signed main(){ n=read(); scanf("%lf",&k); for(int i=1;i<=n;i++) a[i]=read(),siz[i]=1; //节点初始siz sort(a+1,a+n+1,cmp); //从大到小排序 nod root=new node(); build(root,1,n); //建树 for(int i=n;i>=1;i--) { cnt[i]=a[i]==a[i+1]? cnt[i+1]+1:0; //处理cnt数组 fa[i]=(double)i/k; siz[fa[i]]+=siz[i]; //注意求siz一定要倒着枚举！！ } for(int i=1;i<=n;i++) { if(fa[i]&&!vis[fa[i]]) //fa只退回一遍（释放预留的空间，因为当前在遍历它的孩子） { lazy(root,ans[fa[i]],n,siz[fa[i]]-1); vis[fa[i]]=true; } int now=query(root,siz[i]); //求出最左位置 now+=cnt[now]; //往后推 cnt[now]++; //当前位置选择，指针往右移动，下次如果右找到了这里，就到下一个点 ans[i]=now; //记录答案（下标） lazy(root,ans[i],n,-siz[i]); //给它的孩子预留空间 } for(int i=1;i<=n;i++) put(a[ans[i]]),putchar(' '); olinr ~~(0^_^0)+love_nmr;}