当前位置: 首页 > news >正文

「JOISC2020-掃除」题解

掃除 (Sweeping)

sol

从 Subtask 3 的特殊性质入手,可以发现一个关键性质:无论之后如何操作,这个单调性在任何时刻均满足。其原因可以简单考虑一下操作的效力范围与结果得到。

理解之后容易推广到全局,不难发现所有被操作过的点形成的点集满足上述性质。满足此性质的话,每次操作作用到的点都是一个连续区间,且操作过后一维会变得相同,直接上平衡树暴力模拟即可。

假如不考虑中途加点的话,我们可以简单地对每个点找到第一个操作到他的操作,分开考虑横向和纵向操作,那么能碰到这个点的操作长度在一个连续区间内,动态开点线段树即可。

为什么不支持中途加点呢?不难发现,中途加的点,在被操作一次之后不一定与之前被操作过的点满足单调性。

考虑线段树分治,对于每次询问,都在点出现的时刻到询问时刻这个区间所对应线段树上 \(O(\log Q)\) 个段插入该查询点,然后对线段树上每个节点都跑一遍完整过程即可。整体复杂度两个 \(\log\)

感觉关键点就在于开头的那个性质,后面就是火箭毛毛虫大赛了。

code

const int M=2e6+5,Q=1e6+5;int n,m,q,c,qq;
struct node{int x,y,t;}ns[M];
struct cnode{int o,l;}cs[Q];
struct qnode{int x,y,t,be;}qs[Q];int cnt,rt[2];
int dat[Q*64],ls[Q*64],rs[Q*64];
void modify(int k,int v,int &x,int l=0,int r=1e9){if(!x)x=++cnt,ls[cnt]=rs[cnt]=0,dat[cnt]=inf;if(l==r)return chmin(dat[x],v),void();int m=l+r>>1;if(k<=m)modify(k,v,ls[x],l,m);else modify(k,v,rs[x],m+1,r);dat[x]=min(dat[ls[x]],dat[rs[x]]);
}
int query(int lq,int rq,int x,int l=0,int r=1e9){if(!x||lq>rq)return inf;if(lq<=l&&r<=rq)return dat[x];int m=l+r>>1,res=inf;if(lq<=m)chmin(res,query(lq,rq,ls[x],l,m));if(m<rq)chmin(res,query(lq,rq,rs[x],m+1,r));return res;
}auto rnd=mt19937_64(time(0));
struct FHQ{int ls[Q],rs[Q],lx[Q],ly[Q],pri[Q];void push(int x){if(~lx[x])qs[ls[x]].x=lx[ls[x]]=lx[x],qs[rs[x]].x=lx[rs[x]]=lx[x],lx[x]=-1;if(~ly[x])qs[ls[x]].y=ly[ls[x]]=ly[x],qs[rs[x]].y=ly[rs[x]]=ly[x],ly[x]=-1;}int merge(int a,int b){if(!a||!b)return a+b;if(pri[a]>pri[b]){push(a);rs[a]=merge(rs[a],b);return a;}else{push(b);ls[b]=merge(a,ls[b]);return b;}}void splitx(int x,int v,int &a,int &b){if(!x)return a=b=0,void();push(x);if(qs[x].x<=v)a=x,splitx(rs[x],v,rs[x],b);else b=x,splitx(ls[x],v,a,ls[x]);}void splity(int x,int v,int &a,int &b){if(!x)return a=b=0,void();push(x);if(qs[x].y>=v)a=x,splity(rs[x],v,rs[x],b);else b=x,splity(ls[x],v,a,ls[x]);}void upd(int x){if(!x)return;push(x);upd(ls[x]);upd(rs[x]);}void ins(int x,int &rt){int a,b,c;splitx(rt,qs[x].x,a,c);splity(a,qs[x].y,a,b);rt=merge(a,merge(x,merge(b,c)));}
}fhq;struct segment{vec<int> dat[Q<<2],tv[Q];void insert(int lq,int rq,int v,int x=1,int l=1,int r=c){if(lq>rq)return;if(lq<=l&&r<=rq)return dat[x].pub(v);int m=l+r>>1;if(lq<=m)insert(lq,rq,v,x<<1,l,m);if(m<rq)insert(lq,rq,v,x<<1|1,m+1,r);}void solve(int x=1,int l=1,int r=c){if(dat[x].size()){for(auto i:dat[x])fhq.ls[i]=fhq.rs[i]=0,fhq.lx[i]=fhq.ly[i]=-1,fhq.pri[i]=rnd();cnt=rt[0]=rt[1]=0;rep(i,l,r)modify(cs[i].l,i,rt[cs[i].o]);rep(i,l,r)tv[i].clear();for(auto i:dat[x]){qs[i].be=min(query(qs[i].y,n-qs[i].x,rt[0]),query(qs[i].x,n-qs[i].y,rt[1]));if(qs[i].be<=r)tv[qs[i].be].pub(i);}int rt=0;rep(i,l,r){if(cs[i].o){int a,b,c;fhq.splitx(rt,cs[i].l,a,c);fhq.splity(a,n-cs[i].l,a,b);qs[b].y=fhq.ly[b]=n-cs[i].l;rt=fhq.merge(fhq.merge(a,b),c);for(auto x:tv[i])qs[x].y=n-cs[i].l,fhq.ins(x,rt);}else{int a,b,c;fhq.splitx(rt,n-cs[i].l,a,c);fhq.splity(a,cs[i].l+1,a,b);qs[b].x=fhq.lx[b]=n-cs[i].l;rt=fhq.merge(fhq.merge(a,b),c);for(auto x:tv[i])qs[x].x=n-cs[i].l,fhq.ins(x,rt);}}fhq.upd(rt);}if(l<r){int m=l+r>>1;solve(x<<1,l,m);solve(x<<1|1,m+1,r);}}
}seg;inline void Main(){dat[0]=inf;cin>>n>>m>>q;rep(i,1,m)cin>>ns[i].x>>ns[i].y,ns[i].t=0;rep(i,1,q){int o;cin>>o;if(o==1){cin>>qs[++qq].x;qs[qq].t=c;}else if(o==2){cs[++c].o=0;cin>>cs[c].l;}else if(o==3){cs[++c].o=1;cin>>cs[c].l;}else{++m;cin>>ns[m].x>>ns[m].y;ns[m].t=c;}}q=qq;rep(i,1,q){int j=qs[i].x;qs[i].y=ns[j].y,qs[i].x=ns[j].x;seg.insert(ns[j].t+1,qs[i].t,i);}seg.solve();rep(i,1,q)cout<<qs[i].x<<" "<<qs[i].y<<"\n";
}
http://www.hskmm.com/?act=detail&tid=36042

