第七届浙江省赛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( 
10, 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;
}