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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
int read() {
int x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
namespace Brute {
const int MAXN=1e4+10;
bool mark[MAXN][MAXN],sta[MAXN];
void main() {
REP(i,1,m) {
int op=read();
if(op==1) {
int x=read(),l=read(),k=read();
REP(j,max(1,x-k),min(n,x+k)) {
if(mark[j][l]) sta[j]=0;
else sta[j]=1;
mark[j][l]=1;
}
}
else {
int l=read(),r=read(),ans=0;
REP(j,l,r) ans+=sta[j];
printf("%d\n",ans);
}
}
}
}
namespace AC {
const int MAXN=1e5+10;
set<pair<int,int> > s[MAXN];
struct SegmentTree {
int lf[MAXN<<2],rg[MAXN<<2],add[MAXN<<2],sum[MAXN<<2],a[MAXN<<2];
#define l(x) lf[x]
#define r(x) rg[x]
#define len(x) (rg[x]-lf[x]+1)
void pushup(int p) {sum[p]=sum[p*2]+sum[p*2+1];}
void pushdown(int p) {
if(add[p]!=-1) {
add[p*2]=add[p];
add[p*2+1]=add[p];
sum[p*2]=add[p]*len(p*2);
sum[p*2+1]=add[p]*len(p*2+1);
add[p]=-1;
}
}
void build(int p,int l,int r) {
l(p)=l,r(p)=r;
if(l==r) {sum[p]=0,add[p]=-1;return ;}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void change(int p,int l,int r,int d) {
if(l(p)>=l&&r(p)<=r) {
sum[p]=d*len(p);
add[p]=d;
return ;
}
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid) change(p*2,l,r,d);
if(r>mid) change(p*2+1,l,r,d);
pushup(p);
}
int ask(int p,int l,int r) {
if(l(p)>=l&&r(p)<=r) return sum[p];
int ans=0;
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid) ans+=ask(p*2,l,r);
if(r>mid) ans+=ask(p*2+1,l,r);
return ans;
}
} seg;
#define mp(a,b) make_pair(a,b)
void main() {
seg.build(1,1,n);
REP(i,1,m) {
int op=read();
if(op==1) {
int x=read(),L=read(),k=read(),l=max(1,x-k),r=min(n,x+k),nowl=l,nowr=r;
if(s[L].size()) {
set<pair<int,int> >::iterator it=s[L].lower_bound(mp(l,0));
set<pair<int,int> >::iterator pre=it;
if(it!=s[L].begin()) {
pre--;
if((*pre).second>=l) it=pre;
}
if(it==s[L].end()||(*it).first>r) {
s[L].insert(mp(l,r));
seg.change(1,l,r,1);
}
else {
nowl=min(nowl,(*it).first);seg.change(1,l,r,1);
seg.change(1,l,r,1);
while(it!=s[L].end()&&(*it).first<=r) {
seg.change(1,max(l,(*it).first),min(r,(*it).second),0);
nowr=max(nowr,(*it).second);
pre=it,it++;s[L].erase(pre);
}
s[L].insert(mp(nowl,nowr));
}
}
else {
seg.change(1,l,r,1);
s[L].insert(mp(l,r));
}
}
else {
int l=read(),r=read();
printf("%d\n",seg.ask(1,l,r));
}
}
}
}
int main() {
n=read(),m=read();
AC::main();
return 0;
}
|
