zcmimi's blog
avatar
zc
2020-10-16 13:31:15
  • 本文总阅读量

查看原题

点击跳转

编号在[L,R]的同学添加第x位同学为自己的观察对象。保证x<L\le R

从左到右考虑,如果当前这个人没有观察在他之前的人,那么就必须让他听到指令

否则他观察的人在之前已经考虑过了

所以需要听到指令的人就是没有观测的人

那么用线段树维护区间就可以了

#include<bits/stdc++.h>
const int N=300011;
int n,q,s[N<<2];
bool v[N],laz[N<<2];
#define ls rt<<1
#define rs rt<<1|1
void build(int l,int r,int rt){
    if(l==r)return s[rt]=!v[l],void();
    int m=l+r>>1;
    build(l,m,ls),build(m+1,r,rs);
    s[rt]=s[ls]+s[rs];
}
void pd(int rt){
    if(laz[rt])s[ls]=s[rs]=0,laz[ls]=laz[rs]=1,laz[rt]=0;
}
void upd(int L,int R,int l=1,int r=n,int rt=1){
    if(!s[rt])return;
    if(L<=l&&r<=R)return s[rt]=0,laz[rt]=1,void();
    int m=l+r>>1;pd(rt);
    if(L<=m)upd(L,R,l,m,ls);
    if(R>m)upd(L,R,m+1,r,rs);
    s[rt]=s[ls]+s[rs];
}
int ask(int L,int R,int l=1,int r=n,int rt=1){
    if(L<=l&&r<=R)return s[rt];
    int m=l+r>>1;pd(rt);
    return (L<=m?ask(L,R,l,m,ls):0)+(R>m?ask(L,R,m+1,r,rs):0);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,t,x;i<=n;++i)
        for(scanf("%d",&t);t--;)
            scanf("%d",&x),v[x]=1;
    build(1,n,1);
    for(int opt,l,r;q--;){
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1)printf("%d\n",(l>1?ask(1,l-1):0)+(r<n?ask(r+1,n):0));
        else upd(l,r),scanf("%d",&opt);
    }
}
LG 5166 xtq的口令
comment评论
Search
search