Untitled
unknown
c_cpp
2 years ago
9.5 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, 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
*/