spoj8406

题解：

二分+树状数组

记录以下i在当前拍第几

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=;

int a[N],f1[N],f2[N],n,m,x,y,num[N];

int js(int x)

{

    int ans=;

    for (;x;x-=x&-x)ans+=num[x];

    return ans;

}

void inster(int x,int y)

{

    for (;x<=n;x+=x&-x)num[x]+=y;

}

int cmp(int x,int y)

{

    return a[x]<a[y];

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)scanf("%d",&a[i]),f1[i]=f2[i]=i;

    sort(f1+,f1+n+,cmp);

    for (int i=;i<=n;i++)f2[f1[i]]=i;

    for (int i=;i<=n;i++)inster(i,a[f1[i]]-a[f1[i-]]);

    while (m--)

     {

         scanf("%d%d",&x,&y);

         if (x==)

          {

             if (js(n)<y){puts("");continue;}

              int l=,r=n;

              while (l<r)

               {

                   int mid=(l+r)/;

                   if (y>js(mid))l=mid+;

                   else r=mid;

               }

              printf("%d\n",n-l+);

          }

         if (x==)

         {

             if (js(n)<y)continue;

              int l=,r=n;

              while (l<r)

               {

                   int mid=(l+r)/;

                   if (y>js(mid))l=mid+;

                   else r=mid;

               }

              inster(l,-);

         }

         if (x==)

         {

             int l=,r=n,k=js(f2[y]);

             while (l<r)

              {

                  int mid=(l+r+)/;

                  if (k<js(mid))r=mid-;

                  else l=mid;

              }

             swap(f1[f2[y]],f1[l]);

            swap(f2[f1[f2[y]]],f2[f1[l]]);

            inster(l,);

            inster(l+,-);

         }

     }

}