题目描述
小明家有n个信箱，前前后后来送信和取信的总次数为q，称为q次访问，其中这q次访问分成三种类型。
1：邮递员送来了一封信，放在了x号信箱。
2：小明取走了x号信箱的所有信（x信箱可能已经没有信了）。
3：小明取走了前t封送来的信（前t封表示从送来的第一封到送来的第t封，其中这t封信可能已经通过第二类或者之前的第三类访问取走了）
小明现在想要知道每一次访问之后，有多少封信时没有取走的，由于送来的信太多，小明想请学oi的你来解答。
输入
输入文件B.in
第一行两个整数n，q。
接下来q行，每行最开始一个整数type
若type=1紧接着一个整数x，表示第一类操作。
若type=2紧接着一个整数x，表示第二类操作。
若type=3紧接着一个整数t，表示第三类操作。
输出
输出文件B.out
对于每一次访问，输出访问结束时剩下多少信还没有被取走。
样例输入
3 4
1 3
1 1
1 2
2 3
样例输出
1
2
3
2
提示
【样例输入2】
4 6
1 2
1 4
1 2
3 3
1 3
1 3
【样例输出2】
1
2
3
0
1
2
【数据范围】
对于30%的数据，$ n，q le 1000 (
对于另外20%的数据，没有三操作。
对于100%的数据，) n，q le 300000 $
这个题说来我挺zz的,完全不知道自己在想什么.....
直接线段树 + 链表就能怼过去的事,结果我非要写线段树 + 时间戳 + 删除线段
这不是给自己找麻烦嘛....于是写了一会儿果断放弃(反正本来也不太会)
于是就开始 (YY) 怎么写链表了,写的时候被自己蠢到哭,单点修改非要写成左右端点相同的区间修改
觉得不用自上向下更新,就死活不想写 $ tag $ ,结果就是一直WA.....
改正之后好歹能过了~~
用线段树维护链表,其实是一堆链表...有点邻接表的意思
然后每次操作是对链表的,注意 $ 2 $ 操作别忘了把一整个链表删干净...最后别忘了重置链表
$ 3 $ 操作直接在线段树上区间修改就行了,也不难
$ 1 $ 操作先在插入链表再更新至线段树,注意线段树维护的是链表就行了
代码如下:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define Noip2018RpINF return 0
#define ls ( rt << 1 )
#define rs ( rt << 1 | 1 )
#define mid ( ( l + r ) >> 1 )
#define pushup(rt) t[rt].data = t[ls].data + t[rs].data
#define LL long long
const LL N = 3e5 + 5 ;
struct seg{
LL left , right ;
LL data , tag;
}t[ ( N << 2 ) ];
LL n , m , x , tot ;
LL opt , pre[N] , nxt[N] ;
inline void build ( LL rt , LL l , LL r ){
t[rt].left = l ; t[rt].right = r ;
if ( l == r ) return ;
build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ;
pushup(rt) ; return ;
}
inline void insert (LL rt , LL pos){
LL l = t[rt].left , r = t[rt].right ;
if ( l == r ) { t[rt].data = 1 ; return ; }
if ( pos <= mid ) insert ( ls , pos ) ;
else if ( pos > mid ) insert ( rs , pos );
pushup (rt) ; return ;
}
inline void delet (LL rt , LL ll , LL rr){
if (t[rt].tag) return ;//现在来看,不写tag真是太zz了
LL l = t[rt].left , r = t[rt].right ;
if ( ll <= l && r <= rr ) { t[rt].data = 0 ; t[rt].tag = 1 ; return ; }
if ( ll <= mid ) delet( ls , ll , rr );
if ( rr > mid ) delet( rs , ll , rr );
pushup(rt) ; return ;
}
inline void Rinsert (LL x){
nxt[++tot] = pre[x] ; pre[x] = tot ;
insert( 1 , tot ) ; return ; //把修改tot写成修改x真是太zz了
}
inline void Rdelete (LL x){
for (int i = pre[x] ; i ; i = nxt[i] )
delet( 1 , i , i );
pre[x] = 0 ;//忘了归零真是太zz了
return ;
}
int main(){
scanf ("%lld%lld" , & n , & m );
build( 1 , 1 , m ) ;//忘了建树真是太zz了(太真实了)
while ( m -- ){
scanf ("%lld%lld" , & opt , & x ) ;
if ( opt == 1 ) Rinsert ( x ) ;
if ( opt == 2 ) Rdelete ( x ) ;
if ( opt == 3 ) delet( 1 , 1 , x ) ;
printf ("%lld
" , t[1].data ) ;
}
Noip2018RpINF ;
}