Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
2.3 kB
2
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXN 300005

int n,m,color[MAXN],appetite[MAXN],idx[MAXN];
int ma=0,mi=1e9;

typedef struct appetite_sort appetite_sort;
struct appetite_sort{
    int val,idx;
}appetite_sorted[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;
}
int lower_bound(int target){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(color[idx[mid]]<target) l=mid+1;
        else r=mid;
    }
    return l;
}
int upper_bound(int target){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r)/2;
        if(color[idx[mid]]<=target) l=mid+1;
        else r=mid;
    }
    return l;
}

void ope1(){
    int c,l,r;
    scanf("%d %d %d",&c,&l,&r);
    int L=lower_bound(c);
    int R=upper_bound(c);
    int ans=0;
    for(int i=L;i<R;i++){
        if(l<=appetite[idx[i]] && appetite[idx[i]]<=r) ans++;
    }
    printf("%d\n",ans);
}

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

    int target=n;
    for(int i=0;i<n;i++){
        if(appetite[i]>appetite[k] && appetite[i]<appetite[target]) target=i;
    }
    swap(&appetite[k],&appetite[target]);
}
void ope3(){
    int c,d,t;
    scanf("%d %d %d",&c,&d,&t);
    int L=lower_bound(c);
    int R=upper_bound(c);
    int target=0;
    int bound=d?0:INT_MAX;
    for(int i=L;i<R;i++){
        if(d && color[idx[i]]>color[target]) target=idx[i];
        if(!d && color[idx[i]]<color[target]) target=idx[i];
    }
    if(t) appetite[target]=++ma;
    else  appetite[target]=--mi;
}

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

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

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

    appetite[n]=color[n]=INT_MAX;
    while(m--){
        int x;
        scanf("%d",&x);
        if(x==1) ope1();
        if(x==2) ope2();
        if(x==3) ope3();
    }
}