题解 P2617 【Dynamic Rankings】

· · 题解

此题是一道练习离散化的好题

离散化可以让一些算法在允许的空间复杂度内实现

例如本题中我们要用到的桶排

我们把操作离线下来，用快排+map实现离散化，用ren实现映射

然后我们可以

暴力模拟+适当优化23333

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

const int MAXN=1e4+5;

int n,m;
int a[MAXN<<1],ren[MAXN<<1],b[MAXN<<1],cup[MAXN<<1];
struct rpg{
    int x,y,z,kd;
}c[MAXN];
map <int,int> mp;

int main()
{
    scanf("%d%d",&n,&m);b[0]=n;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    for(int i=1;i<=m;++i){
        char ch;int x,y,z;
        scanf("\n%c",&ch);
        if(ch=='Q') scanf("%d%d%d",&x,&y,&z),c[i]=(rpg){x,y,z,1};
        else scanf("%d%d",&x,&y),c[i]=(rpg){x,y,0,2},b[++b[0]]=y;
    }sort(b+1,b+b[0]+1);
    for(int i=1;i<=b[0];++i){
        while(b[i+1]==b[i]) ++i;
        ren[++ren[0]]=b[i];
        mp[b[i]]=ren[0];
    }for(int i=1;i<=n;++i) a[i]=mp[a[i]];
    for(int i=1;i<=m;++i){
        if(c[i].kd==1){
            int cnt=0;
            for(int j=c[i].x;j<=c[i].y;++j) ++cup[a[j]];
            for(int j=1;j<=ren[0];++j){
                if(cnt+cup[j]>=c[i].z){
                    printf("%d\n",ren[j]);
                    break;
                }cnt+=cup[j];
            }for(int j=c[i].x;j<=c[i].y;++j) cup[a[j]]=0;
        }else a[c[i].x]=mp[c[i].y];
    }return 0;
}