[IOI2018]seats排座位——线段树
题目链接：
这题思路真的很神。
原题编号从0开始，很不舒服，我们按从1开始的讲。
发现只需要判断[1,i]这些数是否组成了一个矩阵。
那么我们能不能用线段树，第i个叶子节点存前i个数的信息来判断前i个数能否组成矩阵呢？
有的人可能会想到第i个叶子节点维护前i个数中最左上的点和最右下的点，判断时直接取这两个点形成矩形的面积看是否等于i。
这个判断是可行了，但修改呢？你会发现交换两个点的位置会改变好多点的信息，甚至影响的信息达到O(n)级别。
这时真正的神仙操作来了。
在判断前i个点是否成立时我们将前i个点染成黑色，其他点为白色。
我们维护两个信息：
1、有多少黑点的左边和上边都是白点或边界
2、有多少白点的四联通块中包含大于等于2个黑点
可以看出，如果前i个点形成矩形那么第一个信息值为1，第二个信息值为0。同理也只有这种情况才是矩形。
为什么呢？
如果黑点都连在一起形成一个图形，那么第二个信息为0保证他是一个凸多边形且多边形的边与整个图是平行的，而第一个信息为1则保证他有四个顶点。
如果还是不太明白可以手画一下。
不管所有黑点组成什么图形都至少有一个左上顶点，因此第一个信息的值一定是正数。
我们维护两个信息不方便，不妨维护他们两个的和，那么就只有和为1时是成立的。
在线段树上每个叶子节点维护前i个点染黑后两个信息的和，代表区间的那些父节点则维护区间最小值及最小值个数即可。
那么怎么修改？
对于第i个点我们求出它作为白点有贡献的开始时刻l和作为黑点有贡献的结束时刻r。
那么这个点作为白点时会对[l,i-1]这段时刻有贡献，而作为黑点是会对[i,r-1]这段时刻有贡献。
交换两个点会影响这两个点的四联通块最多10个点的l和r，先减去原先每个点的贡献，交换位置后再对每个点有贡献的时间段区间修改即可，注意这些修改的点要去重。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mp(x,y) (b[(x-1)*m+y])
#define sx(i) (a[i].x)
#define sy(i) (a[i].y)
#define fx(x,i) (x+dx[i])
#define fy(x,i) (x+dy[i])
#define check(x,y) (x>=1&&x<=n&&y>=1&&y<=m)
using namespace std;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int b[1000010];
int mn[4000010];
int sum[4000010];
int t[4000010];
int v[1000010];
int n,m,q;
int x,y;
int st[15];
int top;
struct miku
{
int x;
int y;
}a[1000010];
inline void pushup(int rt)
{
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
sum[rt]=0;
if(mn[rt<<1]==mn[rt])
{
sum[rt]+=sum[rt<<1];
}
if(mn[rt<<1|1]==mn[rt])
{
sum[rt]+=sum[rt<<1|1];
}
}
inline void pushdown(int rt)
{
if(t[rt])
{
t[rt<<1]+=t[rt];
t[rt<<1|1]+=t[rt];
mn[rt<<1]+=t[rt];
mn[rt<<1|1]+=t[rt];
t[rt]=0;
}
}
inline void build(int rt,int l,int r)
{
if(l==r)
{
mn[rt]=v[l];
sum[rt]=1;
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
inline void change(int rt,int l,int r,int L,int R,int k)
{
if(L<=l&&r<=R)
{
mn[rt]+=k;
t[rt]+=k;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid)
{
change(rt<<1,l,mid,L,R,k);
}
if(R>mid)
{
change(rt<<1|1,mid+1,r,L,R,k);
}
pushup(rt);
}
inline int begin_white(int x)
{
int m1=n*m+1;
int m2=n*m+1;
for(int i=0;i<4;i++)
{
if(check(fx(sx(x),i),fy(sy(x),i)))
{
int now=mp(fx(sx(x),i),fy(sy(x),i));
if(now<m1)
{
m2=m1;
m1=now;
}
else if(now<m2)
{
m2=now;
}
}
}
return m2;
}
inline int end_black(int x)
{
int m1=n*m+1;
for(int i=0;i<2;i++)
{
if(check(fx(sx(x),i),fy(sy(x),i)))
{
m1=min(m1,mp(fx(sx(x),i),fy(sy(x),i)));
}
}
return m1;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n*m;i++)
{
scanf("%d%d",&x,&y);
x++;
y++;
a[i].x=x;
a[i].y=y;
b[(x-1)*m+y]=i;
}
for(int i=1;i<=n*m;i++)
{
v[i]=v[i-1];
int l=begin_white(i);
int r=end_black(i);
if(l<i)
{
v[i]--;
}
if(r>i)
{
v[i]++;
}
for(int j=0;j<4;j++)
{
if(check(fx(sx(i),j),fy(sy(i),j)))
{
int now=mp(fx(sx(i),j),fy(sy(i),j));
if(now<i&&end_black(now)==i)
{
v[i]--;
}
else if(now>i&&begin_white(now)==i)
{
v[i]++;
}
}
}
}
build(1,1,n*m);
while(q--)
{
scanf("%d%d",&x,&y);
x++;
y++;
if(x>y)
{
swap(x,y);
}
top=0;
st[++top]=x;
st[++top]=y;
for(int i=0;i<4;i++)
{
if(check(fx(sx(x),i),fy(sy(x),i)))
{
st[++top]=mp(fx(sx(x),i),fy(sy(x),i));
}
}
for(int i=0;i<4;i++)
{
if(check(fx(sx(y),i),fy(sy(y),i)))
{
st[++top]=mp(fx(sx(y),i),fy(sy(y),i));
}
}
sort(st+1,st+1+top);
for(int i=1;i<=top;i++)
{
if(st[i]!=st[i-1])
{
int l=begin_white(st[i]);
int r=end_black(st[i]);
if(l<st[i])
{
change(1,1,n*m,max(l,x),min(st[i],y)-1,-1);
}
if(r>st[i])
{
change(1,1,n*m,max(st[i],x),min(r,y)-1,-1);
}
}
}
swap(mp(sx(x),sy(x)),mp(sx(y),sy(y)));
swap(a[x],a[y]);
for(int i=1;i<=top;i++)
{
if(st[i]!=st[i-1])
{
int l=begin_white(st[i]);
int r=end_black(st[i]);
if(l<st[i])
{
change(1,1,n*m,max(l,x),min(st[i],y)-1,1);
}
if(r>st[i])
{
change(1,1,n*m,max(st[i],x),min(r,y)-1,1);
}
}
}
printf("%d\n",sum[1]);
}
}
版权声明：本文为Khada-Jhin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。