题意简述
有 $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