抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

APIO2019毒瘤题记录

发布于：2019年8月25日

T1:

P5444 [APIO2019]奇怪装置

其实这题比较简单，考虑两个数对相同的条件：

x_1==x_2 \text{&&} y_1==y_2

设两个数对对应的时刻是t1,t2t_1,t_2，那么我们有

{(t1+⌊t1B⌋)mod  A==(t2+⌊t2B⌋)mod  At1mod  B==t2mod  B\begin{cases} (t_1+\lfloor\dfrac{t_1}{B}\rfloor)\mod A == (t_2+\lfloor\dfrac{t_2}{B}\rfloor)\mod A \\ t_1\mod B == t_2 \mod B \end{cases}

不妨设$t_1 = i B+j $其中0≤j≤B−10 \le j \le B-1

由第二个式子，有t2mod  B=jt_2 \mod B = j

那么我们不妨设t2=kB+jt_2 = kB+j

带入第一个式子：

(iB+j+i)mod  A==(kB+j+k)mod  A(iB+j + i) \mod A == (kB+j+k)\mod A

化简一下：

(i(B+1)+j)mod  A==(k(B+1)+j)mod  A(i(B+1)+j)\mod A==(k(B+1)+j)\mod A

发现左右两边的jj可以消掉：

(i(B+1))mod  A==(k(B+1))mod  A(i(B+1))\mod A==(k(B+1))\mod A

所以两式相等的条件就是(k−j)(B+1)mod  A==0(k-j)(B+1) \mod A ==0

即k == j (\mod \\dfracA}{gcd(A,B+1)})

带入原始式子，发现t1,t2t_1,t_2对应的数对相同的充要条件就是t1==t2(mod  ABgc+1))t_1 == t_2 (\mod \frac{AB}{gc\dfrac+1)})

