题解 P2343 【宝石管理系统】

123456zmy · 2020-02-16 09:17:49 · 题解

看到还没用题解用块状链表的，赶紧来水一发。

题意：
给你 m 个数，q 次操作，每次加入一个数 n 或查询全局第 k 大。

其实就是用分块优化的暴力。先找到是对哪一块操作，再加个暴力即可，如果一块过大，则强行拆成两块，插入和查询都是 O(\sqrt{m}) 的。因为我写的是从小到大排序，所以每次查询要稍微改一点。

代码：（码风邪教，复杂度：O((m+q)\sqrt{m})，开 O2 之后跑得飞起）

#include<bits/stdc++.h>
using namespace std;
int c,n,m,q,a[501][501],al[501],an=1,v0,nxt[501],h=1;
void ins(int k)//插入
{
    int i,j;
    for(j=h;nxt[j]&&a[nxt[j]][1]<k;j=nxt[j]);
    for(i=1;i<=al[j]&&a[j][i]<k;i++);
    ++al[j];
    for(;i<=al[j];i++)swap(k,a[j][i]);
    if(al[j]==500)
    {
        nxt[++an]=nxt[j];
        nxt[j]=an;
        al[j]=al[an]=250;
        for(i=251;i<=500;i++)swap(a[an][i-250],a[j][i]);
    }
}
int find(int k)//查询
{
    int j,n1=0;
    for(j=h;nxt[j]&&n1+al[j]<k;j=nxt[j])n1+=al[j];
    return a[j][k-n1];
}
int main()
{
    scanf("%d%d",&m,&q);
    for(int i=1;i<=m;i++)scanf("%d",&v0),ins(v0);//其实可以用sort来优化的。
    while(q--)
    {
        scanf("%d%d",&c,&n);
        if(c==1)printf("%d\n",find(m-n+1));
        else ins(n),++m;
    }
    return 0;
}