Untitled

 avatar
unknown
c_cpp
2 years ago
3.9 kB
3
Indexable
// #include <bits/stdc++.h>
// using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXN 300005

int n,m,COLOR_HASH[MAXN],HASH[MAXN],lb[MAXN], rb[MAXN], color_cnt;
int ma=0,mi=1e9;


typedef struct Info{
    int color,appetite,idx;
}Info;
Info info[MAXN];

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}
void swapInfo(Info *a,Info *b){
    Info tmp=*a;
    *a=*b;
    *b=tmp;
}

int hash_color(int color){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(info[mid].color<color) l=mid+1;
        else r=mid;
    }
    return COLOR_HASH[l];
}

void ope1(){
    int color,L,R;
    scanf("%d %d %d",&color,&L,&R);
    int C=hash_color(color);
    int l=lb[C], r=rb[C];
    while(l<r){
        int mid=(l+r)/2;
        if(info[mid].appetite<L) l=mid+1;
        else r=mid;
    }
    if(info[l].appetite<L){
        printf("0\n");
        return;
    }
    int ansL=l;

    l=lb[C], r=rb[C];
    while(l<r){
        int mid=(l+r)/2;
        if(info[mid].appetite<=R) l=mid+1;
        else r=mid;
    }
    if(info[l].appetite<=R) l++;
    int ansR=l;

    printf("%d\n",ansR-ansL);
}

void ope2(){
    int k;
    scanf("%d",&k);
    k=HASH[k];
    if(info[k].appetite==ma) return;

    int target=n;
    for(int c=0;c<color_cnt;c++){
        int l=lb[c],r=rb[c];
        while(l<r){
            int mid=(l+r)/2;
            if(info[mid].appetite<=info[k].appetite) l=mid+1;
            else r=mid;
        }
        if(info[l].appetite>info[k].appetite && info[l].appetite < info[target].appetite) target=l;
    }
    swap(&info[k].appetite,&info[target].appetite);
    if(info[k].color==info[target].color){
        swapInfo(&info[k],&info[target]);
        swap(&HASH[info[k].idx],&HASH[info[target].idx]);
    }
}

void ope3(){
    int c,d,t;
    scanf("%d %d %d",&c,&d,&t);
    int C=hash_color(c);
    int L=lb[C];
    int R=rb[C];
    if(d){ //right
        if(t){ //max
            info[R].appetite=++ma;
        }else{
            Info tmp=info[R];
            tmp.appetite=--mi;
            for(int i=R;i>L;i++){
                info[i]=info[i-1];
                HASH[info[i].idx]=i;
            }
            info[L]=tmp;
            HASH[info[L].idx]=L;
        }
    }else{ //left
        if(t){ //max
            Info tmp=info[L];
            tmp.appetite=++ma;
            for(int i=L;i<R;i++){
                info[i]=info[i+1];
                HASH[info[i].idx]=i;
            }
            info[R]=tmp;
            HASH[info[R].idx]=R;
        }else{
            info[L].appetite=--mi;
        }
    }
}

int cmp(const void *a, const void *b){
    Info i=*(const Info *)a;
    Info j=*(const Info *)b;
    if(i.color!=j.color) return i.color-j.color;
    else return i.appetite-j.appetite;
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&info[i].appetite);
        info[i].idx=i;
        ma=max(ma,info[i].appetite);
        mi=min(mi,info[i].appetite);
    }
    for(int i=0;i<n;i++) scanf("%d",&info[i].color);
    info[n].appetite=info[n].color=INT_MAX;

    qsort(info,n,sizeof(info[0]),cmp);

    for(int i=1;i<=n;i++){
        COLOR_HASH[i]=COLOR_HASH[i-1];
        if(info[i].color!=info[i-1].color) COLOR_HASH[i]++;
        
        if(info[i].color!=info[i+1].color) rb[COLOR_HASH[i]]=i;
        if(info[i].color!=info[i-1].color) lb[COLOR_HASH[i]]=i;
    }
    color_cnt=COLOR_HASH[n];
    for(int i=0;i<n;i++) HASH[info[i].idx]=i;

    // for(int i=0;i<n;i++) printf("%d %d %d %d\n",info[i].idx,info[i].color,info[i].appetite,HASH[i]);
    // cout << endl;

    while(m--){
        int x;
        scanf("%d",&x);
        if(x==1) ope1();
        if(x==2) ope2();
        if(x==3) ope3();
        // for(int i=0;i<n;i++) printf("%d %d %d %d\n",info[i].idx,info[i].color,info[i].appetite,HASH[i]);
        // cout << endl;
    }
}
Editor is loading...