所以问题转化为线段求并。

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline long long read(){
	long long x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
long long gcd(long long x,long long y){
	return x%y==0?y:gcd(y,x%y);
}
struct Segment{
	long long l,r;
}s[MAXN];
int cnt;
inline void AddSegment(long long l,long long r){
	s[++cnt]=Segment{l,r};
}
inline bool operator < (const Segment &A,const Segment &B){
	return A.l!=B.l?A.l<B.l:A.r<B.r;
}
inline bool operator == (const Segment &A,const Segment &B){
	return A.l==B.l&&A.r==B.r;
}
int main(){
	int n=read();
	long long a=read(),b=read();
	long long M=a/(gcd(a,b+1));
	2e18/M<b?M=2e18:M*=b;
	for (register int i=1;i<=n;++i){
		long long l=read(),r=read();
		if (r-l+1>=M){
			printf("%lld\n",M);
			return 0;
		}
		l%=M,r%=M;
		if (l<=r){
			AddSegment(l,r);
		}
		else {
			AddSegment(0,r);
			AddSegment(l,M-1);
		}
	}
	sort(s+1,s+1+cnt);
	cnt=unique(s+1,s+1+cnt)-s-1;
	long long L=s[1].l,R=s[1].r;
	long long ans=0;
	for (register int i=2;i<=cnt;++i){
		if (R<s[i].l) ans+=R-L+1,L=s[i].l,R=s[i].r;
		else R=max(R,s[i].r);
	}
	ans+=R-L+1;
	printf("%lld\n",ans);
}

T2:

P5443 [APIO2019]桥梁

口胡一下部分分做法：

subtask1:大暴力，跑一个bfs即可。

subtask2:用线段树维护一条链，每次二分找出最左/最右边界。

subtask4:离线+并查集，按照边权从大到小，重量从大到小对汽车和桥分别排序，遍历每辆汽车，设其重量是ww，将承重能力大于等于ww的边全部加入并查集，容易发现并查集是越变越大的，因为汽车重量依次减少，所以它能到达的地方越来越多，大力kruskal重构树也是可以的。

讲一讲正解做法，不妨将暴力和并查集的思路结合在一起，对询问分块，因为桥可能越改越烂，所以并查集的大小不是只增不减的，于是需要支持可撤销。

剩下的部分在代码里面有详细注释

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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int U[MAXN],V[MAXN],D[MAXN],n,m;
int t[MAXN],s[MAXN],w[MAXN],vis[MAXN];

struct Query{
	int w,s,id;
}q[MAXN];
int cntq;
inline bool operator < (const Query &A,const Query &B){
    return A.w>B.w;
}
inline void AddQuery(int w,int s,int id){
	q[++cntq]=Query{w,s,id};
}

int u[MAXN],cntu;
inline void AddUpdate(int e){
	u[++cntu]=e;
}

struct Edge{
	int w,id;
}e[MAXN];
int cnte;
inline bool operator < (const Edge &A,const Edge &B){
    return A.w>B.w;
}
inline void AddEdge(int w,int i){
	e[++cnte]=Edge{w,i};
}


int tag[MAXN],cnt;
namespace BCJ{
	int fa[MAXN],sz[MAXN];
	int _u[MAXN],_v[MAXN];
	inline void Init_BCJ(){
		for (register int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
	}
	int GetFa(int i){
		return fa[i]==i?i:GetFa(fa[i]);
	}
	inline void Union(int i){
		int fau=GetFa(U[i]),fav=GetFa(V[i]);
		if (fau==fav) return ;
		if (sz[fau]>sz[fav]) swap(fau,fav);
		fa[fau]=fav,sz[fav]+=sz[fau];
		_u[i]=fau,_v[i]=fav;//记录修改的点
	}
	inline void Reverse(){//回溯
		for (register int i=cnt;i>=1;--i){
			int from=_u[tag[i]],to=_v[tag[i]];
			_u[tag[i]]=0,_v[tag[i]]=0;
			if (from<0) continue;
			sz[to]-=sz[from],fa[from]=from;
		}
        cnt=0;
	}
}
using namespace BCJ;

int temp[MAXN],ans[MAXN];
inline void Clear(){
	cntu=cntq=cnte=0;
	memset(vis,0,sizeof(vis));
}
int main(){
	n=read(),m=read();
	for (register int i=1;i<=m;++i){
		U[i]=read(),V[i]=read(),D[i]=read();
	}
	int alb=read();
	int Size=1000,lst=1;
	for (register int i=1;i<=alb;++i){
		t[i]=read(),s[i]=read(),w[i]=read();
		if (t[i]==1){//Update s[i]->w[i]
			if (!vis[s[i]]){
				AddUpdate(s[i]);
				vis[s[i]]=true;//vis[i]==true表示i修改过
			}
		}
		else {//Query
			AddQuery(w[i],s[i],i);
		}
		if (i==alb||i%Size==0){//搞完一个块
			for (register int j=1;j<=m;++j) AddEdge(D[j],j),_u[j]=0;//加入所有边 
			Init_BCJ();
			sort(e+1,e+1+cnte),sort(q+1,q+1+cntq);//按照边权从大到小排序
			int p=1;
			for (register int j=1;j<=cntq;++j){//遍历每个询问
				for (;p<=cnte&&e[p].w>=q[j].w;++p){//没有修改过的边
					int id=e[p].id;
					if (vis[id]) continue;
					Union(id),_u[id]=0;//这条边一定在后面的并查集里面，所以不需要回滚
				}
				for (register int k=lst;k<q[j].id;++k){//lst后面都没有做到
                    int id=s[k];
					if (t[k]==1) temp[id]=1;//标记需要修改的边
				}
				for (register int k=1;k<=cntu;++k){
					int id=u[k];
					if (!temp[id]&&D[id]>=q[j].w) {//没有修改，但是需要回滚，因为后面的操作可能把桥变得更坏
						Union(id),tag[++cnt]=id;
					}
				}
				for (register int k=q[j].id;k>=lst;--k){
					int id=s[k];
					if (t[k]==1) temp[id]=0;//回滚temp数组，所以是倒序
					if (t[k]==2||_u[id]) continue;//如果是query就跳过
					_u[id]=-1,tag[++cnt]=id;//需要回滚
					if (w[k]>=q[j].w) Union(id);//w[k]>=q[j].w对答案可能会有影响
				}
				ans[q[j].id]=sz[GetFa(q[j].s)];//记录答案
				Reverse();//回溯并查集
			}
			for (;lst<=i;++lst){//lst记录修改和查询到哪里
                if (t[lst]==1) D[s[lst]]=w[lst];//把这一块的修改全部做掉，防止影响后面的答案
                else printf("%d\n",ans[lst]);
			}
			Clear();//清空
		}
	}
}

总结：此题的分块做法将暴力可以修改边的性质和离线做法对询问排序的做法结合在一起，十分巧妙。

T3：

P5445 [APIO2019]路灯

其实这道题部分分可以拿到60分，现在来详细讲解一下：

subtask1:n,q<=100n,q<=100暴力，每次暴力复制一份数组：

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
namespace BruteForce{
	int a[MAXN][MAXN];
	inline void Copy(int i,int j,int n){//Copy i to j
		for (register int k=1;k<=n;++k){
			a[j][k]=a[i][k];
		}
	}
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[0][i]=s[i]-'0';
		for (register int i=1;i<=q;++i){
			Copy(i-1,i,n);
			if (cmd[i]==0){
				int l=ql[i],r=qr[i];
				int ans=0;
				for (register int j=0;j<i;++j){
					bool flag=false;
					for (register int k=l;k<r;++k){
						if (a[j][k]==0) {
							flag=true;break;
						}
					}
					if (flag==false){
						ans++;
					}
				}
				printf("%d\n",ans);
			}
			else {
				int pos=qval[i];
				a[i][pos]=!a[i][pos];
			}
		}
		return 0;
	}
}

subtask2:这个部分分思维难度比较大，考虑到一个灯的贡献，如果它在t1t_1时刻被点亮，而在t2t_2时刻被熄灭，发现它对答案的贡献是t2−t1t_2-t_1

不妨记录一个lstlst，代表最后一次这个路灯被点亮/熄灭的时刻，还有一个ansans，对于t∈[1,lst]t \in [1,lst]如果tt时，a[i]==1a[i]==1，那么ans[i]++ans[i]++。

每次Update时这样更新ansans：

1
2
3
4
if (a[pos]==0){
	ans[pos]+=t-lst[pos];
}
lst[pos]=t;

查询时则是，把前缀和分为两个部分记录：

1
ans[l]+(t-lst[l])*a[l]
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
namespace Special_2{
	int lst[MAX];//最后一次这个路灯被点亮/熄灭的时刻
	int ans[MAX],a[MAX];
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[i]=s[i]-'0';
		for (register int i=1;i<=n;++i) {
			if (a[i]==1) lst[i]=0;
			else lst[i]=-1;
		}
		for (register int t=1;t<=q;++t){
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				printf("%d\n",ans[l]+(t-lst[l])*a[l]);
			}
			else {
				int pos=qval[t];
				a[pos]=!a[pos];
				if (a[pos]==0){
					ans[pos]+=t-lst[pos];
				}
				lst[pos]=t;
			}
		}
		return 0;
	}
}

