题解 P2596 【[ZJOI2006]书架】

· · 题解

Online operate & quest 在线操作查询

（树状数组是骗分AC的好东西）

按题意用数组 shelt 模拟书架，前后预留长度，

L,R 分别表示书架顶端、底端

Top, Bottom, Insert 按题意模拟即可，把原来有书现在留空的地方置为0，更新树状数组，

用3个函数：加入(add), 删除(dele) delete是关键字 , 计算上面有多少书(cal).

提高组水平的暴力模拟

MORE VIOLENT YOUR CODE IS, MORE EXTRA MARKS BELONG TO YOU

(less than 100ms)

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char t[10];
int shelf[240005],f[240005];
int c[240005];  // put books into a Binary Indexed Tree
int n,m,S,T,L,R,Next,Left,Right,mid,ans;
const int TOP=80000;
int lowbit(int x)
{
    return x-(x&(x-1));
}
void add(int x)
{
    while(x<=3*TOP+3)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
void dele(int x)
{
    while(x<=3*TOP+3)
    {
        c[x]--;
        x+=lowbit(x);
    }
}
int cal(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&shelf[TOP+i]);
        f[shelf[TOP+i]]=TOP+i;
        add(TOP+i);
    }
    L=TOP+1; R=TOP+n;
    while(m--)
    {
        scanf("%s%d",t,&S);
        if(t[0]=='T')
        {
            shelf[f[S]]=0;
            dele(f[S]);
            f[S]=L-1;
            add(f[S]);
            L--;
            shelf[f[S]]=S;
        }
        if(t[0]=='B')
        {
            shelf[f[S]]=0;
            dele(f[S]);
            f[S]=R+1;
            add(f[S]);
            R++;
            shelf[f[S]]=S;
        }
        if(t[0]=='I')
        {
            cin>>T;
            int k=T;
            while(shelf[f[S]+T]==0)
                T+=k;
            Next=shelf[f[S]+T];
            swap(shelf[f[S]],shelf[f[S]+T]);
            swap(f[S],f[Next]);
        }
        if(t[0]=='A')
            printf("%d\n",cal(f[S]-1));
        if(t[0]=='Q')
        {
            Left=L; Right=R; ans=240004;
            while(Left<=Right)
            {
                mid=(Left+Right)/2;
                if(cal(mid)>=S)
                {
                    ans=min(ans,mid);
                    Right=mid-1;
                }
                else
                    Left=mid+1;
            }
            printf("%d\n",shelf[ans]);
        }
    }
    return 0;
}