举报@臣萎根 抄袭大量题解

题目：P3285 [SCOI2014]方伯伯的OJ
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
struct Node{
    Node* l;
    Node* r;
    int cal,val;
    Node(){
        cal=val=0;
        l=r=NULL;
    }
};
int n,q,Bi,Ai,Jia,Len,pai;
Node* Root;
map<int,int> wei;

Node* NewNode(){
    return new Node();
}

inline int Cal(Node* o,int l,int r)
{
    if(o!=NULL)
        return o->cal;
    r=min(Jia+n,r);
    l=max(Jia+1,l);
    return (l>r?0:r-l+1);
}

void update(Node* o,int l,int r,int k,int val0,int cao)
{
//  printf("%d %d %d %d %d %d\n",l,r,k,val0,cao,pai);
    o->cal+=cao;
    if(l==r){
        if(cao!=-1)
            o->val=val0;
        return;
    }
    int mid=(l+r)>>1,l_cal=Cal(o->l,l,mid);
//  cout<<"cal: "<<l_cal<<endl;
    if(k<=mid)
    {
        if(o->l==NULL){
            o->l=NewNode();
            o->l->cal=l_cal;
        }
        update(o->l,l,mid,k,val0,cao);
    }
    else
    {
        if(o->r==NULL){
            o->r=NewNode();
            o->r->cal=o->cal-1-l_cal;
        }
        pai+=l_cal;
        update(o->r,mid+1,r,k,val0,cao);
    }
}

int query(Node* o,int l,int r,int k)
{
    if(l==r){
        if(!o->val)
            o->val=l-Jia;
        return o->val;
    }
    int mid=(l+r)>>1,l_cal=Cal(o->l,l,mid); 
    if(k<=l_cal)
    {
        if(o->l==NULL){
            o->l=NewNode();
            o->l->cal=l_cal;
        }
        return query(o->l,l,mid,k);
    }
    else
    {
        if(o->r==NULL){
            o->r=NewNode();
            o->r->cal=o->cal+1-l_cal;
        }
        return query(o->r,mid+1,r,k-l_cal);
    }
}

void out(int f,int x){
    printf("After %d %d the rank is :\n",f,x);
    for(int i=1;i<=n;i++)
        printf("%d ",query(Root,1,Len,i));
    printf("\nEnd\n");

}

int main()
{
//  freopen("scoi.in","r",stdin);
//  freopen("scois.out","w",stdout);
    Root=NewNode();
    scanf("%d%d",&n,&q);
    Jia=q;
    Root->cal=n;
    Bi=Jia;
    Ai=Jia+n+1;
    Len=n+2*Jia;
    int a=0;
    while(q--)
    {
        pai=0;
        int f,x,y;
        scanf("%d%d",&f,&x);
        x-=a;
        int w=wei[x];
//      cout<<"sd:"<<w<<endl;
        if(!w) w=x+Jia;
        if(f==1)
        {
            scanf("%d",&y);
            y-=a;   
            wei[x]=-1;
            wei[y]=w;

            update(Root,1,Len,w,y,0);
            pai++;
            a=pai;
            printf("%d\n",a);
        }
        else if(f==2)
        {
            wei[x]=Bi;

            update(Root,1,Len,w,2853,-1);
            pai++;
            a=pai;
            printf("%d\n",a);
            update(Root,1,Len,Bi,x,1);
            Bi--;
        }
        else if(f==3)
        {
            wei[x]=Ai;

            update(Root,1,Len,w,2853,-1);
            pai++;
            a=pai;
            printf("%d\n",a);
            update(Root,1,Len,Ai,x,1);
            Ai++;
        }
        else
        {
            a=query(Root,1,Len,x);
            printf("%d\n",a);
        }
//      out(f,x);
    }
    return 0;
}