subtask3：

对于区间[l,r−1][l,r-1]它全部被点亮的时刻之和，就是[l,r−1][l,r-1]所有路灯之中，最后一个被点亮的时刻lstlst，用现在时刻tt减去lstlst即可。

维护一个支持单点覆盖，区间求最大值的线段树即可。

初始化成INFINF，如果查询结果是INFINF，说明这个区间没有灯被点亮，输出00。

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
namespace SegmentTree{
	struct node{
		int l,r;
		int maxn;
	}tree[1000005*4];
	#define lc i<<1
	#define rc i<<1|1
	inline void pushup(int i){
		tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
	}
	void Build(int i,int l,int r){
		tree[i].l=l,tree[i].r=r;
		if (l==r){
			tree[i].maxn=0x7fffffff;
			return ;
		}
		int mid=(l+r)>>1;
		Build(lc,l,mid);
		Build(rc,mid+1,r);
		pushup(i);
	}
	void Update(int i,int pos,int val){
		if (tree[i].l==tree[i].r){
			tree[i].maxn=val;
			return ;
		}
		int mid=(tree[i].l+tree[i].r)>>1;
		if (pos<=mid) Update(lc,pos,val);
		else Update(rc,pos,val);
		pushup(i);
	}
	int Query(int i,int L,int R){
		if (L<=tree[i].l&&tree[i].r<=R){
			return tree[i].maxn;
		}
		int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff;
		if (L<=mid) ans=max(ans,Query(lc,L,R));
		if (mid<R) ans=max(ans,Query(rc,L,R));
		return ans;
	}
}
using namespace SegmentTree;
namespace Special_3{
	inline int Solve(int n,int q){
		//printf("coming into 3\n");
		Build(1,1,n);
		for (register int i=1;i<=n;++i){
			if ((s[i]-'0')==1) Update(1,i,0);
		}
		for (register int t=1;t<=q;++t) {
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				int ans=Query(1,l,r-1);
				if (ans==0x7fffffff) puts("0");//这条路上面有灯从未被点亮
				else printf("%d\n",t-ans); 
			}
			else {
				int i=qval[t];
				Update(1,i,t);
			}
		}
		return 0;
	}
}

