自动搬运

查看原文

来自洛谷，原作者为

	suzhikz 我永远喜欢艾莉丝！

搬运于2025-08-24 23:05:25，当前版本为作者最后更新于2025-06-08 19:07:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分块比较板子的题目。

每个块内维护每个下标对 $k$ 取模后每种下标的最大值。

询问的时候维护下扫过的数字个数 $cnt$，然后在下一个块查询下标取模后为 $(k-(cnt \bmod k)\bmod k)$ 的位置。

删除就是把询问再做一遍然后找到第一个有这个数的块，然后删除后再暴力重构。

//我永远喜欢艾莉丝!
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<random>
#include<time.h>
#include<stdlib.h>
#include<bitset>
#define il inline
#define reg register
#define ll long long
#define popcount __builtin_popcount
using namespace std;
//#define int __int128
inline void read(int &n){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}n=x*f;}
inline void read(ll &n){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}n=x*f;}
const int N=1e5+5,B=405;
int n,k,a[N];
struct node{
	int m,l[B+10],r[B+10],w[B+10],maxx[B+10],siz;
	void init(vector<int>g){
		m=siz=g.size();
		r[0]=1;l[m+1]=m;
		for(int i=0;i<m;i++){
			w[i+1]=g[i];l[i+1]=i;r[i+1]=i+2;
			maxx[i%k]=max(maxx[i%k],g[i]);
		}
	}
	int find(int x){
		if(x>B)return 0;else return maxx[x];
	}
	void del(int ma,int mb){
		int u=0;
		int cnt=0;
		for(int i=r[0];i<=m&&i>0;i=r[i]){
			if(cnt%k==mb&&w[i]==ma){
				u=i;break;
			}
			cnt++;
		}
		memset(maxx,0,sizeof(maxx));siz--;
		r[l[u]]=r[u];l[r[u]]=l[u];
		cnt=0;
//		cout<<ma<<' '<<u<<endl;
		for(int i=r[0];i<=m&&i>0;i=r[i]){
//			cout<<w[i]<<' ';
			maxx[cnt%k]=max(maxx[cnt%k],w[i]);
			cnt++;
		}
	}
}b[405];int tot;

int main(){
	read(n);read(k);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=(n-1)/B+1;i++){
		int l=(i-1)*B+1,r=min(n,i*B);
		vector<int>tmp;
		for(int j=l;j<=r;j++){
			tmp.push_back(a[j]);
		}
		tot++;b[tot].init(tmp);
	}
	for(int i=1;i<=n;i++){
		int cnt=0,maxx=0,cnt2;
		for(int j=1;j<=tot;j++){
			maxx=max(maxx,b[j].find((k-cnt%k)%k));
			cnt+=b[j].siz;
		}
		cnt=0;
//		cout<<pos<<' ';
		cout<<maxx<<endl;
		for(int j=1;j<=tot;j++){
			if(b[j].find((k-cnt%k)%k)==maxx){
				b[j].del(maxx,(k-cnt%k)%k); break;
			}else{
				cnt+=b[j].siz;
			}
		}
//		cout<<endl;
	} 
	
	
	return 0;
}