$n leq 500000$个数字，给实数$k$，问用这些数字填上的，满足$d_i geq d_{left lfloor frac{i}{k} ight floor}$的字典序最大的序列。
如果数字不同的话按后序遍历从大到小填就行了。
如果数字相同的话就不行。比如输入4 2 1 1 1 2。
预定。每选一个数，要预定几个比他大的数。首先从小到大排序。
方法零：线段树上维护每个数选了没选。在同一层的时候，每选一个数，就预定他左边紧贴着他的，他子树大小个数的数字。然后这层选完再把它还原回去。用个可持久化可以还原回去。难写。
方法一：线段树上维护每个数右边有几个数还没预定。每次找数需要找一个x，满足x左边的“未预定数”都大于等于x的子树大小，找权值尽量大的、同权值尽量靠左的数字选中。选完后，把它左边所有数的“未预定数”减去他的子树大小。决定一个点时取消它父亲的影响，注意只用取消一次。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 //#include<time.h> 5 //#include<complex> 6 //#include<queue> 7 #include<algorithm> 8 #include<stdlib.h> 9 using namespace std; 10 11 #define LL long long 12 int qread() 13 { 14 char c; int s=0; while ((c=getchar())<'0' || c>'9'); 15 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s; 16 } 17 18 //Pay attention to '-' , LL and double of qread!!!! 19 20 int n; double K; 21 #define maxn 500011 22 int num[maxn]; 23 struct Edge{int to,next;}edge[maxn]; int first[maxn],le=2; 24 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;} 25 26 int size[maxn]; 27 void dfs(int x) 28 { 29 size[x]=1; 30 for (int i=first[x];i;i=edge[i].next) 31 { 32 Edge &e=edge[i]; 33 dfs(e.to); size[x]+=size[e.to]; 34 } 35 } 36 37 struct SMT 38 { 39 struct Node{int ls,rs; int Min,add;}a[maxn<<1]; 40 int size,n; 41 void up(int x) {a[x].Min=min(a[a[x].ls].Min,a[a[x].rs].Min);} 42 void build(int &x,int L,int R) 43 { 44 x=++size; 45 if (L==R) {a[x].Min=n-L; return;} 46 int mid=(L+R)>>1; 47 build(a[x].ls,L,mid); build(a[x].rs,mid+1,R); 48 up(x); 49 } 50 void build(int m) {n=m; size=0; int x; build(x,1,n);} 51 52 void addsingle(int x,int v) {a[x].add+=v; a[x].Min+=v;} 53 void down(int x) {if (a[x].add) {addsingle(a[x].ls,a[x].add); addsingle(a[x].rs,a[x].add); a[x].add=0;}} 54 55 int ql,qr,v; 56 void Add(int x,int L,int R) 57 { 58 if (ql<=L && R<=qr) {addsingle(x,v); return;} 59 down(x); 60 int mid=(L+R)>>1; 61 if (ql<=mid) Add(a[x].ls,L,mid); 62 if (qr>mid) Add(a[x].rs,mid+1,R); 63 up(x); 64 } 65 void add(int L,int R,int v) {if (L>R) return; ql=L; qr=R; this->v=v; Add(1,1,n);} 66 67 int Query(int x,int L,int R) 68 { 69 if (L==R) return L; 70 down(x); 71 int mid=(L+R)>>1; 72 if (a[a[x].ls].Min>=v) return Query(a[x].rs,mid+1,R); 73 return Query(a[x].ls,L,mid); 74 } 75 int query(int val) {v=val; return Query(1,1,n);} 76 77 int Find(int x,int L,int R) 78 { 79 if (L==R) return L; 80 down(x); 81 int mid=(L+R)>>1; 82 if (num[mid]>=v) return Find(a[x].ls,L,mid); 83 return Find(a[x].rs,mid+1,R); 84 } 85 int find(int val) {v=val; return Find(1,1,n);} 86 87 }t; 88 89 int ans[maxn],fa[maxn]; 90 int main() 91 { 92 n=qread(); scanf("%lf",&K); 93 for (int i=1;i<=n;i++) num[i]=qread(); 94 95 fa[0]=-1; 96 for (int i=1;i<=n;i++) in(fa[i]=(int)(i/K+1e-9),i); 97 dfs(0); 98 99 sort(num+1,num+1+n); num[++n]=0x3f3f3f3f; 100 t.build(n); 101 for (int i=1;i<n;i++) 102 { 103 if (fa[i] && fa[i]!=fa[i-1]) t.add(1,ans[fa[i]],size[fa[i]]-1); 104 int val=num[t.query(size[i])-1]; int p=t.find(val); 105 ans[i]=p; t.add(1,ans[i],-size[i]); 106 } 107 108 for (int i=1;i<n;i++) printf("%d ",num[ans[i]]); 109 return 0; 110 }
方法二：看不太懂