subtask4:不知道怎么搞。

60pt60pt代码：

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <bits/stdc++.h>
#define MAXN 205
#define MAX 300005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
/*
把询问离线下来 
*/
int cmd[MAX],ql[MAX],qr[MAX],qval[MAX],vis[MAX];
char opr[10],s[MAX];
bool flag2,flag3;
inline void ReadQuerys(int q){
	flag2=flag3=true;
	for (register int i=1;i<=q;++i){
		scanf("%s",opr);
		if (opr[0]=='q'){
			cmd[i]=0;
			int l=read(),r=read();
			if (r!=l+1) flag2=false;
			ql[i]=l,qr[i]=r;
		}
		else {
			cmd[i]=1;
			int pos=read();
			if (vis[pos]==1) flag3=false;
			vis[pos]=1;
			qval[i]=pos;
		}
	}
}
namespace SegmentTree{
	struct node{
		int l,r;
		int maxn;
	}tree[1000005*4];
	#define lc i<<1
	#define rc i<<1|1
	inline void pushup(int i){
		tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
	}
	void Build(int i,int l,int r){
		tree[i].l=l,tree[i].r=r;
		if (l==r){
			tree[i].maxn=0x7fffffff;
			return ;
		}
		int mid=(l+r)>>1;
		Build(lc,l,mid);
		Build(rc,mid+1,r);
		pushup(i);
	}
	void Update(int i,int pos,int val){
		if (tree[i].l==tree[i].r){
			tree[i].maxn=val;
			return ;
		}
		int mid=(tree[i].l+tree[i].r)>>1;
		if (pos<=mid) Update(lc,pos,val);
		else Update(rc,pos,val);
		pushup(i);
	}
	int Query(int i,int L,int R){
		if (L<=tree[i].l&&tree[i].r<=R){
			return tree[i].maxn;
		}
		int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff;
		if (L<=mid) ans=max(ans,Query(lc,L,R));
		if (mid<R) ans=max(ans,Query(rc,L,R));
		return ans;
	}
}
using namespace SegmentTree;
namespace Special_3{
	inline int Solve(int n,int q){
		//printf("coming into 3\n");
		Build(1,1,n);
		for (register int i=1;i<=n;++i){
			if ((s[i]-'0')==1) Update(1,i,0);
		}
		for (register int t=1;t<=q;++t) {
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				int ans=Query(1,l,r-1);
				if (ans==0x7fffffff) puts("0");//这条路上面有灯从未被点亮
				else printf("%d\n",t-ans); 
			}
			else {
				int i=qval[t];
				Update(1,i,t);
			}
		}
		return 0;
	}
}
namespace Special_2{
	int lst[MAX];//最后一次这个路灯被点亮的时刻
	int ans[MAX],a[MAX];
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[i]=s[i]-'0';
		for (register int i=1;i<=n;++i) {
			if (a[i]==1) lst[i]=0;
			else lst[i]=-1;
		}
		for (register int t=1;t<=q;++t){
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				printf("%d\n",ans[l]+(t-lst[l])*a[l]);
			}
			else {
				int pos=qval[t];
				a[pos]=!a[pos];
				if (a[pos]==0){
					ans[pos]+=t-lst[pos];
				}
				lst[pos]=t;
			}
		}
		return 0;
	}
}
namespace BruteForce{
	int a[MAXN][MAXN];
	inline void Copy(int i,int j,int n){//Copy i to j
		for (register int k=1;k<=n;++k){
			a[j][k]=a[i][k];
		}
	}
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[0][i]=s[i]-'0';
		for (register int i=1;i<=q;++i){
			Copy(i-1,i,n);
			if (cmd[i]==0){
				int l=ql[i],r=qr[i];
				int ans=0;
				for (register int j=0;j<i;++j){
					bool flag=false;
					for (register int k=l;k<r;++k){
						if (a[j][k]==0) {
							flag=true;break;
						}
					}
					if (flag==false){
						ans++;
					}
				}
				printf("%d\n",ans);
			}
			else {
				int pos=qval[i];
				a[i][pos]=!a[i][pos];
			}
		}
		return 0;
	}
}
int main(){
	int n=read(),q=read();
	scanf("%s",s+1);
	ReadQuerys(q);
	if (n<=100&&q<=100) return BruteForce::Solve(n,q);
	if (flag2) return Special_2::Solve(n,q);
	if (flag3) return Special_3::Solve(n,q);
	puts("you are a alb!");
	return 0;
}

