题解：P5166 xtq的口令

yhlj24444 · 2025-06-30 09:22:50 · 题解

题解P5166

推理一下：

• 如果这个人没有观察对象的话，那他就必须听到指令
• 如果这个人有观察对象，那考虑观察对象的状态即可，所以对答案来说没有贡献

所以令无观察对象者为 1 ，有观察对象者为 0 ，题目所给的询问就转化成区间推平为 0 ，和区间和查询区间和即为区间 [1,l-1] 和 [r+1,n]

用分块维护，代码如下:

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

求过qwq