需要注意一些细节

懵逼的 题目

传送至 HDU

扯淡的 题解

case打成canse错了整整两页显得非常开心

怀疑人生.jpg

啊…总的来说是一道很简单的权值线段树裸题...@丁虚高
比起逆序对就是多了一个出队(修改值为0就好了)…
然后二分找中位数…
cx(le, ri, k)可以返回在[le, ri]区间中第k大的数(离散化后的值)
设区间中点为mi = (le + ri) >> 1
如果在区间[le, mi]中比mi小的数(b[LS(dq)].zh)大于等于给定的k, 那么说明区间内第k大的数肯定在左子区间内, 否则左区间内比zh[k]小的数不足k个, 则说明zh[k]一定在右子区间才能满足是区间的第k

没了, 注意两个细节:

  • Case不是Canse23333333333
  • 初始化, 注意输入的值可能为0, 所以不能把输入的数组初始化为0, 而且输入数组是一定要初始化的, 因为有的时间点没有in不会覆盖之前的值

还有…这个题真的很值得吐槽啊!!! QAQ

这里写图片描述

注: 按照第一次出场顺序分别为 张飞, 赵云, 关羽, 马超, 黄忠

GG

沙茶的 代码

// HDU5249

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define MAXN (10000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct node
{
    int le;
    int ri;
    int zh;
} b[MAXN << 2];

int n;
int dqn;
char srs[MAXN][20];
int srx[MAXN], c[MAXN];

void init();
void solve();
void js(int, int, int);
void xg(int, int, int);
int cx(int, int, int);
int cx2(int, int, int, int);
bool cmp(int, int);
int main()
{
#define DEBUG

#ifdef DEBUG
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
#endif
//    ios::sync_with_stdio(false);
//    cin.tie(NULL);
    int ca = 0;
    while (~scanf("%d", &dqn))
    {
        printf("Case #%d:\n", ++ca);
//        cout << "Case #" << ++ca << ":" << endl;
        init();
        solve();
    }
    return 0;
}
void init()
{
    memset(srx, -1, sizeof(srx));
    memset(c, 0x7f, sizeof(c));
    c[0] = 0;
    for (int i = 1; i <= dqn; i++)
    {
        scanf("%s", srs[i]);
//        cin >> srs[i];
        if (srs[i][0] == 'i')
        {
//            cin >> srx[i];
            scanf("%d", &srx[i]);
            c[++c[0]] = srx[i];
        }
    }
    n = c[0];
    sort(c + 1, c + n + 1, cmp);
    n = unique(c + 1, c + n + 1) - c - 1;
    for (int i = 1; i <= dqn; i++)
    {
        if (srx[i] >= 0)
            srx[i] = lower_bound(c + 1, c + n + 1, srx[i]) - c;
    }
    js(1, 1, n);
}
void solve()
{
    queue<int> q;
    for (int i = 1; i <= dqn; i++)
    {
        if (srs[i][0] == 'i')
        {
            q.push(srx[i]);
            xg(1, srx[i], 1);
        }
        else if (srs[i][0] == 'q')
            cout << c[cx2(1, 1, n, q.size() / 2 + 1)] << endl;
        else if (srs[i][0] == 'o')
        {
            xg(1, q.front(), -1);
            q.pop();
        }
    }
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri, b[dq].zh = 0;
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
void xg(int dq, int wz, int zh)
{
    if (b[dq].le == b[dq].ri && b[dq].le == wz)
    {
        b[dq].zh += zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi)
        xg(LS(dq), wz, zh);
    else
        xg(RS(dq), wz, zh);
//    (wz <= mi) ? (xg(LS(dq), wz, zh)) : (xg(RS(dq), wz, zh));
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
/*int cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    // return ((ri <= mi) ? cx(LS(dq), le, ri) : ((le > mi) ? cx(RS(dq), le, ri) : (cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri))))
    if (le > mi)
        return cx(RS(dq), le, ri);
    else if (ri <= mi)
        return cx(LS(dq), le, ri);
    else
        return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}*/
int cx2(int dq, int le, int ri, int k)
{
    if (le == ri)
        return ri;
    int mi = /*(le + ri) >> 1*/(b[dq].le + b[dq].ri) >> 1;
    int x = /*cx(1, le, mi)*/b[LS(dq)].zh;
    if (k > x)
        return cx2(RS(dq), mi + 1, ri, k - x);
    else
        return cx2(LS(dq), le, mi, k);
}
bool cmp(int x, int y)
{
    return x < y;
}

/*
6
in 874
query
out
in 24622
in 12194
query
*/

By 心态略崩的 Cansult