100pts100pts思路：

不妨考虑打一个巨大的表（误，其中表的第ii行第jj列表示询问[i,j][i,j]的答案。

如何维护这个表，延续我们subtask2的思路，考虑到一个灯的贡献，如果它在t1t_1时刻被点亮，而在t2t_2时刻被熄灭，发现它对答案的贡献是t2−t1t_2-t_1，而这一个灯会对整个区间做出贡献，考虑加入一个灯，连成的全部被点亮的灯的区间是[l,r][l,r]，灯的下标为xx，那么这个灯的加入会对左端点在[l,x][l,x]，右端点在[x,r][x,r]的询问造成贡献，熄灭也是同理。

关键问题来了，我们要对这个矩形加上多少，一个灯的贡献是它被点亮的所有时刻之和减去它被熄灭的所有时刻之和，所以亮起我们加上−t-t，熄灭加上tt，如果询问时两点已经联通，那么加上tt。

注意到我们很难处理区间修改，单点查询的问题，不妨做一次差分，变成区间查询，单点修改，可以CDQ分治或者树套树维护。

CDQ分治代码：

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
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void write(register int x){
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
int m;
namespace BIT{
	int C[MAXN];
	#define lowbit(x) (x&(-x))
	inline int Query(int k){
		int ans=0;
		for (register int i=k;i>=1;i-=lowbit(i)){
			ans+=C[i];
		}
		return ans;
	}
	inline void Update(int k,int val){
		for (register int i=k;i<MAXN;i+=lowbit(i)){
			C[i]+=val;
		}
	}
}
using namespace BIT;

struct node{
	int t,x,y,id;
	int type,val,ans;
};
node F[MAXN*4];
int tot,n;
inline void Add(int tim,int type,int x,int y,int val,int id){
	F[++tot].t=tim;
	F[tot].x=x;
	F[tot].y=y;
	F[tot].type=type;
	F[tot].val=val;
	F[tot].id=id;
	F[tot].ans=0;
}
inline bool cmp1(const node &A,const node &B){
	if (A.t!=B.t) return A.t<B.t;
	if (A.x!=B.x) return A.x<B.x;
	return A.y<B.y;
}
inline bool cmp2(const node &A,const node &B){
	if (A.x!=B.x) return A.x<B.x;
	return A.y<B.y;
}
inline bool cmp3(const node &A,const node &B){
	return A.y<B.y;
}
node tempF[MAXN*4];
inline void Msort(int l,int r){
	int mid=(l+r)/2;
	int j=l,k=mid+1;
	for (register int i=l;i<=r;++i){
		if ((k>r)||(j<=mid&&cmp2(F[j],F[k]))) tempF[i]=F[j++];
		else tempF[i]=F[k++];
	}
	for (register int i=l;i<=r;++i){
		F[i]=tempF[i];
	}
}
//1 query 2 update
void CDQ(int l,int r){
	if (l==r) return ;
	int mid=(l+r)>>1;
	CDQ(l,mid),CDQ(mid+1,r);
 	int p=l-1;
	for (register int i=mid+1;i<=r;++i){
		while (p<mid&&F[p+1].x<=F[i].x){++p;if (F[p].type==2) Update(F[p].y,F[p].val);}
		if (F[i].type==1) F[i].ans+=Query(F[i].y);
	}
	for (register int i=l;i<=p;++i){
		if (F[i].type==2) Update(F[i].y,-F[i].val);
	}
	Msort(l,r);
}
inline void AddRec(int tim,int x1,int y1,int x2,int y2,int val){
	Add(tim,2,x1-1,y1-1,val,0);
	Add(tim,2,x1-1,y2,-val,0);
	Add(tim,2,x2,y1-1,-val,0);
	Add(tim,2,x2,y2,val,0);
}
char s[MAXN];
set<int>S;
#define Iter set<int>::iterator
inline int GetPre(const int &A){
	Iter it=S.lower_bound(A);
	return *--it;
}
inline int GetNex(const int &A){
	Iter it=S.upper_bound(A);
	return *it;
}
int Ans[MAXN];
int main(){
	n=read(),m=read();
	scanf("%s",s+1);
	for (register int i=1;i<=n;++i) if (s[i]=='0') S.insert(i);
	S.insert(0);
	S.insert(n+1);
	int cntq=0;
	char opr[10];
	for (register int i=1;i<=m;++i){
		scanf("%s",opr);
		if (opr[0]=='q'){
			int l=read(),r=read();
			Add(i,1,l,r-1,0,++cntq);
			if (GetNex(l)>r-1&&s[l]=='1'&&s[r-1]=='1') Ans[cntq]+=i;
		}
		else {
			int pos=read();
			s[pos]=s[pos]=='1'?'0':'1';
			if (s[pos]=='1'){//联通
				int l=GetPre(pos)+1,r=GetNex(pos)-1;
				S.erase(pos);
				AddRec(i,l+1,pos+1,pos+1,r+1,-i);
			}
			else {
				int l=GetPre(pos)+1,r=GetNex(pos)-1;
				S.insert(pos);
				AddRec(i,l+1,pos+1,pos+1,r+1,i);
			}
		}
	}
	sort(F+1,F+1+tot,cmp1);
	CDQ(1,tot);
	for (register int i=1;i<=tot;++i){
		if (F[i].type==1){
			Ans[F[i].id]+=F[i].ans;
		}
	}
	for (register int i=1;i<=cntq;++i){
		printf("%d\n",Ans[i]);
	}
}

树套树代码：

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
#include <bits/stdc++.h>
#define MAXN 300005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void write(register int x){
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}


