学步园

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 111111;
int T, L, n;
int sum[maxn<<2];

void build(int rt, int l, int r)
{
    sum[rt] = 0;
    if (l == r)
        return ;
    int m = (l + r) >> 1;
    build(rt << 1, l, m);
    build(rt << 1 | 1, m + 1, r);
}

void update(int rt, int l, int r, int p, int val)
{
    if (l == p && r == p)
    {
        sum[rt] += val;
        return ;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(rt << 1, l, m, p, val);
    else update(rt << 1 | 1, m + 1, r, p, val);
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

int querySum(int rt, int l, int r, int L, int R)
{
    if (L <= l && R >= r)
        return sum[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret += querySum(rt << 1, l, m, L, R);
    if (R > m) ret += querySum(rt << 1 | 1, m + 1, r, L, R);
    return ret;
}

int queryPos1(int rt, int l, int r, int s)
{
    if (l == r)
        return l;
    int m = (l + r) >> 1;
    if (sum[rt<<1] >= s)
        return queryPos1(rt << 1, l, m, s);
    return queryPos1(rt << 1 | 1, m + 1, r, s - sum[rt<<1]);
}

int queryPos2(int rt, int l, int r, int s)
{
    if (l == r)
        return l;
    int m = (l + r) >> 1;
    if (sum[rt<<1|1] >= s)
        return queryPos2(rt << 1 | 1, m + 1, r, s);
    return queryPos2(rt << 1, l, m, s - sum[rt<<1|1]);
}

int main()
{
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas)
    {
        int dir = 1, curp = 0;
        __int64 ans = 0;
        int op, pp;
        scanf("%d %d", &L, &n);
        build(1, 0, L);
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &op);
            if (op == 0)
            {
                scanf("%d", &pp);
                update(1, 0, L, pp, 1);
            }
            else
            {
                if (sum[1] == 0)
                    continue;
                int s1 = querySum(1, 0, L, 0, curp);
                int s2 = querySum(1, 0, L, curp, L);
                if (s1 == 0)
                {
                    int p2 = queryPos2(1, 0, L, s2);
                    ans += p2 - curp;
                    curp = p2;
                    dir = 1;
                    update(1, 0, L, curp, -1);
                }
                else if (s2 == 0)
                {
                    int p1 = queryPos1(1, 0, L, s1);
                    ans += curp - p1;
                    curp = p1;
                    dir = 0;
                    update(1, 0, L, curp, -1);
                }
                else
                {
                    int p1 = queryPos1(1, 0, L, s1);
                    int p2 = queryPos2(1, 0, L, s2);
                    /*if (p1 == curp || p2 == curp)
                    {
                        update(1, 0, L, curp, -1);
                        continue;
                    }*/
                    if (curp - p1 < p2 - curp)
                    {
                        ans += curp - p1;
                        curp = p1;
                        dir = 0;
                        update(1, 0, L, curp, -1);
                    }
                    else if (curp - p1 > p2 - curp)
                    {
                        ans += p2 - curp;
                        curp = p2;
                        dir = 1;
                        update(1, 0, L, curp, -1);
                    }
                    else
                    {
                        ans += p2 - curp;
                        if (dir == 1)
                        {
                            curp = p2;
                            update(1, 0, L, curp, -1);
                        }
                        else
                        {
                            curp = p1;
                            update(1, 0, L, curp, -1);
                        }
                    }
                }
            }
        }
        printf("Case %d: %I64d\n", cas, ans);
    }
    return 0;
}