ZOJ 3612 树状数组 第K大数

题意就是有大约1-10000个操作，每次插入或者删除一个数，每次操作后的中位数都要输出

然后思路就比较清晰了， 先把数据都读进来，所有的数存起来离散化，然后再处理每个操作，每次维护树状数组即可，然后如果整个序列有奇数个，就直接二分找最中间的，如果偶数个就找两个数。

这题比较恶心的就是输出了。用cout按理说最好了，但是会超时，用long long的话，除以2的时候判奇数输出.5也会挂，除非转换成double然后%.1f不会挂，这一点很费解啊。当然直接用double转化为字符串是不可能挂的。

保险点用double 吧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 10005
#define MAXM 1000005
#define INF 1000000000
#define eps 1e-6
using namespace std;
int op[MAXN];
int n, a[MAXN], t[MAXN];
double x[MAXN], num[MAXN];
int lowbit(int x)
{
    return x & -x;
}
void modify(int x, int v)
{
    for(int i = x; i <= n; i += lowbit(i))
        a[i] += v;
}
int getsum(int x)
{
    int sum = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        sum += a[i];
    return sum;
}
int find(double val, int low, int high)
{
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        if(fabs(x[mid] - val) < eps) return mid;
        if(x[mid] > val) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}
int median(int val, int low, int high)
{
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        int sum = getsum(mid);
        if(sum >= val) high = mid - 1;
        else low = mid + 1;
    }
    return low;
}
void output(double val)
{
    if(floor(val) == val)
    printf("%.0f\n", val);
    else
    {
        char s[55];
        sprintf(s, "%f", val);
        int len = strlen(s);
        int pos = len - 1;
        for(int i = len - 1; i >= 0; i--)
        {
            if(s[i] != '0' || i == 0)
            {
                pos = i;
                break;
            }
        }
        for(int i = 0; i <= pos; i++) putchar(s[i]);
        putchar('\n');
    }
}
int main()
{
    int T;
    char s[22];
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%s%lf", s, &num[i]);
            if(s[0] == 'r') op[i] = 0;
            else op[i] = 1;
            x[i] = num[i];
        }
        sort(x + 1, x + n + 1);
        int f = n;
        n = unique(x + 1, x + n + 1) - x - 1;
        memset(a, 0, sizeof(a));
        memset(t, 0, sizeof(t));
        for(int i = 1; i <= f; i++)
        {
            if(op[i])
            {
                int pos = find(num[i], 1, n);
                modify(pos, 1);
                t[pos]++;
                int len = getsum(n);
                if(len % 2 == 1)
                {
                    double k = x[median(len / 2 + 1, 1, n)];
                    output(k);
                }
                else
                {
                    double k1 = x[median(len / 2, 1, n)];
                    double k2 = x[median(len / 2 + 1, 1, n)];
                    output((k1 + k2) / 2);
                }
            }
            else
            {
                int pos = find(num[i], 1, n);
                if(t[pos] < 1) printf("Wrong!\n");
                else
                {
                    t[pos]--;
                    modify(pos, -1);
                    int len = getsum(n);
                    if(len == 0) printf("Empty!\n");
                    else if(len % 2 == 1)
                    {
                        double k = x[median(len / 2 + 1, 1, n)];
                        output(k);
                    }
                    else
                    {
                        double k1 = x[median(len / 2, 1, n)];
                        double k2 = x[median(len / 2 + 1, 1, n)];
                        output((k1 + k2) / 2);
                    }
                }
            }
        }
    }
    return 0;
}