int rt[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int val;
    }tree[MAXN*50];
    int tot;
    #define lc tree[i].l
    #define rc tree[i].r
    inline void pushup(int i){
        tree[i].val=tree[lc].val+tree[rc].val;
    }
    void Update(int &i,int pos,int val,int l,int r){
        if (!i) i=++tot;
        if (l==r){
            tree[i].val+=val;
            return ;
        }
        int mid=(l+r)>>1;
        if (pos<=mid) Update(lc,pos,val,l,mid);
        else Update(rc,pos,val,mid+1,r);
        pushup(i);
    }
    int Query(int i,int L,int R,int l,int r){
        if (L<=l&&r<=R){
            return tree[i].val;
        }
        int mid=(l+r)>>1,ans=0;
        if (L<=mid) ans+=Query(lc,L,R,l,mid);
        if (mid<R) ans+=Query(rc,L,R,mid+1,r);
        return ans;
    }
}
using namespace SegmentTree;

#define lowbit(x) (x&-x)
inline void Add(int x,int y,int val){
    for (register int i=x;i<MAXN;i+=lowbit(i)){
        Update(rt[i],y,val,1,MAXN-1);
    }
}
inline int Ask(int x,int y){
    int ans=0;
    for (register int i=x;i>0;i-=lowbit(i)){
        ans+=Query(rt[i],1,y,1,MAXN-1);
    }
    return ans;
}

int n,m;
inline void AddRec(int x1,int y1,int x2,int y2,int val){
	Add(x1-1,y1-1,val);
	Add(x1-1,y2,-val);
	Add(x2,y1-1,-val);
	Add(x2,y2,val);
}
char s[MAXN];
set<int>S;
#define Iter set<int>::iterator
inline int GetPre(const int &A){
	Iter it=S.lower_bound(A);
	return *--it;
}
inline int GetNex(const int &A){
	Iter it=S.upper_bound(A);
	return *it;
}
int Ans[MAXN];
int main(){
	n=read(),m=read();
	scanf("%s",s+1);
	for (register int i=1;i<=n;++i) if (s[i]=='0') S.insert(i);
	S.insert(0);
	S.insert(n+1);
	int cntq=0;
	char opr[10];
	for (register int i=1;i<=m;++i){
		scanf("%s",opr);
		if (opr[0]=='q'){
			int l=read(),r=read();
			int ans=Ask(l,r-1);
			if (GetNex(l)>r-1&&s[l]=='1'&&s[r-1]=='1') ans+=i;
			printf("%d\n",ans);
		}
		else {
			int pos=read();
			s[pos]=s[pos]=='1'?'0':'1';
			if (s[pos]=='1'){//联通
				int l=GetPre(pos)+1,r=GetNex(pos)-1;
				S.erase(pos);
				AddRec(l+1,pos+1,pos+1,r+1,-i);
			}
			else {
				int l=GetPre(pos)+1,r=GetNex(pos)-1;
				S.insert(pos);
				AddRec(l+1,pos+1,pos+1,r+1,i);
			}
		}
	}
}

