APIO2019毒瘤题记录

T1:

P5444 [APIO2019]奇怪装置

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

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

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

$\begin{cases} (t_1+\lfloor\frac{t_1}{B}\rfloor)\mod A == (t_2+\lfloor\frac{t_2}{B}\rfloor)\mod A \\ t_1\mod B == t_2 \mod B \end{cases}$

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

由第二个式子，有 $t_2 \mod B = j$

那么我们不妨设 $t_2 = kB+j$

带入第一个式子：

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

化简一下：

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

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

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

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

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

带入原始式子，发现 $t_1,t_2$ 对应的数对相同的充要条件就是 $t_1 == t_2 (\mod \frac{AB}{gcd(A,B+1)})$

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

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

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

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

#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<=100$ 暴力，每次暴力复制一份数组：

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:这个部分分思维难度比较大，考虑到一个灯的贡献，如果它在 $t_1$ 时刻被点亮，而在 $t_2$ 时刻被熄灭，发现它对答案的贡献是 $t_2-t_1$

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

每次Update时这样更新 $ans$ ：

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

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

ans[l]+(t-lst[l])*a[l]

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]$ 所有路灯之中，最后一个被点亮的时刻 $lst$ ，用现在时刻 $t$ 减去 $lst$ 即可。

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

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

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:不知道怎么搞。

$60pt$ 代码：

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

$100pts$ 思路：

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

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

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

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

CDQ分治代码：

#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]);
	}
}

树套树代码：

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

卡常代码：

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

Steven_Meng's Blog

T1:

T2:

T3：

下一篇：BZOJ 4987 Tree