并不对劲的bzoj1861: [Zjoi2006]Book 书架

传送门->

这题的正确做法是splay维护这摞书。

但是并不对劲的人选择了暴力（皮这一下很开心）。

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define re register

#define maxn 300010

using namespace std;

inline int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(isdigit(ch)==0 && ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(int x)

{

    int f=0;char ch[20];

    if(!x){puts("0");return;}

    if(x<0){putchar('-');x=-x;}

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

}

int a[maxn],tr[maxn],pos[maxn],n,m,qx,qy,hd,tl;

char s[20];

int lt(int x){return x&(-x);}

void add(int x,int k){for(;x<=n+m*2;x+=lt(x))tr[x]+=k;}

int ask(int x){int k=0;for(;x;x-=lt(x))k+=tr[x];return k;}

int kth(int k)

{

    int l=hd,r=tl,ans=tl+233;

    while(l<=r)

    {

        int mi=(r+l)>>1;

        int rank=ask(mi);

        if(rank==k)ans=min(ans,mi);

        if(rank>=k)r=mi-1;

        else l=mi+1;

    }

    return ans;

}

int main()

{

    n=read(),m=read();hd=1+m,tl=n+m;

    rep(i,1,n)a[i+m]=read(),pos[a[i+m]]=i+m,add(i+m,1);

    rep(k,1,m)

    {

    	scanf("%s",s);qx=read();

    	if(s[0]=='T')add(pos[qx],-1),hd--,add(hd,1),swap(a[hd],a[pos[qx]]),pos[qx]=hd;

    	if(s[0]=='B')add(pos[qx],-1),tl++,add(tl,1),swap(a[tl],a[pos[qx]]),pos[qx]=tl;

    	if(s[0]=='I')

    	{

    		qy=read();if(!qy)continue;

    		int tmp=ask(pos[qx])+qy;

    	//	cout<<"rank:"<<tmp<<endl;

    		int ans=kth(tmp);

    	//	cout<<"ans&pos:"<<qx<<" "<<a[ans]<<pos[qx]<<" ";

            int px=pos[qx];

            swap(pos[qx],pos[a[ans]]);swap(a[px],a[ans]);// cout<<pos[qx]<<endl;

    	}

    	if(s[0]=='A')write(ask(pos[qx])-1);

    	if(s[0]=='Q')

    	{

    		int ans=kth(qx);

    		write(a[ans]);

    	}

   	//cout<<"a:"<<endl;

   	//rep(i,1,n+m*2)cout<<a[i]<<" ";cout<<endl;

   	//cout<<"pos:"<<endl;

   	//rep(i,1,n)cout<<pos[i]<<" ";cout<<endl;

    }

    return 0;

}

/*

10 10

1 3 2 7 5 8 10 4 9 6

Query 3

Top 5

Ask 6

Bottom 3

Ask 3

Top 6

Insert 4 -1

Query 5

Query 2

Ask 2

*/

　　

据说照顾了splay的大肠腧的数据为暴力提供了漏洞。