首页 > 代码库 > 【HDU】5249-KPI(线段树+离散化)
【HDU】5249-KPI(线段树+离散化)
好久没写线段树都不知道怎么写了。。。
很easy的线段树二分问题
#include<cstdio> #include<set> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; #define lson (pos<<1) #define rson (pos<<1|1) const int maxn = 10005; int n,Case = 1; char op[10]; int Hash[maxn]; int cnt; struct In{ int op,v; }in[maxn]; int HASH(int x){ return lower_bound(Hash,Hash + cnt,x) - Hash + 1; } int sum[maxn << 2]; void pushup(int pos){ sum[pos] = sum[lson] + sum[rson]; return; } void update(int L,int R,int m,int pos,int value){ if(L == R){ sum[pos] = value; return; } int mid = (L + R) >> 1; if(m <= mid) update(L,mid,m,lson,value); else update(mid + 1,R,m,rson,value); pushup(pos); return; } int query(int L,int R,int value,int pos){ if(L == R) return L; int mid = (L + R) >> 1; if(sum[lson] >= value) return query(L,mid,value,lson); else return query(mid + 1,R,value - sum[lson],rson); } int main(){ while(scanf("%d",&n) != EOF){ printf("Case #%d:\n",Case++); cnt = 0; queue<int>q; memset(sum,0,sizeof(sum)); for(int i = 0; i < n; i++){ scanf("%s",op); if(op[0] == ‘i‘){ in[i].op = 1; scanf("%d",&in[i].v); Hash[cnt++] = in[i].v; } else if(op[0] == ‘o‘) in[i].op = 2; else if(op[0] == ‘q‘) in[i].op = 3; } sort(Hash,Hash + cnt); cnt = unique(Hash,Hash + cnt) - Hash; for(int i = 0; i < n; i++){ if(in[i].op == 1){ int e = HASH(in[i].v); q.push(e); update(1,cnt,e,1,1); } else if(in[i].op == 2){ int e = q.front(); q.pop(); update(1,cnt,e,1,0); } else if(in[i].op == 3){ int f = sum[1]; int fx = f / 2 + 1; int pos = query(1,cnt,fx,1); printf("%d\n",Hash[pos - 1]); } } } return 0; } /* 10 in 1 in 2 in 3 in 4 in 5 o q o q q */
【HDU】5249-KPI(线段树+离散化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。