成全高清视频免费观看动漫版-成全视频动漫免费高清-午夜不卡久久精品无码免费

1 题目给定三种操作: 0 x 表示把x插入容器 ; 1 x 表示删除一个x如果没有x则输出 No Elment! ; 2 a k 表示比a大的数中的第k大的数如果没有输出No Find!

2 我们先来看一下树状数组的功能，树状数组能够在在logN的时间内求出某段区间的和，那么对于2 a k这种操作我们可以看成是求是否有x满足[a,x]这个区间的和为k，那么这样就变成了树状数组的求和问题了。那我们再来考虑插入和删除操作，插入一个x相当于更新树状数组，删除x注意多个的情况

3 通过第2点的分析我们知道我们主要是否有区间[a , x]的和为k，那么我们知道对于树状数组来说从a开始的区间的和是递增的，因此我们可以通过二分答案，然后去求出满足的x

4 那么我们来分析一下时间复杂度，枚举操作为O(n)，每次操作的最坏时间为O(logN)，因此时间复杂度为O(n*logN);

/*********************************************** 
* By: chenguolin                               *  
* Date: 2013-08-20                             * 
* Address: http://blog.csdn.net/chenguolinblog * 
***********************************************/
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
const int MAXN = 100010; 
  
int n; 
bool vis[MAXN]; 
int treeNum[MAXN]; 
  
int lowbit(int x){ 
    return x&(-x); 
} 
  
int getSum(int x){ 
    int sum = 0; 
    while(x){ 
         sum += treeNum[x]; 
         x -= lowbit(x); 
    } 
    return sum; 
} 
  
void add(int x , int val){ 
    while(x < MAXN){ 
         treeNum[x] += val; 
         x += lowbit(x); 
    } 
} 
  
int search(int l , int x){ 
    int left = l+1; 
    int right = MAXN-1; 
    while(left <= right){ 
        int mid = (left+right)>>1; 
        int sum = getSum(mid)-getSum(l); 
        if(sum == x){ 
            if(vis[mid]) 
               return mid; 
            right = mid-1; 
        } 
        else if(sum < x) 
            left = mid+1; 
        else{ 
            if(getSum(mid-1)-getSum(l) < x) 
                return mid; 
            right = mid-1; 
        } 
    } 
    return -1; 
} 
  
void solve(){ 
    int mark , x , y; 
    memset(vis , false , sizeof(vis)); 
    memset(treeNum , 0 , sizeof(treeNum)); 
    for(int i = 0 ; i < n ; i++){ 
        scanf("%d" , &mark);  
        if(mark == 0){ 
            scanf("%d" , &x); 
            add(x , 1); 
            vis[x] = true; 
        } 
        else if(mark == 1){ 
            scanf("%d" , &x); 
            int sum = getSum(x)-getSum(x-1); 
            if(sum == 0) 
                puts("No Elment!"); 
            else{ 
                add(x , -1); 
                if(sum == 1) 
                   vis[x] = false; 
            } 
        } 
        else{ 
            scanf("%d%d" , &x , &y); 
            int ans = search(x , y); 
            if(ans == -1) 
                puts("Not Find!"); 
            else
                printf("%d\n" , ans); 
        } 
    } 
} 
  
int main(){ 
    while(scanf("%d" , &n) != EOF) 
         solve();          
    return 0; 
}

·2024年9月目录
·2024年8月目录
·2024年7月目录
·2024年6月目录
·2024年5月目录
·2024年4月目录
·2024年3月目录
·2024年2月目录
·2024年1月目录
·2023年12月目录
·2023年11月目录
·2023年10月目录
·2023年9月目录
·2023年8月目录