先令编号从\(1\)开始。我们要求\([1,i]\)这些数字能否构成一个矩形。
考虑能否用线段树维护,让每个叶子节点\(i\)表示前\(i\)个数能否构成矩形。
一种方法是维护前\(i\)个点最左上点和最右下点的坐标,直接判断这两个点构成的矩形面积是否是\(i\)。
发现修改的时候这个最值不好维护,每次修改可能是\(O(n)\)的。
考虑合法矩形的特征。把前\(i\)个点标记为黑点,其余点是白点。那么前\(i\)个点构成了一个矩形当且仅当:
- 左边和上边都是白点的黑点有且只有一个。
- 不存在一个白点,它的上下左右有两个及以上黑点。
正确性比较显然...?(雾)不说了。
记左边上边都是白点的黑点数量为\(t1\),上下左右有两个及以上黑点是白点数量为\(t2\)。注意到\(t1>0\),\(t2\)非负,那么\(i\)合法当且仅当\(t1+t2=1\),所以只在叶节点处维护前\(i\)个点为黑点时,\(t1+t2\)的值就好了。非叶节点就维护区间最小值及最小值的个数。
考虑修改时如何维护。
记\(l\)为点\(i\)周围点(上下左右)编号的次小值,点\(i\)作为白点时,会对\([l,i-1]\)这些位置有贡献。
记\(r\)为点\(i\)左边、上边的点的编号的最小值,那么点\(i\)作为黑点时,会对\([i,r-1]\)这些位置有贡献。
每次交换两个点\(x,y\),最多只会影响\(10\)个点的\(l,r\),所以把这些点取出来,减掉在线段树上的贡献,交换\(x,y\)之后再把它们的贡献加上即可。
注意要对这些点判重。
//27496ms 1688K
#include "seats.h"
#include <cstdio>
#include <cctype>
#include <algorithm>
#define F(p,i) (p+Way[i])
#define ID(x,y) ((x-1)*m+y)
#define Check(x,y) (x>=1&&x<=n&&y>=1&&y<=m)
#define gc() getchar()
const int N=1e6+5,Way[]={1,0,-1,0,1};//down left up right
int n,m,tot,A[N],X[N],Y[N],val[N];
struct Segment_Tree
{
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
#define S N<<2
int mn[S],cnt[S],tag[S];
#undef S
#define Upd(rt,v) tag[rt]+=v, mn[rt]+=v
#define Update(rt) mn[rt]=std::min(mn[ls],mn[rs]), cnt[rt]=(mn[rt]==mn[ls]?cnt[ls]:0)+(mn[rt]==mn[rs]?cnt[rs]:0)
inline void PushDown(int rt)
{
Upd(ls,tag[rt]), Upd(rs,tag[rt]), tag[rt]=0;
}
void Build(int l,int r,int rt)
{
if(l==r)
{
mn[rt]=val[l], cnt[rt]=1;
return;
}
int m=l+r>>1;
Build(lson), Build(rson), Update(rt);
}
void Modify(int l,int r,int rt,int L,int R,int v)
{
if(L<=l && r<=R) {Upd(rt,v); return;}
if(tag[rt]) PushDown(rt);
int m=l+r>>1;
if(L<=m) Modify(lson,L,R,v);
if(m<R) Modify(rson,L,R,v);
Update(rt);
}
}T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now;
}
inline int CalcW(int p)
{
int mn1=tot+1,mn2=mn1,x=X[p],y=Y[p];
for(int i=0,xn,yn; i<4; ++i)
if(xn=F(x,i),yn=F(y,i+1),Check(xn,yn))
{
int w=A[ID(xn,yn)];
if(w<mn1) mn2=mn1, mn1=w;
else if(w<mn2) mn2=w;
}
return mn2;
}
inline int CalcB(int p)
{
int x=X[p],y=Y[p],xn1=F(x,1),yn1=F(y,2),xn2=F(x,2),yn2=F(y,3);
return std::min(Check(xn1,yn1)?A[ID(xn1,yn1)]:tot+1,Check(xn2,yn2)?A[ID(xn2,yn2)]:tot+1);
}
#define S 1,tot,1
void give_initial_chart(int n,int m,std::vector<int> R,std::vector<int> C)
{
int tot=n*m; ::n=n, ::m=m, ::tot=tot;
for(int i=1; i<=tot; ++i) X[i]=R[i-1]+1,Y[i]=C[i-1]+1,A[ID(X[i],Y[i])]=i;
// for(int i=1; i<=tot; ++i) X[i]=read()+1,Y[i]=read()+1,A[ID(X[i],Y[i])]=i;
for(int i=1; i<=tot; ++i)
{
val[i]=val[i-1];
if(CalcW(i)<i) --val[i];
if(CalcB(i)>i) ++val[i];
for(int j=0,x=X[i],y=Y[i],xn,yn,w; j<4; ++j)
if(xn=F(x,j),yn=F(y,j+1),Check(xn,yn))
{
if((w=A[ID(xn,yn)])<i && CalcB(w)==i) --val[i];
else if(w>i && CalcW(w)==i) ++val[i];
}
}
T.Build(S);
}
int swap_seats(int a,int b)
{
static int B[12];
++a, ++b;
int x=X[a],y=Y[a],t=2; B[1]=a, B[2]=b;
for(int i=0,xn,yn; i<4; ++i)
if(xn=F(x,i),yn=F(y,i+1),Check(xn,yn)) B[++t]=A[ID(xn,yn)];
x=X[b],y=Y[b];
for(int i=0,xn,yn; i<4; ++i)
if(xn=F(x,i),yn=F(y,i+1),Check(xn,yn)) B[++t]=A[ID(xn,yn)];
std::sort(B+1,B+1+t);
for(int i=1; i<=t; ++i)
if(B[i]!=B[i-1])
{
int p=B[i],l=CalcW(p),r=CalcB(p);
if(l<p) T.Modify(S,l,p-1,-1);
if(r>p) T.Modify(S,p,r-1,-1);
}
std::swap(A[ID(X[a],Y[a])],A[ID(X[b],Y[b])]);
std::swap(X[a],X[b]), std::swap(Y[a],Y[b]);
for(int i=1; i<=t; ++i)
if(B[i]!=B[i-1])
{
int p=B[i],l=CalcW(p),r=CalcB(p);
if(l<p) T.Modify(S,l,p-1,1);
if(r>p) T.Modify(S,p,r-1,1);
}
return T.cnt[1];
}
//int main()
//{
// int n=read(),m=read(),Q=read(); ::n=n, ::m=m;
// give_initial_chart(n,m);
// while(Q--) printf("%d\n",swap_seats(read(),read()));
//
// return 0;
//}
LOJ.2864.[IOI2018]排座位(线段树)的更多相关文章
-
[IOI2018]排座位——线段树
题目链接: IOI2018seat 题目大意:给出一个$H*W$的矩阵,将$0 \sim W*H-1$分别填入矩阵的格子里(每个格子里一个数),定义一个子矩阵是美妙的当且仅当这个子矩阵包含且仅包含$0 ...
-
【LOJ#6029】市场(线段树)
[LOJ#6029]市场(线段树) 题面 LOJ 题解 看着就是一个需要势能分析的线段树. 不难发现就是把第二个整除操作化为减法. 考虑一下什么时候整除操作才能变成减法. 假设两个数为\(a,b\). ...
-
【Loj#535】花火(线段树,扫描线)
[Loj#535]花火(线段树,扫描线) 题面 Loj 题解 首先如果不考虑交换任意两个数这个操作,答案就是逆序对的个数. 那么暴力就是枚举交换哪个两个数,然后用数据结构之类的东西动态维护逆序对. 但 ...
-
Loj #2570. 「ZJOI2017」线段树
Loj #2570. 「ZJOI2017」线段树 题目描述 线段树是九条可怜很喜欢的一个数据结构,它拥有着简单的结构.优秀的复杂度与强大的功能,因此可怜曾经花了很长时间研究线段树的一些性质. 最近可怜 ...
-
LOJ#3043.【ZJOI2019】 线段树 线段树,概率期望
原文链接www.cnblogs.com/zhouzhendong/p/ZJOI2019Day1T2.html 前言 在LOJ交了一下我的代码,发现它比选手机快将近 4 倍. 题解 对于线段树上每一个节 ...
-
[IOI2018]会议——分治+线段树
题目链接: [IOI2018]meetings 题目大意:有$n$座山峰,每座山峰有一个高度,有$q$次询问,每次需要确定一个开会山峰使$[l,r]$所有山峰上的人都前往开会山峰,一个山峰的人去开会的 ...
-
[loj#2005][SDOI2017]相关分析 _线段树
「SDOI2017」相关分析 题目链接:https://loj.ac/problem/2005 题解: 把上面的式子拆掉,把下面的式子拆掉. 发现所有的东西都能用线段树暴力维护. 代码: #inclu ...
-
[IOI2018]机械娃娃——线段树+构造
题目链接: IOI2018doll 题目大意:有一个起点和$m$个触发器,给出一个长度为$n$的序列$a$,要求从起点出发按$a$的顺序经过触发器并回到起点(一个触发器可能被经过多次也可能不被经过), ...
-
[LOJ#2980][THUSCH2017]大魔法师(线段树+矩阵)
每个线段树维护一个行向量[A,B,C,len]分别是这个区间的A,B,C区间和与区间长度,转移显然. 以及此题卡常,稍微哪里写丑了就能100->45. #include<cstdio> ...
随机推荐
-
Highchart URL
http://www.highcharts.com/stock/demo/flags-general http://www.codesec.net/view/217265.html http://js ...
-
不同Framework下StringBuilder和String的性能对比,及不同Framework性能比(附Demo)
本文版权归mephisto和博客园共有,欢迎转载,但须保留此段声明,并给出原文链接,谢谢合作. 文章是哥(mephisto)写的,SourceLink 阅读目录 介绍 环境搭建 测试用例 MSDN说明 ...
-
html submit 登录
<!doctype html> <html lang="en"> <head> <meta name="Generator&qu ...
-
Asp.Net集群中Session共享
今天遇到了这个问题,于是研究了一下.要解决这个问题,首先就要明白一些Session的机理.Session在服务器是以散列表形式存在的,我们都知道Session是会话级的,每个用户访问都会生成一个Ses ...
-
虚拟DOM和react中的diff算法总结
https://blog.csdn.net/qq_26708777/article/details/78107577 一.虚拟DOM 1.什么是虚拟DOM及原理 把真实DOM树,变成js ...
-
【EMV L2】Cardholder Verification Rule(CVR) Format
Cardholder Verification Rule(CVR)由两个字节组成: 高字节为Cardholder Verification Method (CVM) Codes,表示执行Cardhol ...
-
SDOI2016 R1做题笔记
SDOI2016 R1做题笔记 经过很久很久的时间,shzr终于做完了SDOI2016一轮的题目. 其实没想到竟然是2016年的题目先做完,因为14年的六个题很早就做了四个了,但是后两个有点开不动.. ...
-
linux shell下16进制 “\uxxxx” unicode to UTF-8中文
问题出现背景: 项目中有个通过ip获取归属地城市需求,我是直接通过新浪的ip归属查询接口来获取的.我使用的是shell脚本调用 RESULT=$(curl -s 'http://int.dpool.s ...
-
LOJ#6503.「雅礼集训 2018 Day4」Magic[容斥+NTT+启发式合并]
题意 \(n\) 张卡牌 \(m\) 种颜色,询问有多少种本质不同的序列满足相邻颜色相同的位置数量等于 \(k\). 分析 首先本质不同不好直接处理,可以将同种颜色的卡牌看作是不相同的,求出答案后除以 ...
-
UI基础:UIView(window,frame,UIColor,CGPoint,alpha,CGRect等) 分类: iOS学习-UI 2015-06-30 20:01 119人阅读 评论(0) 收藏
UIView 视图类,视图都是UIView或者UIView子类 UIWindow 窗口类,用于展示视图,视图一定要添加window才能显示 注意:一般来说,一个应用只有一个window 创建一个UIW ...