Untitled

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXN 300005

int n,m,COLOR_HASH[MAXN],HASH[MAXN], color_cnt, color_sorted[MAXN] ,Num[MAXN], color_cnt;
const int inf=INT_MAX;

typedef struct Node{
    int val, size, cnt, w, color,idx;
    struct Node *l, *r;
} Node;

Node *new_node(int x,int color,int idx){
    Node* node = (Node*) malloc(sizeof(Node));
    node->val=x;
    node->color=color;
    node->idx=idx;
    node->size=1;
    node->cnt=1;
    node->w=rand();
    node->l=NULL;
    node->r=NULL;
    return node;
}

void update_son(Node* node){
    node->size=node->cnt;
    if(node->l != NULL) node->size+=node->l->size;
    if(node->r != NULL) node->size+=node->r->size;
}

Node *built(){
    Node* rt=new_node(inf,-1,-1);
    rt->l=new_node(-inf,-1,-1);
    rt->w=-inf;
    rt->l->w=-inf;
    update_son(rt);
    return rt;
}

Node *root[MAXN], *ALL;

void left_rotate(Node** a){
    Node* b=(*a)->r;
    (*a)->r=b->l;
    b->l=(*a);
    (*a)=b;
    update_son((*a));
    update_son((*a)->l);
}

void right_rotate(Node** a){
    Node* b=(*a)->l;
    (*a)->l=b->r;
    b->r=(*a);
    (*a)=b;
    update_son((*a));
    update_son((*a)->r);
}

int size(Node *node){
    return node ? node->size : 0;
}

void insert(Node** node, int val,int color,int idx){
    if(!(*node)){
        (*node)=new_node(val,color,idx);
        return;
    }
    if(val == (*node)->val){
        (*node)->cnt++;
    }else if(val < (*node)->val){
        insert(&((*node)->l), val, color,idx);
        if((*node)->l->w < (*node)->w) right_rotate(node);
    }else{
        insert(&((*node)->r), val, color,idx);
        if((*node)->r->w < (*node)->w) left_rotate(node);
    }
    update_son((*node));
}

void del(Node** node, int val){
    if (val < (*node)->val) del(&(*node)->l, val);
    else if ((*node)->val < val) del(&(*node)->r, val);
    else {
        if ((*node)->cnt > 1) {
            (*node)->cnt--;
            update_son((*node));
            return;
        }
        if ((*node)->l == NULL && (*node)->r == NULL) {
            free(*node);
            *node = NULL;
            return;
        }
        if ((*node)->l == NULL) {
            left_rotate(node);
            del(&(*node)->l, val);
        } else if ((*node)->r == NULL) {
            right_rotate(node);
            del(&(*node)->r, val);
        } else {
            if ((*node)->l->w < (*node)->r->w) {
                right_rotate(node);
                del(&(*node)->r, val);
            } else {
                left_rotate(node);
                del(&(*node)->l, val);
            }
        }
    }
    update_son((*node));
}

int val_to_rank(Node *node, int val){
    if(val == node->val) return size(node->l) + 1;
    else if(val < node->val) return val_to_rank(node->l,val);
    else return size(node->l) + node->cnt + val_to_rank(node->r,val);
}

int element_color=0, element_idx=0,rank=0;
int _rank_to_val(Node *node, int rank){
    if(rank <= size(node->l)) return _rank_to_val(node->l,rank);
    else if(rank <= size(node->l) + node->cnt){
        element_idx=node->idx;
        return node->val;
    }else return _rank_to_val(node->r,rank - size(node->l) - node->cnt);
}

int rank_to_val(Node *node, int rank){
    return _rank_to_val(node,rank+1);
}

int suff_equal(Node* p, int val){
    int suf=0;
    rank=0;
    while(p){
        if(val > p->val)  rank+=size(p->l)+1, p=p->r;
        else suf=p->val,element_color=p->color, element_idx=p->idx, p=p->l;
    }
    return suf;
}


int suff_bigger(Node* p, int val){
    int suf=0;
    rank=0;
    while(p){
        if(val >= p->val)  rank+=size(p->l)+1, p=p->r;
        else suf=p->val, element_color=p->color, element_idx=p->idx, p=p->l;
    }
    return suf;
}

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=color_cnt-1;
    while(l<r){
        int mid=(l+r)/2;
        if(color_sorted[mid]<color) l=mid+1;
        else r=mid;
    }
    if(color_sorted[l]!=color) return -1;
    return l;
}

void ope1(){
    int color,L,R;
    scanf("%d %d %d",&color,&L,&R);
    int C=hash_color(color);
    if(C==-1){
        printf("0\n");
        return;
    }
    suff_equal(root[C],L);
    int lb=rank;
    suff_bigger(root[C],R);
    int rb=rank;;
    printf("%d\n",rb-lb);
}

void ope2(){
    int k;
    scanf("%d",&k);
    int bigger_appe=suff_bigger(ALL, info[k].appetite);
    int bigger_color=element_color;
    int bigger_idx=element_idx;

    if(bigger_color==-1) return;

    int cur_appe=suff_equal(ALL, info[k].appetite);
    int cur_color=element_color;
    int cur_idx=element_idx;

    del(&ALL,cur_appe);
    del(&ALL,bigger_appe);

    insert(&ALL,bigger_appe,cur_color,cur_idx);
    insert(&ALL,cur_appe,bigger_color,bigger_idx);

    del(&root[cur_color],cur_appe);
    del(&root[bigger_color],bigger_appe);

    insert(&root[cur_color],bigger_appe,cur_color,cur_idx);
    insert(&root[bigger_color],cur_appe,bigger_color,bigger_idx);

    swap(&info[cur_idx].appetite, &info[bigger_idx].appetite);
}

void ope3(){
    int c,d,t;
    scanf("%d %d %d",&c,&d,&t);
    c=hash_color(c);

    int new_val, old_val, target_idx;
    if(d){ //max
        old_val=rank_to_val(root[c],Num[c]);
        target_idx=element_idx;
    }else{ //min
        old_val=rank_to_val(root[c],1);
        target_idx=element_idx;
    }
    if(t){ //ma+1
        new_val=rank_to_val(ALL,n)+1;
    }else{ //mi-1
        new_val=rank_to_val(ALL,1)-1;
    }

    del(&root[c],old_val);
    insert(&root[c],new_val,c,target_idx);

    del(&ALL,old_val);
    insert(&ALL,new_val,c,target_idx);
    
    info[target_idx].appetite=new_val;
}

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);
    for(int i=0;i<n;i++) scanf("%d",&info[i].color), color_sorted[i]=info[i].color;
    
    qsort(color_sorted,n,sizeof(color_sorted[0]),cmp);

    Num[0]++;
    for(int i=1;i<=n;i++){
        if(color_sorted[i]!=color_sorted[color_cnt]) color_cnt++;
        
        color_sorted[color_cnt]=color_sorted[i];
        Num[color_cnt]++;
    }

    for(int i=0;i<color_cnt;i++) root[i]=built();
    ALL=built();

    for(int i=0;i<n;i++){
        info[i].color=hash_color(info[i].color);
        insert(&root[info[i].color],info[i].appetite,info[i].color,i);
        insert(&ALL,info[i].appetite,info[i].color,i);
    }
    
    while(m--){
        int x;
        scanf("%d",&x);
        if(x==1) ope1();
        if(x==2) ope2();
        if(x==3) ope3();
    }
}