题解 51nod2014 小朋友的笑话

题解 51nod2014 小朋友的笑话

题面

51nod

解析

考虑维护每个笑话所占的区间,

用线段树统计在笑的人数,每次更新时将当前区间设成 $1$,再将与以前的区间交设为 $0$.

但是暴力维护区间空间会炸,考虑到一次更新会将几个区间合并成一个大的区间.

因此用 $\texttt{set}$ 维护每个笑话的区间,保证维护的区间没有交,

每次更新的时候将有交的区间合并.

这样每个区间只会加入一次,被合并一次.

具体操作可见代码.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <set>
#include <algorithm>
#define ls(a) a<<1
#define rs(a) a<<1|1
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=100005;
struct tree{int l,r,sum,tag;}t[N<<2];
int n,m,f[N];
set< pair<int,int> > s[N];
set< pair<int,int> >::iterator it,tmp;

inline void pushup(int p){
t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}

inline void pushdown(int p){
if(t[p].tag==-1) return ;
t[ls(p)].tag=t[rs(p)].tag=t[p].tag;
t[ls(p)].sum=t[p].tag*(t[ls(p)].r-t[ls(p)].l+1);
t[rs(p)].sum=t[p].tag*(t[rs(p)].r-t[rs(p)].l+1);
t[p].tag=-1;
}

inline void build(int p,int l,int r){
t[p].l=l;t[p].r=r;t[p].tag=-1;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls(p),l,mid);build(rs(p),mid+1,r);
pushup(p);
}

inline void change(int p,int l,int r,int x){
if(t[p].l>=l&&t[p].r<=r){
t[p].sum=(t[p].r-t[p].l+1)*x;t[p].tag=x;
return ;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(ls(p),l,r,x);
if(r>mid) change(rs(p),l,r,x);
pushup(p);
}

inline int query(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1,ret=0;
if(l<=mid) ret+=query(ls(p),l,r);
if(r>mid) ret+=query(rs(p),l,r);
pushup(p);
return ret;
}

inline void solve(int L,int R,int x){
if(s[x].empty()){
s[x].insert(make_pair(L,R));
change(1,L,R,1);return ;
}
int l=L,r=R;
it=s[x].lower_bound(make_pair(L,0));
if(it!=s[x].begin()) it--;
while(it!=s[x].end()&&(*it).second<L) it++;
change(1,L,R,1);
if(it==s[x].end()){s[x].insert(make_pair(L,R));return ;}
while(it!=s[x].end()&&(*it).first<=R){
change(1,max((*it).first,L),min((*it).second,R),0);
l=min(l,(*it).first);r=max(r,(*it).second);
tmp=it;it++;s[x].erase(tmp);
}
s[x].insert(make_pair(l,r));
}

int main(){
n=read();m=read();build(1,1,n);
while(m--){
int op=read();
if(op==1){
int x=read(),l=read(),k=read();
solve(max(x-k,1),min(x+k,n),l);
}
else if(op==2){
int l=read(),r=read();
printf("%d\n",query(1,l,r));
}
}
return 0;
}
感谢您又打赏