@[optimize_2](/user/224978) 动态还是静态？
动态可以用对顶堆，静态直接 nth_element 就行了
by _thiscall @ 2021-09-11 19:21:02
@[optimize_2](/user/224978) 之前tg有道阅读程序是这样
by S0CRiA @ 2021-09-11 19:26:15
@[optimize_2](/user/224978) 哦不对是pj
https://ti.luogu.com.cn/problemset/1028 第23题
by S0CRiA @ 2021-09-11 19:27:42
@[optimize_2](/user/224978) 傻逼吗，每次把信息重新塞到答案里。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using GTR::read;
int n,lim,tp;
const int N=1e7+5,M=3e6+5;
int a[N],ans[6][M],w[N];
vector<int>q[M];
int sta[N],st;
inline void work(int id){
sta[0]=0,st=0;
for (int i=1;i<=n;++i){
for (vector<int>::iterator it=q[i].begin();it!=q[i].end();++it){
while (st>0&&a[sta[st]]<a[*it]) st--;
ans[id][*it]=sta[st];
}
while (st>0&&a[sta[st]]<a[i]) st--;
sta[++st]=i;
}
}
int main(){
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
n=read(),lim=read(),tp=read();
for (int i=1;i<=n;++i) a[i]=read();
if (lim==1){
sta[0]=0,st=0;
for (int i=1;i<=n;++i){
while (st>0&&a[sta[st]]<a[i]) st--;
w[i]=sta[st];
sta[++st]=i;
}
if (tp==0){
for (int i=1;i<=n;++i){
for (int j=1;j<=lim;++j)
printf("%d ",w[i]);
printf("\n");
}
}else{
ll res=0;
for (ll i=1;i<=n;++i)
for (ll j=1;j<=lim;++j)
res^=1ll*w[i]*i*j;
cout << res << endl;
}
return 0;
}else{
for (int i=1;i<=n;++i) q[i].push_back(i);
for (int i=1;i<=lim;++i)
{
work(i);
if (i==lim) continue;
for (int j=1;j<=n;++j) while (q[j].size()) q[j].pop_back();
for (int j=1;j<=n;++j)
{
if (ans[i][j]==0) continue;
q[ans[i][j]].push_back(j);
}
}
}
if (tp==0){
for (int i=1;i<=n;++i){
for (int j=1;j<=lim;++j)
printf("%d ",ans[j][i]);
printf("\n");
}
}else{
ll res=0;
for (ll i=1;i<=n;++i)
for (ll j=1;j<=lim;++j)
res^=(1ll*ans[j][i])*i*j;
cout << res << endl;
}
return 0;
}
```
by Bosun @ 2021-09-11 19:30:35
@[optimize_2](/user/224978) 你就是逊
by Bosun @ 2021-09-11 19:34:15
@[zbs140](/user/127915) 语气这么冲干嘛楼主也没招惹到你啊
by 子丑 @ 2021-09-11 19:48:23
@[子丑](/user/428154) 没有，开玩笑，他我同学
by Bosun @ 2021-09-11 20:11:40
都别当真
by Bosun @ 2021-09-11 20:12:20
一般这样回复的都是认识的啦@[子丑](/user/428154)
by BlankAo @ 2021-09-11 21:32:55
@[zbs140](/user/127915) 吓到了不过我之前也猜你们是同学
by 子丑 @ 2021-09-11 21:44:13