【LuoGu T44990】不认识 / 题解

【LuoGu T44990】不认识 / 题解

原题链接

题意简述

有 $n$ 个同学站成一排($1 \leq n \leq 10^6$),一开始彼此不认识。每次给定一个区间 $[l,r]$,让区间内的同学都相互认识以下。求每次操作前区间内不认识的同学的对数。

思路

我们将 $n$ 个同学之间的认识状态用一个二维 0 / 1 矩阵,或者说一个 0 / 1 正方形表示出来。

一开始同学们相互都不认识,所以这个正方形内部除了对角线都是空的。现在我们操作区间 $[1,3]$,我在图形中使用红色标记这次操作。在操作之前,互相不认识的同学有 $3$ 对,也就是 $\dfrac{S_{empty}}{2}$。

现在给定区间 $[3,4]$,用黄色正方形覆盖这段区间。可以看到,在覆盖前只有一对同学互相不认识。

类似的,我们可以用蓝色标识区间 $[2,4]$。这之前的输出结果是 $1$。

如果我们继续操作区间 $[2,3]$,会发现它已经被填满了,答案为 $0$。

我们发现,每次加入的正方形,对角线都是共线的。也就是说,当横坐标确定,已填色区域的纵坐标是连续的,这对于使用数据结构维护很重要。那么我们就可以直接以横坐标为关键字,用线段树维护已填色区域的上边缘纵坐标。

加入正方形,相当于区间取最大值;已知已填色区域上边缘纵坐标之和,就可以求出每个合法正方形内的填色区域面积。

区间取最大值的时候,因为上边缘纵坐标是单调的,先二分找到需要更改的地方,然后区间覆盖。$\Theta(n\log n)$。

代码

#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define len (r-l+1)
#define maxn 1000100
#define ll long long
#define mid ((l+r)>>1)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>1)+(x&1),lp=lazy[p];
    lazy[p]=0;lazy[ls]=lazy[rs]=lp;
    chkmax(rmn[ls],lp);
    chkmax(rmn[rs],lp);
    sum[ls]=(ll)lp*lx;
    sum[rs]=(ll)lp*(x-lx);
}
void Build(int l,int r,int p){
    if (l==r){sum[p]=rmn[p]=l;return;}
    Build(l,mid,ls),Build(mid+1,r,rs);
    Pushup(p);
}
int find(int l,int r,int k,int p){
    if (l==r) return l;
    if (lazy[p]) Pushdown(p,len);
    if (rmn[ls]>=k) return find(l,mid,k,ls);
    else return find(mid+1,r,k,rs);
}
void Update(int l,int r,int L,int R,int k,int p){
    if (l>R||r=L&&r<=R){
        sum[p]=(ll)len*k;
        lazy[p]=rmn[p]=k;
        return; 
    }
    if (lazy[p]) Pushdown(p,len);
    Update(l,mid,L,R,k,ls);
    Update(mid+1,r,L,R,k,rs);
    Pushup(p);
}
ll Query(int l,int r,int L,int R,int p){
    if (l>R||r=L&&r<=R) return sum[p];
    if (lazy[p]) Pushdown(p,len);
    return Query(l,mid,L,R,ls)+Query(mid+1,r,L,R,rs);
}
int main(){
    scanf("%d%d",&n,&q);
    Build(1,n,1);
    for (register int i=1,l,r;i<=q;++i){
        scanf("%d%d",&l,&r);
        l^=lastans,r^=lastans;
        int pos=find(1,n,r,1)-1;
        if (pos