B1057 Stack(分块,树状数组+二分)

B1057 Stack (30分)

数据范围N ≤10^5​​ ,模拟栈的push和pop的每个过程，求每个过程中栈内元素的中位数。
对于N次查询，使用快排去求中位数O( N * log2(N) ) * O(N)肯定会超时。

//树状数组不是顶级的考纲吗/(ㄒoㄒ)/~~

1.分块

单次查询中位数时间O(N^1/2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX=100005;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
const int sqr=316;//sqrt(100001)向下取整，每块的最大容量。
stack<int>st;
int table[MAX];//hsah
int blocks[sqr];//每个块的当前元素数量
void peekmedian(int k)
{
    int sum=0;
    int idx=0;
    while(sum+blocks[idx]<k)
    {
        sum+=blocks[idx++];
    }
    int num=idx*316;//idx第一个数
    while(sum+table[num]<k)
    {
        sum+=table[num++];
    }
    printf("%d\n",num);
}
void push(int x)
{
      st.push(x);
      blocks[x/sqr]++;
      table[x]++;
}
void pop()
{
    int top=st.top();
    st.pop();
    blocks[top/sqr]--;
    table[top]--;
    printf("%d\n",top);
}
int main()
{
    int n;
    string s,a;
    memset(table,0,sizeof(table));
    memset(blocks,0,sizeof(blocks));
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++)
    {
        cin>>s;
        if(s=="Push")
        {
            int num;
            scanf("%d",&num);
            push(num);
        }
        else if(s=="Pop")
        {
          if(!st.empty())
          {
            pop();
          }
          else
            printf("Invalid\n");
        }
        else if(s=="PeekMedian")
        {
          if(!st.empty())
          {
            int k=st.size();
            int mid;
            if(k%2==1)
                mid=(k+1)/2;
            else
                mid=k/2;
            peekmedian(mid);
          }
          else
            printf("Invalid\n");
        }
    }

    return 0;
}

2.树状数组+二分

对一个序列，用hash记录每个元素出现的个数，那么序列第k大就是求最小的i使得sum(hash[1]~hash(i))>=k成立,用树状数组来解决hash数组求和问题,
等价于求第一个满足getsum(i)>=k的最小i
树状数组求和时间复杂度O(logn),二分查询i时间复杂度O(logn)
总时间O(logn)*O(logn)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX=100005;
const int INF=0x3f3f3f3f;
const int mod=1000000007;
const int sqr=316;//sqrt(100001)向下取整，每块的最大容量。
#define lowbit(i)((i)&(-i))
stack<int>st;
int c[MAX];//树状数组
void update(int x,int v)
{
    for(int i=x;i<=MAX;i+=lowbit(i))
    {
        c[i]+=v;
    }
}
int getsum(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        sum+=c[i];
    }
    return sum;
}
int peekmedian(int k)
{
    int l=1,r=MAX,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(getsum(mid)>=k)
        {
            r=mid;
        }
        else
            l=mid+1;
    }
    return l;

}
void push(int x)
{
    st.push(x);
    update(x,1);
}
void pop()
{
    int top=st.top();
    st.pop();
    printf("%d\n",top);
    update(top,-1);
}
int main()
{
    int n;
    string s,a;
    memset(c,0,sizeof(c));
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++)
    {
        cin>>s;
        if(s=="Push")
        {
            int num;
            scanf("%d",&num);
            push(num);
        }
        else if(s=="Pop")
        {
          if(!st.empty())
          {
            pop();
          }
          else
            printf("Invalid\n");
        }
        else if(s=="PeekMedian")
        {
          if(!st.empty())
          {
            int k=st.size();
            int mid;
            if(k%2==1)
                mid=(k+1)/2;
            else
                mid=k/2;
            printf("%d\n",peekmedian(mid));
          }
          else
            printf("Invalid\n");
        }
    }

    return 0;
}