第七屆浙江省賽C題
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3749

         比賽的時候還是很容易就想到了“線段樹+離散化”，說明之前一些線段樹的題目做了還是有效果的。但是接下來就是悲劇的時刻，沒有想清楚怎么離散化，還有就是更新的函數，構造不出來，知道“線段樹+離散化”又有什么用呢？唉，對線段樹理解地不夠深刻的。。。由于比賽中這道題目的AC率不高，我們隊還有一些很多人通過的題沒有AC，我就立馬放棄了這道題，想最后還有時間的話，再來想想。 跟預想的一樣，比賽的時候是沒有時間再看這道題了。
        比賽結束之后，看到了解題報告，后來又參看了http://boskijr.is-programmer.com/posts/17295.html#more Boski Jr.的代碼，然后終于AC了。
        學到了一招比較好的離散化的方式，使用半開半必的區間，比如 [ a , b ]  可以用 [ a, b+1 ) 來代替，可以省下不少空間呢。
        以下是我的代碼：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

struct node 
{
    int s,t;
    char op[3];
};
struct segment
{
    int l,r;
    int left,right; // 記錄區間兩端的高度
    int flag;       // 記錄整段區間被下壓的次數
    int count;      // 記錄區間中處于高度0的條數
};

const int maxn = 21000;
node a[maxn];
segment tree[maxn<<3];
int lisan[maxn<<1]; 

void make_tree( int v, int l, int r )
{
    int mid;
    tree[v].l = l, tree[v].r = r;
    tree[v].flag = tree[v].left = tree[v].right = 0;
    tree[v].count = 1;
    if( l + 1 != r )
    {
        mid = ( l + r ) >> 1;
        make_tree( v<<1, l, mid );
        make_tree( ( v<<1 ) + 1, mid, r );
    }
}

void update( int v, int s, int t, int c )
{
    int mid;
    if( lisan[tree[v].l] == s && lisan[tree[v].r] == t )
    {
        tree[v].flag += c;
        tree[v].left += c;
        tree[v].right += c;
        if( tree[v].flag )    // 如果區間高度不是0，說明被下壓，沒有0線段
            tree[v].count = 0; 
        else                  // 葉子節點 
            if( tree[v].l + 1 == tree[v].r ) 
            tree[v].count = 1;
        else                  // 一般節點
            tree[v].count = tree[v<<1].count + tree[(v<<1)+1].count -
            ( tree[v<<1].right == 0 && tree[(v<<1)+1].left == 0 );
        return ;
    }
    mid = ( tree[v].l + tree[v].r ) >> 1;
    if( lisan[mid] >= t ) update( v<<1, s, t, c );
    else if( lisan[mid] <= s ) update( (v<<1)+1, s, t, c );
    else 
    {
        update( v<<1, s, lisan[mid], c );
        update( (v<<1)+1, lisan[mid], t, c );
    }
    tree[v].left = tree[v<<1].left + tree[v].flag;
    tree[v].right = tree[(v<<1)+1].right + tree[v].flag;

    if( tree[v].flag ) tree[v].count = 0;
    else 
        tree[v].count = tree[v<<1].count + tree[(v<<1)+1].count -
        ( tree[v<<1].right == 0 && tree[(v<<1)+1].left == 0 );
}

void init( int n, int m )
{
    int i,len=0;
    lisan[len++] = 0;
    lisan[len++] = n;
    for( i = 0; i < m; i++ )
    {
        scanf("%s%d%d",a[i].op,&a[i].s,&a[i].t);
        a[i].t++;
        lisan[len++] = a[i].s;
        lisan[len++] = a[i].t;
    }
    sort( lisan, lisan + len );
    len = unique( lisan, lisan + len ) - lisan;
    make_tree( 1, 0, len-1 );
}

int main( )
{
    int i,t,n,m,k = 1;
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%d",&n,&m);
        init( n, m );
        printf("Case #%d:\n",k++);
        for( i = 0; i < m; i++ )
        {
            update( 1, a[i].s, a[i].t, ( a[i].op[0] == 'p' ? 1 : -1 ) );
            printf("%d\n",tree[1].count);
        }
    }
    return 0;
}