Untitled
unknown
c_cpp
7 months ago
9.5 kB
2
Indexable
Never
// #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, color_sorted[MAXN] ,Num[MAXN]; 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; 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; while(p){ if(val > p->val) 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; while(p){ if(val >= p->val) 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=n; 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 COLOR_HASH[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; } int lb=val_to_rank(root[C], suff_equal(root[C],L)); int rb=val_to_rank(root[C], suff_bigger(root[C],R)); printf("%d\n",rb-lb); } void ope2(){ int k; scanf("%d",&k); // printf("in ope2 find %d\n",info[k].appetite); int cur_appe=suff_equal(ALL, info[k].appetite); int cur_color=element_color; int cur_idx=element_idx; int bigger_appe=suff_bigger(ALL, info[k].appetite); int bigger_color=element_color; int bigger_idx=element_idx; // for(int i=1;i<n;i++) printf("%d ",rank_to_val(ALL,i)); // printf("\n#%d %d %d %d %d %d\n",cur_appe, cur_color, cur_idx, bigger_appe, bigger_color, bigger_idx); if(bigger_color==-1) return; 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); // printf("require %d %d %d\n",c,d,t); int mi=rank_to_val(ALL,1); int ma=rank_to_val(ALL,n); int mi_ele=rank_to_val(root[c],1); int mi_ele_idx=element_idx; int ma_ele=rank_to_val(root[c],Num[c]); int ma_ele_idx=element_idx; /* 1 9 11 27 26 3 45 4 55 66 7 8 0 0 2 2 0 3 0 1 2 0 3 4 ----- */ // printf("%d %d %d %d %d %d\n", mi ,ma ,mi_ele, ma_ele, mi_ele_idx, ma_ele_idx); int new_val, old_val, target_idx; if(d){ //max old_val=ma_ele; target_idx=ma_ele_idx; }else{ //min old_val=mi_ele; target_idx=mi_ele_idx; } if(t){ //ma+1 new_val=ma+1; }else{ //mi-1 new_val=mi-1; } // printf("%d %d %d\n",new_val, old_val,target_idx); 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; // for(int i=0;i<n;i++) printf("%d ",info[i].appetite); // printf("\n"); // for(int i=0;i<n;i++) printf("%d ",info[i].color); // printf("\n"); // for(int i=1;i<=Num[c];i++) printf("%d ",rank_to_val(root[c],i)); // printf("%d ",rank_to_val(ALL,6)); // for(int i=1;i<=n;i++) printf("%d ",rank_to_val(ALL,i)); // printf("\n"); return ; } 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++){ COLOR_HASH[i]=COLOR_HASH[i-1]; if(color_sorted[i]!=color_sorted[i-1]) COLOR_HASH[i]++; Num[COLOR_HASH[i]]++; } color_cnt=COLOR_HASH[n]; 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); } // suff_equal(root[2],27); // printf("%d",element_idx); // return 0; // printf("%d",rank_to_val(ALL,1)); // return 0; // for(int i=0;i<n;i++) printf("%d %d %d %d\n",info[i].idx,info[i].color,info[i].appetite,HASH[i]); // printf("\n"); // for(int i=1;i<=Num[0];i++) printf("%d ",rank_to_val(root[0],i)); // return 0; // printf("%d ",rank_to_val(root[0],2)); // printf("\n"); // return 0; 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]); // printf("\n"); // printf("after:%d\n",x); // for(int i=1;i<=n;i++) printf("%d ",rank_to_val(ALL,i)); // printf("######\n"); // for(int i=0;i<n;i++) printf("%d ",info[i].appetite); // printf("-----\n"); // for(int i=0;i<n;i++) printf("%d ",info[i].color); // printf("-----\n"); } } /* 12 60 1 9 11 27 26 3 45 4 55 66 7 8 22 22 42 42 22 52 22 32 42 22 52 49494949 2 5 3 42 1 1 3 49494949 1 1 3 32 1 1 3 49494949 0 0 1 22 0 87 3 42 1 0 3 49494949 1 0 2 2 3 49494949 1 1 2 2 3 49494949 0 1 1 52 -3 206 3 42 1 1 3 52 0 0 3 32 1 0 1 42 16 222 2 1 3 49494949 1 1 1 22 4 213 3 49494949 1 0 3 52 1 0 3 49494949 0 1 2 5 3 32 1 0 1 52 14 154 3 32 0 0 3 22 1 0 2 7 3 52 1 1 1 62 -8 48 3 32 0 0 2 6 3 32 0 0 3 22 1 1 3 32 0 0 1 22 6 54 1 42 13 163 3 32 1 0 2 0 1 52 -10 5 1 52 -3 4 3 52 0 0 3 49494949 0 0 2 2 3 49494949 0 1 1 62 -8 117 1 42 10 223 1 52 17 132 2 2 2 3 3 49494949 1 0 2 0 3 49494949 0 0 2 6 2 7 3 22 0 0 1 62 13 158 3 42 1 0 3 49494949 0 1 */