美文网首页
分块思想

分块思想

作者: 小幸运Q | 来源:发表于2018-07-15 16:00 被阅读7次

    数据结构:

    √N个块block[0,...,√N - 1],范围是从[k*√N,(k+1)*√N - 1],查询的范围[0,N-1]

    缺点:适用于一个确定范围的插入删除+查询

    相当于维护一个能返回中位数同时支持插入和删除的数据结构。

    image.png

    插入与删除:

    Sign数组记录下标对应的数字的重复次数,
    Block记录block范围内的数字的出现次数之和。

    • 一个数A插入时,int Sign[A]++,int Block[A/sqrtN]++
    • 当A要删除的时候,int Sign[A]--,int Block[A/sqrtN]--

    举个例子:

    // 已存在的元素{0,1,3,4,4,5,8}
    最高是8,所以取9,如果是9,则取16。
    
    // block作为块
    block[0]=2     // 0,1
    block[1]=4     // 3,4,4,5
    block[2]=1     // 8
    
    // table记录同一个值有多少重复的元素
    table[0]=1;
    table[1]=1;
    table[2]=0;
    table[3]=1;
    table[4]=2;
    table[5]=1;
    table[6]=0;
    

    示例代码:

    #include <bits/stdc++.h>
    using namespace std;
    // 最大值
    #define N 100010
    // 块的大小
    const int sqrtN=316;
    
    vector<int>s;
    
    int block[N]={0};
    // 存储块的数据,设为sqrtN会报错....
    int table[N]={0};
    // 存储对应取值的数据
    
    void findMedian(){
      if(s.empty()){
        cout<<"Invalid"<<endl;
        return;
      }
      int i,j;
      int counts=0;
      int target=0;
      if(s.size()&1){
        // 奇数
        target=(s.size()+1)/2;
      }
      else{
        // 偶数
        target=s.size()/2;
      }
      for(i=0;i<sqrtN;i++){
        counts+=block[i];
        if(counts>=target){
          counts-=block[i];
          // 计算第K个值可能的开始-结束的值
          int bottom=i*sqrtN;
          int hign=(i+1)*sqrtN-1;
    
          for(j=bottom;j<=hign;j++){
            counts+=table[j];
            if(counts>=target){
              printf("%d\n",j);
              return ;
            }
          }
        }
      }
    }
    void Push(int num){
      table[num]++;
      block[num/sqrtN]++;
      s.push_back(num);
    }
    void Popup(){
      if(s.empty()){
        printf("Invalid\n");
        return;
      }
      int tp=s[s.size()-1];
      s.pop_back();
      // 点值--
      table[tp]--;
      // 块值--
      block[tp/sqrtN]--;
      printf("%d\n",tp);
    }
    int main(){
      int i,j;
      int times;
      char input[100];
    
      char Pop[]="Pop";
      char PeekMedian[]="PeekMedian";
      scanf("%d\n",&times);
      // 必须摘去\n要不然会影响到后面的读取
    
      // 书上的方法只是在该用例输入的时候可以投机取巧,字符串处理最好还是cin.getline(input,N)+string的方式
      for(i=0;i<times;i++){
        scanf("%s",input);
        // 要判断字符串相等需要用string==string,但是用char[]+strcmp更省钱
        if(strcmp(input,Pop)==0){
          Popup();
        }
        else if(strcmp(input,PeekMedian)==0){
          findMedian();
        }
        else{
          int num;
          scanf("%d",&num);
          Push(num);
        }
      }
    }
    /*
    17
    Pop
    PeekMedian
    Push 3
    PeekMedian
    Push 2
    PeekMedian
    Push 1
    PeekMedian
    Pop
    Pop
    Push 5
    Push 4
    PeekMedian
    Pop
    Pop
    Pop
    Pop
    */
    

    相关文章

      网友评论

          本文标题:分块思想

          本文链接:https://www.haomeiwen.com/subject/uihypftx.html