卡常代码：

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
#include <bits/stdc++.h>
#define MAXN 205
#define MAX 300005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void write(register int x){
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
inline void Print(int x){
	if (x==0) puts("0");
	else write(x),putchar('\n');
}
/*
把询问离线下来 
*/
int cmd[MAX],ql[MAX],qr[MAX],qval[MAX],vis[MAX];
char opr[10],s[MAX];
bool flag2,flag3;
inline void ReadQuerys(int q){
	flag2=flag3=true;
	for (register int i=1;i<=q;++i){
		scanf("%s",opr);
		if (opr[0]=='q'){
			cmd[i]=0;
			int l=read(),r=read();
			if (r!=l+1) flag2=false;
			ql[i]=l,qr[i]=r;
		}
		else {
			cmd[i]=1;
			int pos=read();
			if (vis[pos]==1) flag3=false;
			vis[pos]=1;
			qval[i]=pos;
		}
	}
}
namespace SegmentTree{
	struct node{
		int l,r;
		int maxn;
	}tree[1000005*4];
	#define lc i<<1
	#define rc i<<1|1
	inline void pushup(int i){
		tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
	}
	void Build(int i,int l,int r){
		tree[i].l=l,tree[i].r=r;
		if (l==r){
			tree[i].maxn=0x7fffffff;
			return ;
		}
		int mid=(l+r)>>1;
		Build(lc,l,mid);
		Build(rc,mid+1,r);
		pushup(i);
	}
	void Update(int i,int pos,int val){
		if (tree[i].l==tree[i].r){
			tree[i].maxn=val;
			return ;
		}
		int mid=(tree[i].l+tree[i].r)>>1;
		if (pos<=mid) Update(lc,pos,val);
		else Update(rc,pos,val);
		pushup(i);
	}
	int Query(int i,int L,int R){
		if (L<=tree[i].l&&tree[i].r<=R){
			return tree[i].maxn;
		}
		int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff;
		if (L<=mid) ans=max(ans,Query(lc,L,R));
		if (mid<R) ans=max(ans,Query(rc,L,R));
		return ans;
	}
}
using namespace SegmentTree;
namespace Special_3{
	inline int Solve(int n,int q){
		Build(1,1,n);
		for (register int i=1;i<=n;++i){
			if ((s[i]-'0')==1) Update(1,i,0);
		}
		for (register int t=1;t<=q;++t) {
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				int ans=Query(1,l,r-1);
				if (ans==0x7fffffff) puts("0");//这条路上面有灯从未被点亮
				else Print(t-ans); 
			}
			else {
				int i=qval[t];
				Update(1,i,t);
			}
		}
		return 0;
	}
}
namespace Special_2{
	int lst[MAX];//最后一次这个路灯被点亮的时刻
	int ans[MAX],a[MAX];
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[i]=s[i]-'0';
		for (register int i=1;i<=n;++i) {
			if (a[i]==1) lst[i]=0;
			else lst[i]=-1;
		}
		for (register int t=1;t<=q;++t){
			if (cmd[t]==0){
				int l=ql[t],r=qr[t];
				Print(ans[l]+(t-lst[l])*a[l]);
			}
			else {
				int pos=qval[t];
				a[pos]=!a[pos];
				if (a[pos]==0){
					ans[pos]+=t-lst[pos];
				}
				lst[pos]=t;
			}
		}
		return 0;
	}
}
namespace BruteForce{
	int a[MAXN][MAXN];
	inline void Copy(int i,int j,int n){//Copy i to j
		for (register int k=1;k<=n;++k){
			a[j][k]=a[i][k];
		}
	}
	inline int Solve(int n,int q){
		for (register int i=1;i<=n;++i) a[0][i]=s[i]-'0';
		for (register int i=1;i<=q;++i){
			Copy(i-1,i,n);
			if (cmd[i]==0){
				int l=ql[i],r=qr[i];
				int ans=0;
				for (register int j=0;j<i;++j){
					bool flag=false;
					for (register int k=l;k<r;++k){
						if (a[j][k]==0) {
							flag=true;break;
						}
					}
					if (flag==false){
						ans++;
					}
				}
				Print(ans);
			}
			else {
				int pos=qval[i];
				a[i][pos]=!a[i][pos];
			}
		}
		return 0;
	}
}
namespace Correct{
	int Max;
	namespace BIT{
		int C[MAX];
		#define lowbit(x) (x&(-x))
		inline int Query(int k){
			int ans=0;
			for (register int i=k;i>=1;i-=lowbit(i)){
				ans+=C[i];
			}
			return ans;
		}
		inline void Update(int k,int val){
			for (register int i=k;i<=Max;i+=lowbit(i)){
				C[i]+=val;
			}
		}
	}
	using namespace BIT;
	
