Desription 给你n个数。现在你可以选择若干个数（也可以一个都不选），选择的价值为所有数的价值和。现在给所有可能的选择，先按权值从小到大排序，对于权值相同的，根据所用数字集合的标号的字典序从小到大排序。请输出第k小的选择的价值，以及所用的选择集合。
Sample Input 4 10 3 7 4 3
Sample Output 10 1 3 4
这题卡长卡了我一上午。。。 首先我们如果按照DFS的思想，每一次对于一个数，我们要么选，要么不选，但这样是肯定会T的，我们需要一些想法。 如果我希望使序列长度加1，那我肯定是选择前面一个最小的数。 如果我们使序列长度增长，那我们肯定就使选择一个当前的次小值将他替换当前队尾的值，这里你可以用超级钢琴的思想来做，然后用个堆维护。 然后关于字典序之类的，你可以用他pre的rank来瞎搞搞。 （关于卡长，有一个小技巧：把数组维数换一换就能快。。。 我本来st表是这么开的：int f[1000010][21] 给成这样就快了：int f[21][1000010] 至于能快多少，这道题里面，差不多有6，7s这样子。。。 ）
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std
;
typedef long long LL
;
inline int read() {
int s
= 0, f
= 1; char ch
= getchar();
while(ch
< '0' || ch
> '9') {if(ch
== '-') f
= -1; ch
= getchar();}
while(ch
>= '0' && ch
<= '9') s
= s
* 10 + ch
- '0', ch
= getchar();
return s
* f
;
}
struct node
{
LL sum
;
int l
, r
, x
, pre
, rank
;
} p
[3000010];
int o
, heap
[3000010];
LL a
[1000010];
int Log
[1000010], f
[21][1000010], bin
[21];
inline int _min(int x
, int y
) {return a
[x
] <= a
[y
] ? x
: y
;}
inline bool pd(int x
, int y
) {
if(p
[x
].sum
== p
[y
].sum
) {
if(p
[x
].x
== p
[y
].x
) return p
[p
[x
].pre
].rank
< p
[p
[y
].pre
].rank
;
return p
[x
].x
< p
[y
].x
;
} return p
[x
].sum
< p
[y
].sum
;
}
inline void up(int x
) {
while(x
) {
if(x
/ 2 && pd(heap
[x
], heap
[x
/ 2])) swap(heap
[x
], heap
[x
/ 2]), x
/= 2;
else break;
}
}
inline void down(int x
) {
int s
= x
* 2;
while(s
<= o
) {
if(s
< o
&& pd(heap
[s
+ 1], heap
[s
])) s
++;
if(pd(heap
[s
], heap
[x
])) swap(heap
[x
], heap
[s
]), x
= s
, s
*= 2;
else break;
}
}
inline int query(int l
, int r
) {
register int hh
= Log
[r
- l
+ 1];
return _min(f
[hh
][l
], f
[hh
][r
- bin
[hh
] + 1]);
}
inline void print(int x
) {
printf("%d ", p
[x
].x
);
if(p
[x
].pre
) print(p
[x
].pre
);
}
int main() {
int n
= read(), k
= read(); k
--;
if(k
== 0) {
printf("0\n");
return 0;
}
a
[0] = 999999999;
register int i
, j
;
for(i
= 2; i
<= n
; ++i
) Log
[i
] = Log
[i
>> 1] + 1;
for(i
= 1; i
<= n
; ++i
) a
[i
] = read(), f
[0][i
] = i
;
bin
[0]=1;
for(i
= 1; i
<= 20; ++i
) bin
[i
] = bin
[i
- 1] << 1;
for(i
= 1; bin
[i
] <= n
; ++i
) for(j
= 1; j
+ bin
[i
- 1] <= n
; ++j
) f
[i
][j
] = _min(f
[i
- 1][j
], f
[i
- 1][j
+ bin
[i
- 1]]);
int tp
= 1;
p
[1].l
= 1, p
[1].r
= n
, p
[1].x
= query(1, n
), p
[1].sum
= a
[p
[1].x
], p
[1].pre
= 0;
heap
[o
= 1] = 1;
LL last
= -1, hh
= 0;
while(k
--) {
int g
= heap
[1];
swap(heap
[1], heap
[o
--]);
down(1);
node now
= p
[g
];
if(!k
) {printf("%lld\n", now
.sum
); print(g
); return 0;}
if(now
.sum
> last
) last
= now
.sum
, hh
= 1;
else hh
++;
p
[g
].rank
= hh
;
if(now
.x
> 1) {
int j
= ++tp
;
p
[j
].l
= 1, p
[j
].r
= now
.x
- 1, p
[j
].x
= query(1, now
.x
- 1);
p
[j
].sum
= now
.sum
+ a
[p
[j
].x
], p
[j
].pre
= g
;
heap
[++o
] = j
; up(o
);
}
if(now
.l
< now
.x
) {
int j
= ++tp
;
p
[j
].l
= now
.l
, p
[j
].r
= now
.x
- 1, p
[j
].x
= query(now
.l
, now
.x
- 1);
p
[j
].sum
= now
.sum
+ a
[p
[j
].x
] - a
[now
.x
], p
[j
].pre
= now
.pre
;
heap
[++o
] = j
; up(o
);
}
if(now
.x
< now
.r
) {
int j
= ++tp
;
p
[j
].l
= now
.x
+ 1, p
[j
].r
= now
.r
, p
[j
].x
= query(now
.x
+ 1, now
.r
);
p
[j
].sum
= now
.sum
+ a
[p
[j
].x
] - a
[now
.x
], p
[j
].pre
= now
.pre
;
heap
[++o
] = j
; up(o
);
}
}
return 0;
}
