自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:10:50，当前版本为作者最后更新于2019-08-26 17:17:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5445 APIO2019 路灯

一道清新的数据结构题...

将连续一段亮着的灯所连接的站点称为一个连通块，考虑点亮/熄灭一盏灯对于答案的贡献。

若点亮了一盏灯，相当于沟通了左右两个连通块，因此我们找出左右两个连通块的左右端点，将它们标记为连通即可。

若熄灭了一盏灯，相当于将一个连通块拆成两个，将两边之间的联系标记成中断即可。

考虑如何实现这个问题。

首先是找到一个点所在的连通块的左右端点，这个可以用两棵线段树来维护（另一篇题解貌似直接set了），点亮的操作相当于是区间赋值（右部连通块中点的左端点修改成左连通块中点的左端点，左连通块中点的右端点修改成右连通块中点的右端点），熄灭同理（左连通块中点的右端点修改成这个路灯左侧的站点，右连通块中点的左端点修改成这个路灯右侧的站点）。

接下来考虑如何统计答案。

构造一个$(n+1)\times (n+1)$的矩阵$M$，$M_{ij}$表示$i$与$j$站点的连通性，我们采用代价提前计算的方法，考虑点亮的操作，若操作在$t$时刻进行，左右连通块区间分别为$[l,x],[x+1,r]$，那么将矩阵中左上角为$(l,x+1)$，右下角为$(x,r)$的子矩阵中所有元素的值增加$q-t$，表示接下来的所有时刻，它们都将连通。

同理，如果要熄灭一盏灯，将那个子矩阵中的所有元素减少$q-t$即可，表示接下来的所有时刻，它们都不连通。

需要注意的就是，$t$时刻询问时如果$x,y$依然连通，由于我们采用代价提前计算，所以需要减掉当前时刻之后的代价，即$q-t$。若$x,y$现在不连通，那么之后的代价已经在曾经的某个时候减掉了，不需要再处理。

于是现在我们要解决子矩阵加，单点求值。

什么？CDQ？如果在线呢？

通过差分将子矩阵加转化成四个点的加减，单点求值转化成前缀矩阵求和。然后就是常规的树状数组套权值线段树问题。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=400010;
int tot,cnt,n,q,x,y,ans,rt[MAXN],val[MAXN<<5],ch[MAXN<<5][2],lp[2][4*MAXN];    //rt,val,ch为BIT套权值线段树用，lp为维护连通块左右端点用
char s[MAXN];
void upd (int p) {
	val[p]=val[ch[p][0]]+val[ch[p][1]];
	return;
}
void modify_t (int &rt,int l,int r,int pos,int v) {
	if (!rt) {rt=++tot;}
	if (l==r) {val[rt]+=v;return;}
	int mid=(l+r)>>1;
	if (pos<=mid) {modify_t(ch[rt][0],l,mid,pos,v);}
	else {modify_t(ch[rt][1],mid+1,r,pos,v);}
	upd(rt);
	return;
}
int query_t (int rt,int l,int r,int xl,int xr) {
	if (xr<l||r<xl) {return 0;}
	if (xl<=l&&r<=xr) {return val[rt];}
	int mid=(l+r)>>1;
	return query_t(ch[rt][0],l,mid,xl,xr)+query_t(ch[rt][1],mid+1,r,xl,xr);
}
void modify (int x,int y,int v) {
	if (y>n+1) {return;}
	for (int i=x;i<=n+1;i+=(i&(-i))) {modify_t(rt[i],1,n+1,y,v);}
	return;
}    //差分后的单点修改
int query (int x,int y) {
	int res=0;
	for (int i=x;i;i-=(i&(-i))) {res+=query_t(rt[i],1,n+1,1,y);}
	return res;
}    //前缀矩阵和
void pd (int p) {
	if (lp[0][p]) {
		lp[0][p*2]=lp[0][p*2+1]=lp[0][p];
		lp[0][p]=0;
	}
	if (lp[1][p]) {
		lp[1][p*2]=lp[1][p*2+1]=lp[1][p];
		lp[1][p]=0;
	}
	return;
}    //区间覆盖的标记下传
void buildt (int p,int l,int r) {
	if (l==r) {lp[0][p]=lp[1][p]=l;return;}
	int mid=(l+r)>>1;
	buildt(p*2,l,mid),buildt(p*2+1,mid+1,r);
	return;
}
void modify2 (int k,int p,int l,int r,int xl,int xr,int v) {
	if (xr<l||r<xl) {return;}
	if (xl<=l&&r<=xr) {lp[k][p]=v;return;}
	pd(p);
	int mid=(l+r)>>1;
	modify2(k,p*2,l,mid,xl,xr,v),modify2(k,p*2+1,mid+1,r,xl,xr,v);
}    //区间覆盖
int query2 (int k,int p,int l,int r,int pos) {
	if (l==r) {return lp[k][p];}
	pd(p);
	int mid=(l+r)>>1;
	if (pos<=mid) {return query2(k,p*2,l,mid,pos);}
	else {return query2(k,p*2+1,mid+1,r,pos);} 
}    //单点查询
bool chk (int x,int y) {
	return (query2(0,1,1,n+1,x)==query2(0,1,1,n+1,y));
}    //判断两点是否连通，只要看所在连通块左端点是否相等
void con (int x,int v) {
	int l=query2(0,1,1,n+1,x),r=query2(1,1,1,n+1,x+1);
	modify2(1,1,1,n+1,l,x,r),modify2(0,1,1,n+1,x+1,r,l);
	modify(l,x+1,q-v),modify(l,r+1,v-q),modify(x+1,x+1,v-q),modify(x+1,r+1,q-v);
	return;
}
void del (int x,int v) {
	int l=query2(0,1,1,n+1,x),r=query2(1,1,1,n+1,x+1);
	modify2(1,1,1,n+1,l,x,x),modify2(0,1,1,n+1,x+1,r,x+1);
	modify(l,x+1,v-q),modify(l,r+1,q-v),modify(x+1,x+1,q-v),modify(x+1,r+1,v-q);
	return;
}
int main () {
	scanf("%d%d%s",&n,&q,s+1);
	buildt(1,1,n+1); 
	for (int i=1;i<=n;i++) {
		if (s[i]=='1') {con(i,0);}
	}
	for (int i=1;i<=q;i++) {
		scanf("%s%d",s+1,&x);
		if (s[1]=='q') {
			scanf("%d",&y);
			ans=query(x,y);
			if (chk(x,y)) {ans-=q-i;}
			printf("%d\n",ans);
		} else {
			if (chk(x,x+1)) {del(x,i);}
			else {con(x,i);}
		}
	}
	return 0;
}