树状数组求第K大+离散化入门例题

我就是我 2022-02-23 13:06 217阅读 0赞

## 洛谷3369 ##

## 题目描述 ##

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1.  插入xx数
2.  删除xx数(若有多个相同的数，因只删除一个)
3.  查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)
4.  查询排名为xx的数
5.  求xx的前驱(前驱定义为小于xx，且最大的数)
6.  求xx的后继(后继定义为大于xx，且最小的数)

## 输入输出格式 ##

**输入格式：**

第一行为nn，表示操作的个数,下面nn行每行有两个数optopt和xx，optopt表示操作的序号( 1 \\leq opt \\leq 61≤opt≤6 )

**输出格式：**

对于操作3,4,5,63,4,5,6每行输出一个数，表示对应答案

## 输入输出样例 ##

**输入样例\#1：** 复制

10
    1 106465
    4 1
    1 317721
    1 460929
    1 644985
    1 84185
    1 89851
    6 81968
    1 492737
    5 493598

**输出样例\#1：** 复制

106465
    84185
    492737

#include<bits/stdc++.h>
    using namespace std;
    //思路  离散化  之后插入删除都是离散化之后的数据 查询排名即是查询和  查询第几名是所 规划发布 
    int n,opt[100001],res[100020],tot,val[102200],num[100201],sz;
    int pos(int x){
    	return lower_bound(num+1,num+sz+1,x)-num;//离散化 
    }
    void add(int x,int k){
    	while(x<=sz)res[x]+=k,x+=x&-x;//修改个数 
    } 
    int sum(int x){
    	int ans=0;
    	while(x)ans+=res[x],x-=x&-x;
    	return ans;//小于这个数字的个数 
    }
    int find_k(int x){//找到第X小 
    	int ans=0;//结果下标记 
    	for(int i=20;i>=0;i--){//注意这里：i是次方数，2的0次方为1 
    		ans+=1<<i;
    		if(ans>sz||res[ans]>=x)ans-=1<<i;//找出小于该数的最大的二进制数 直到找到最大的<x的那个数的位置ans ，ans投射到离散数组里num就是对应的数，我们只需要把ans+1 
    		else x-=res[ans];
    	}
    	return num[ans+1];
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%d%d",&opt[i],&val[i]);
    		if(opt[i]!=4)num[++tot]=val[i];		
    	}	
    	sort(num+1,num+tot+1);
    	sz=unique(num+1,num+1+tot)-num-1;
    	for(int i=1;i<=n;i++){
    		int x=val[i];
    		switch(opt[i]){
    			case 1:add(pos(x),1);break;
    			case 2:add(pos(x),-1);break;
    			case 3:printf("%d\n",sum(pos(x)-1)+1);break;
    			case 4:printf("%d\n",find_k(x));break;
    			case 5:printf("%d\n",find_k(sum(pos(x)-1)));break;
    			case 6:printf("%d\n",find_k(sum(pos(x))+1)); break;
    		}
    	}
    	return 0;
    }