相关文章:

  • 结对作业
  • CF简单构造小计
  • 深入认识ClassLoader - 一次投产失败的复盘
  • python 包来源镜像
  • CSharp基础复习-1
  • Linux7种文件类型
  • 米理 课程描述/学习计划/Study program
  • 2025年线路调压器厂家推荐榜:10kv线路调压器/单相线路调压器/三相线路调压器/助力电网稳定运行,优选品牌指南
  • Day15
  • 2025 智能/商超照明/灯具/灯光/源头厂家推荐榜:上海富明阳凭分区域光效领跑,生鲜 / 百货场景适配优选
  • 2025 艺考文化课推荐榜:济南震华学校 5 星领跑,全阶段体系适配基础补弱到高分冲刺
  • 2025 广州人力资源/派遣/劳务外包/人事代理/推荐榜:精典人才凭派遣合规 + 全场景适配领跑,企业用工优选
  • 2025 变电站厂家推荐榜最新资讯:撬装变电站/移动车载变电站/预制舱式变电站/移动变电站/预装式变电站/聚焦智能适配与可靠服务,这家企业成优选​
  • 题解:P12525 [Aboi Round 1] 私は雨
  • 完整教程:罗技G102有线鼠标自己维修教程
  • 挖矿-学校挖矿排查
  • 杂谈
  • 读书日记2
  • 鸿蒙hdc命令【杭州多测师】
  • 定位问题3:明明堆栈已经打印出来了,偏就是定位不出来?
  • Spring 统一机制处理 - 拦截器与适配器
  • 如何将海量纸质表格一键数字化?表格识别技术给出答案
  • 10.21 NOIP 模拟赛 T1. 小 h 学步
  • 深入解析:大数据Spark(六十六):Transformation转换算子sample、sortBy和sortByKey
  • 完整教程:web前端团队开发code review方案最佳实践
  • 加密货币如何改变金融诈骗的游戏规则
  • 最大值的不同统计方法
  • 远程服务器显示pyQt界面
  • java的字符和字符串
  • python_日志记录-loguru