题解：P11221 [COTS 2019] 序列操作 K-ti

· · 题解

分块比较板子的题目。

每个块内维护每个下标对 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;
}