Segment Game（樹狀數組）

暫時存下代碼，細節有的沒處理好。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 4e5+5;

int p[maxn], a[maxn], b[maxn], num[maxn];

int cnt, s[2][maxn];

int bit(int x)

{

    return x & (-x);

}

void add(int x, int d, int o)

{

    while(x <= cnt) {

        s[o][x] += d;

        x += bit(x);

    }

}

int sum(int x, int o)

{

    int ret = 0;

    while(x > 0) {

        ret += s[o][x];

        x -= bit(x);

    }

    return ret;

}

int main()

{

    int n, ca = 0;

    while(~scanf("%d", &n)) {

        cnt = 0;

        int c = 0;

        for(int i = 1; i <= n; ++i)

        {

            scanf("%d %d", &p[i], &a[i]);///b是

            if(!p[i])///進行加邊（點）操作

            {

                b[i] = a[i]+ (++c);

                num[cnt++] = a[i];

                num[cnt++] = b[i];

            }

        }

        sort(num, num+cnt);///先進行一下排序操作

        cnt = unique(num, num + cnt ) - num;///代表去掉重複的之後剩下的個數

        memset(s, 0, sizeof(s));

        int ad = 1;

        printf("Case #%d:\n", ++ca);

        for(int i = 1; i <= n; ++i)

        {

            if(p[i] == 0)

            {

                int aa = lower_bound(num, num+cnt, a[i]) - num + 1;

                int bb = lower_bound(num, num+cnt, b[i]) - num + 1;

                printf("%d\n", sum(bb, 1) - sum(aa-1, 0));

                a[ad] = aa;///a數組記錄第幾次操作的右端點

                b[ad++] = bb;///b數組記錄左端點

                add(aa, 1, 0);

                add(bb, 1, 1);

            }

            else

            {

                add(a[a[i]], -1, 0);

                add(b[a[i]], -1, 1);

            }

        }

    }

    return 0;

}