出题人题解 | #Stringsobits#

原题解链接：https://ac.nowcoder.com/discuss/150246

$O(nm)O(nm)$是可以跑过的。考虑暴力一点的做法。

对每个位置存一个链表。 每次区间赋值就在区间中每个位置的链表末尾加入一个$0\mathrm{/}10/1$。

查询就看区间中每个位置的链表末尾是$00$还是$11$。

撤销操作,就是链表的删除，对某个位置的删除是$O(1)O(1)$的。

所以时间复杂度为$O(nm)O(nm)$,但是空间也是$O(nm)O(nm)$的。

注意到不同位置互不影响，对每个位置依次计算,空间就是$O(m)O(m)$的了。

$stdstd$

撤销操作容易想到线段树分治,所以还可以线段树分治+线段树/$bitsetbitset$,复杂度

$O(m\log m\log n)\mathrm{/}O\left(\frac{nm\log m}{64}\right)O(m\; \backslash log\; m\; \backslash log\; n)\; /\; O\backslash left(\backslash frac\{n\; m\; \backslash log\; m\}\{64\}\backslash right)$

#include <cstdio>
#include <cctype>
#include <assert.h>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=2e4+7;

int n,m,Ans[N];
char s[N];
struct Operation
{
	int opt,id,l,r;
}A[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
void Solve(int pos)
{
	static int val[N],L[N],R[N],id[N];
	int tot=0; const int ed=m+1;
	R[0]=ed, L[ed]=0, val[tot]=s[pos]=='1';
	for(int i=1; i<=m; ++i)
		if(A[i].opt!=3)
		{
			if(A[i].r<pos||A[i].l>pos) continue;
			if(A[i].opt==4) {Ans[i]+=val[L[ed]]; continue;}
			int p=L[ed];
			id[i]=++tot, val[tot]=A[i].opt==1?0:1;
			R[p]=tot, L[ed]=tot, L[tot]=p, R[tot]=ed;
		}
		else
		{
			int p=A[i].id; assert(A[p].opt==1||A[p].opt==2);
			if(A[p].r<pos||A[p].l>pos) continue;
			int x=id[p];
			R[L[x]]=R[x], L[R[x]]=L[x];
		}
}

int main()
{
//	freopen("string24.in","r",stdin);
//	freopen("string.out","w",stdout);

	n=read(), m=read(), scanf("%s",s+1);
	for(int i=1; i<=m; ++i)
	{
		if((A[i].opt=read())==3) A[i].id=read();
		else A[i].l=read(), A[i].r=read(), assert(A[i].l>=1&&A[i].r<=n&&A[i].l<=A[i].r);
	}
	for(int i=1; i<=n; ++i) Solve(i);
	for(int i=1; i<=m; ++i) if(A[i].opt==4) printf("%d\n",Ans[i]);

	return 0;
}