题解：P5166 xtq的口令

#include<cmath>
#include<iostream>
typedef long long lli;
using namespace std;
int a[200007],lazy[1007],be[200007],block,tot;
int l[1007],r[1007],n,sum[1007];
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*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0){x=~(x-1);putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+48);
}
inline void build()
{
	block=sqrt(n),tot=n/block;
	if(n%block)tot++;
	for(register int i=1;i<=tot;++i)
		l[i]=(i-1)*block+1,r[i]=i*block;
	r[tot]=n;
	for(register int i=1;i<=n;++i)
		be[i]=(i-1)/block+1,sum[be[i]]+=a[i];
}
inline void upd(int x,int y)
{
	if(be[x]==be[y])
	{
		for(register int i=x;i<=y;++i)
			if(a[i])--a[i],--sum[be[i]];
		return;
	}
	for(register int i=x;i<=r[be[x]];++i)
		if(a[i])--a[i],--sum[be[i]];
	for(register int i=l[be[y]];i<=y;++i)
		if(a[i])--a[i],--sum[be[i]];
	for(register int i=be[x]+1;i<=be[y]-1;++i)
		if(sum[i]!=0)--lazy[i],sum[i]-=block;
}
int query(int x,int y)
{
	int res=0;
	if(be[x]==be[y])
	{
		for(register int i=x;i<=y;++i)
			res+=max(a[i]+lazy[be[i]],0);
		return res;
	}
	for(register int i=x;i<=r[be[x]];++i)
		res+=max(a[i]+lazy[be[i]],0);
	for(register int i=l[be[y]];i<=y;++i)
		res+=max(a[i]+lazy[be[i]],0);
	for(register int i=be[x]+1;i<=be[y]-1;++i)
		res+=max(sum[i],0);
	return res;
}
int main()
{
 	int q;
	n=read(),q=read();
	for(int i=0;i<=n+1;i++)a[i]=1;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		x=read();
		while(x--)y=read(),a[y]=0;
	}
	build();
	while(q--)
	{
        int x,y,op,k;
		op=read(),x=read(),y=read();
		if(op==2)k=read(),upd(x,y);
		else 
		{
			int t=0;
			if(x>1)t+=query(1,x-1);
			if(y<n)t+=query(y+1,n);
			write(t),putchar('\n');
		}
	}
	return 0;
}