51nod2014

核心思路

解决这道题需要面对两个问题。首先是如何求或修改某一区间的小朋友的状态,这可以用线段树解决;其次是如何知道某一个(段)小朋友已经听过这个笑话,这个问题可以用 max{l}\max\{l\} 个set维护。

具体的操作是这样。首先得到了一段 [xk,x+k][x-k,x+k] 的区间,将这个区间内的所有数修改为 11,再将这个区间与对应笑话的set取并,将交集部分修改为 00 。取交集的操作是,先找到第一个包含于 [xk,x+k][x-k,x+k] 的区间,然后向后增加指针直至离开 [xk,x+k][x-k,x+k] 这一区间。

set中最多出现 nn 个区间,查找到第一个需要 nlognn\log n ,从那往后最多经历 nn 个区间,修改每一个区间的复杂度为 logn\log n,因此总的复杂度为 O(nlogn)O(n\log n)

完整代码

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;
}

评论