	struct node{
		int t,x,y,id;
		int type,val,ans;
	};
	node F[MAX*4];
	int tot;
	inline void Add(int tim,int type,int x,int y,int val,int id){
		F[++tot].t=tim;
		F[tot].x=x;
		F[tot].y=y;
		F[tot].type=type;
		F[tot].val=val;
		F[tot].id=id;
		F[tot].ans=0;
	}
	inline bool cmp1(const node &A,const node &B){
		if (A.t!=B.t) return A.t<B.t;
		if (A.x!=B.x) return A.x<B.x;
		return A.y<B.y;
	}
	inline bool cmp2(const node &A,const node &B){
		if (A.x!=B.x) return A.x<B.x;
		return A.y<B.y;
	}
	inline bool cmp3(const node &A,const node &B){
		return A.y<B.y;
	}
	node tempF[MAX*4];
	inline void Msort(int l,int r){
		int mid=(l+r)/2;
		int j=l,k=mid+1;
		for (register int i=l;i<=r;++i){
			if ((k>r)||(j<=mid&&cmp2(F[j],F[k]))) tempF[i]=F[j++];
			else tempF[i]=F[k++];
		}
		for (register int i=l;i<=r;++i){
			F[i]=tempF[i];
		}
	}
	void CDQ(int l,int r){
		if (l==r) return ;
		int mid=(l+r)>>1;
		CDQ(l,mid),CDQ(mid+1,r);
	 	int p=l-1;
		for (register int i=mid+1;i<=r;++i){
			while (p<mid&&F[p+1].x<=F[i].x){++p;if (F[p].type==2) Update(F[p].y,F[p].val);}
			if (F[i].type==1) F[i].ans+=Query(F[i].y);
		}
		for (register int i=l;i<=p;++i){
			if (F[i].type==2) Update(F[i].y,-F[i].val);
		}
		Msort(l,r);
	}
	inline void AddRec(int tim,int x1,int y1,int x2,int y2,int val){
		Add(tim,2,x1-1,y1-1,val,0);
		Add(tim,2,x1-1,y2,-val,0);
		Add(tim,2,x2,y1-1,-val,0);
		Add(tim,2,x2,y2,val,0);
	}
	set<int>S;
	#define Iter set<int>::iterator
	inline int GetPre(const int &A){
		Iter it=S.lower_bound(A);
		return *--it;
	}
	inline int GetNex(const int &A){
		Iter it=S.upper_bound(A);
		return *it;
	}
	int Ans[MAX];
	inline int Solve(int n,int q){
		Max=q;
		for (register int i=1;i<=n;++i) if (s[i]=='0') S.insert(i);
		S.insert(0);
		S.insert(n+1);
		int cntq=0;
		for (register int i=1;i<=q;++i){
			if (cmd[i]==0){
				int l=ql[i],r=qr[i];
				//printf("l,r: %d %d\n",l,r);
				Add(i,1,l,r-1,0,++cntq);
				if (GetNex(l)>r-1&&s[l]=='1'&&s[r-1]=='1') Ans[cntq]+=i;
			}
			else {
				int pos=qval[i];
				//printf("%d\n",pos);
				s[pos]=s[pos]=='1'?'0':'1';
				if (s[pos]=='1'){
					int l=GetPre(pos)+1,r=GetNex(pos)-1;
					S.erase(pos);
					AddRec(i,l+1,pos+1,pos+1,r+1,-i);
				}
				else {
					int l=GetPre(pos)+1,r=GetNex(pos)-1;
					S.insert(pos);
					AddRec(i,l+1,pos+1,pos+1,r+1,i);
				}
			}
		}
		sort(F+1,F+1+tot,cmp1);
		CDQ(1,tot);
		for (register int i=1;i<=tot;++i){
			if (F[i].type==1){
				Ans[F[i].id]+=F[i].ans;
			}
		}
		for (register int i=1;i<=cntq;++i){
			Print(Ans[i]);
		}
		return 0;
	}
} 
int main(){
	int n=read(),q=read();
	scanf("%s",s+1);
	ReadQuerys(q);
	if (n<=100&&q<=100) return BruteForce::Solve(n,q);
	if (flag2) return Special_2::Solve(n,q);
	if ((n!=500||q!=300000)&&flag3) return Special_3::Solve(n,q);
	return Correct::Solve(n,q);
	return 0;
}
相关文章
基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/61bab5e6.html

更新于：2022年6月14日

APIO

评论