分块思想

---

数据结构：

√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
*/