网页qq登录保护怎么关,网站推广优化联系方式,义乌外贸网站建设行吗,网站没做好可以备案吗传送门 题解看得……很……迷#xff1f; 因为取完一个数后#xff0c;它的子树中只能取权值小于等于它的数。我们先把权值从大到小排序#xff0c;然后记$a_i$为他左边#xff08;包括自己#xff09;所有取完他还能取的数的个数。那么当取完一个点$x$的数之后#xff0…传送门 题解看得……很……迷 因为取完一个数后它的子树中只能取权值小于等于它的数。我们先把权值从大到小排序然后记$a_i$为他左边包括自己所有取完他还能取的数的个数。那么当取完一个点$x$的数之后我们需要为它子树中的点预留出权值这些权值肯定在它的左边。但我们不知道它子树中的数会取哪几个数所以我们就把$x$及其右边的数的$a_i$全都减去$x$的子树大小$size_x$那么就代表$x$的左边有这么多位置被占据了。那么某一个点$y$要取值的时候我们只要在线段树上找到最左边的一个点满足它右边包括自己所有的$a_i$都大于等于当前子树的$size$即可这个在线段树上二分就可以了 然后要注意父亲给他们预留出了权值那么在做到儿子的时候把这些预留的空间取出来也就是把上面的影响消除。父亲只给儿子预留了一次空间所以消除影响也只需要一次就够了 1 //minamoto2 #includebits/stdc.h3 using namespace std;4 inline int read(){5 #define num ch-06 char ch;bool flag0;int res;7 while(!isdigit(chgetchar()))8 (ch-)(flagtrue);9 for(resnum;isdigit(chgetchar());resres*10num);
10 (flag)(res-res);
11 #undef num
12 return res;
13 }
14 const int N5e55;
15 int mn[N2],tag[N2];
16 int n;double k;
17 int a[N],ans[N],sz[N],fa[N],cnt[N];
18 inline bool cmp(int a,int b){return ab;}
19 #define ls (p1)
20 #define rs (p1|1)
21 inline void upd(int p){mn[p]min(mn[ls],mn[rs]);}
22 inline void ppd(int p,int t){mn[p]t,tag[p]t;}
23 inline void pd(int p){ppd(ls,tag[p]),ppd(rs,tag[p]),tag[p]0;}
24 void build(int p,int l,int r){
25 if(lr) return (void)(mn[p]l);
26 int mid(lr)1;
27 build(ls,l,mid),build(rs,mid1,r),upd(p);
28 }
29 int query(int p,int l,int r,int k){
30 if(lr) return mn[p]k?l:l1;
31 int mid(lr)1;if(tag[p]) pd(p);
32 return kmn[rs]?query(ls,l,mid,k):query(rs,mid1,r,k);
33 }
34 void update(int p,int l,int r,int ql,int qr,int k){
35 if(qllqrr) return (void)(ppd(p,k));
36 int mid(lr)1;if(tag[p]) pd(p);
37 if(qlmid) update(ls,l,mid,ql,qr,k);
38 if(qrmid) update(rs,mid1,r,ql,qr,k);
39 upd(p);
40 }
41 int main(){
42 // freopen(testdata.in,r,stdin);
43 nread();scanf(%lf,k);
44 for(int i1;in;i) a[i]read();
45 sort(a1,a1n,cmp);
46 for(int in-1;i;--i)
47 cnt[i]a[i]a[i1]?cnt[i1]1:0;
48 for(int i1;in;i) fa[i](int)(i/k),sz[i]1;
49 for(int in;i;--i) sz[fa[i]]sz[i];
50 build(1,1,n);
51 for(int i1;in;i){
52 if(fa[i]fa[i]!fa[i-1]) update(1,1,n,ans[fa[i]],n,sz[fa[i]]-1);
53 int xquery(1,1,n,sz[i]);
54 xcnt[x],cnt[x],x-(cnt[x]-1);ans[i]x;
55 update(1,1,n,x,n,-sz[i]);
56 }
57 for(int i1;in;i) printf(%d ,a[ans[i]]);
58 return 0;
59 } 转载于:https://www.cnblogs.com/bztMinamoto/p/9807441.html
