HDU 5249 离线树状数组求第k大+离散化

时间：2021-10-17 08:22:25

KPI

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1160    Accepted Submission(s): 488

Problem Description
你工作以后, KPI 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。
 
Input
有大约100组数据。

每组数据第一行有一个n(1≤n≤10000)

，代表服务记录数。

接下来有n行，每一行有3种形式
  "in x": 代表重要值为x(0≤x≤109)

的请求被推进管道。
  "out": 代表服务拉取了管道头部的请求。
  "query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有m条请求, 我想知道，升序排序后第floor(m/2)+1th

条请求的重要值.

为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有"out"和"query"操作。

 
Output
对于每组数据，先输出一行

Case #i:
然后每一次"query"，输出当前管道内重要值的中间值。

 
Sample Input
6
in 874
query
out
in 24622
in 12194
query
 
Sample Output
Case #1:
874
24622
 
Source
题意： 三种操作 ”in  x“ 将x 加入到队列
                      ”out“ 删除队头元素
                      ”query“ 队列中现有元素升序排列后 输出第 （ len/2+1） 大元素
题解：1.将所有元素离散化处理 这里的方法比较麻烦 具体看代码有多次映射
         2.根据操作  将离散化后的元素加入 树状数组 in~add（x,1）,out~add(x,-1);
         3.树状数组求第k大 
         f[n] 树状数组
         f[1]=a1
         f[2]=a1+a2
         f[3]=a3
 
 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 #include<algorithm>

 #include<stack>

 #include<queue>

 using namespace std;

 struct node

 {

     int x;

     int y;

 } s[];

 int t;

 int jishu=;

 char a[][];

 int b[];

 int exm;

 int f[];

 int coun=;

 map<int,int> mp;

 map<int,int> mpp;

 queue<int> st;

 int n;

 bool cmp(struct node aa,struct node bb )

 {

     return aa.x<bb.x;

 }

 void add(int x,int y,int n)

 {

         for (;x<=n;x+=x&(-x)) f[x]+=y;

 }

 int sum(int x)

 {

         int ret=;

         for (;x;x-=x&(-x)) ret+=f[x];

         return ret;

 }

 int find_k(int k) //求第k大 板子

 {

         int i,w=;

         for (i=;i>=;i--)

         if (w+(<<i)<=n&&f[w+(<<i)]<k)

         {

             k-=f[w+(<<i)];w+=<<i;

         }

         return w+;

 }

 int k_num(int k){

     int w=,cnt=;

     for(int i=;i>=;i--)

     {  

         w+=(<<i);

         if(w>n || k<=f[w])

         w-=(<<i);

         else

          {

           k-=f[w];

          }

     }

     return w+;

 }

 int main()

 {

        while(scanf("%d",&t)!=EOF)

 {       jishu++;

         memset(s,,sizeof(s));

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(f,,sizeof(f));

         mp.clear();

         mpp.clear();

         while(st.size()>)

          st.pop();

     coun=;

     for(int i=;i<=t;i++)

     {

         scanf("%s",&a[i]);

         if(a[i][]=='i')

         {

             scanf("%d",&exm);

             s[++coun].x=exm;//存插入的元素

             s[coun].y=coun;//struct 存储对应位置

         }

     }

     cout<<"Case #"<<jishu<<":"<<endl;

     sort(s+,s++coun,cmp);//结构体排序 x为主键升序排列

     b[s[].y]=;

     int k=;

      mp[s[].x]=;

      mpp[]=s[].x;

     for(int i=;i<=coun;i++)//for循环完成离散化处理

     {

         if(s[i].x==s[i-].x)

          {

           b[s[i].y]=k;

           mp[s[i].x]=k;// 与元素的相互映射

           mpp[k]=s[i].x;//

          }

         else

          {

          b[s[i].y]=++k;

          mp[s[i].x]=k;

          mpp[k]=s[i].x;

          }

     }

     n=k;

     k=;

     for(int i=;i<=t;i++)

     {

        if(a[i][]=='i')

         {

             st.push(mpp[b[++k]]);

             add(b[k],,n);

         }

         if(a[i][]=='o')

       {

          int now=st.front();

          st.pop();

          add(mp[now],-,n);

       }

       if(a[i][]=='q')

       {

            int len=st.size();

            int location=k_num((len/)+);

            printf("%d\n",mpp[location]);

       }

     }

 }

     return ;

 }

 /*

 10

 in 3

 in 1

 out

 in 4

 query

 in 2

 out

 in 100

 in 1

 query

 */
 
 

相关文章