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

AT_joisc2021_c フードコート (Foodcourt)

换维扫描线好题。

发现删除操作会出现过删(即删除的个数大于序列中元素数),这个很难处理。

思考一下应该能想到将每次询问查询的 \(b\to cnt_{del}+b\) 其中 \(cnt_{del}\) 为在该询问之前这个序列删除的数的个数,这样就不用删除只需插入即可。但是这样对于每个删除操作操作的每个序列都要求出删了多少个数,很困难,时间复杂度不能接受。

对于一个询问 \((A,B)\) 发现如果能找到序列 \(A\) 在此询问之前操作序列中最后一次出现过删的操作,对于该位置后的操作序列对 \(B\) 的贡献就可以用上文的方法求,而该操作及之前加入的所有元素都已经清空,只需将 \(b\to cnt_{add}\) 即可,这里的 \(cnt_{add}\) 表示该操作前加入的元素个数和。

扫描线。以序列编号为做扫描线,以操作编号建立线段树,叶子节点 \([i,i]\) 上维护第 \(1\) 到第 \(i\) 次操作的过程中共加的元素总数(不计删除)记为 \(add_i\) 以及经过 \(1\)\(i\) 操作加的元素总数减去删除的元素总数记为 \(sum_i\)(不考虑过删),节点 \([l,r]\) 维护 \(\max_{i=l}^{r}add_i,\min_{i=l}^{r}sum_i\)

下文区间 \([l,r]\) 某值记为 \(f(l,r)\)\(f(i,i)\) 简记为 \(f(i)\)

将修改 \((l,r,c,k)\) 拆分成在第 \(l\) 个序列将 \([id,q]\) 区间加 \(k\),在第 \(r+1\) 个序列将 \([id,q]\) 区间加 \(-k\),其中 \(id\) 为这个操作是操作序列中第几个操作,\(q\) 是总操作数(均不计询问)。

假设当前询问操作前进行了 \(x\) 次操作,线段树上二分出 \([1,x]\) 中最后一个 \(sum\) 等于 \(\min_{i=l}^{r} sum\) 的位置,就是上文最后一次出现过删的操作(因为对于 \(i<j,sum_j>sum_i\) 则第 \(i\) 次操作到第 \(j\) 次操作的变化量 \(<0\) 即删除数大于加入数,出现过删),记为 \(p\)。假设询问 \((A,B)\) 前有 \(m\) 此操作,在线段树上二分出 \([p,m]\) 中第一个 \(add\) 大于等于 \(add(m)-sum(m)+sum(p)+B\) 的位置,记为 \(p_1\)。上述值即为第二段中贡献 \(B\) 的值 \(add(m)-sum(m)+sum(p)=del(m)+sum(p)=add(p)+del(p+1,m)\),其中 \(del\) 是删除的元素个数。则第 \(p_1\) 次操作加入元素即为答案。

时间复杂度 \(O(n\log n)\)

// Problem: フードコート (Foodcourt)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_joisc2021_c
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
const int N=3e5+5;int num[N],ans[N];
struct oper{int opt,id,k,c;};vector<oper>g[N],a[N];
struct node{int l,r,add,sum,la,ls;}tr[N<<2];
void pushup(int u){tr[u].add=max(tr[u<<1].add,tr[u<<1|1].add),tr[u].sum=min(tr[u<<1].sum,tr[u<<1|1].sum);}
void pd(int u){if(tr[u].ls)tr[u<<1].ls+=tr[u].ls,tr[u<<1|1].ls+=tr[u].ls,tr[u<<1].sum+=tr[u].ls,tr[u<<1|1].sum+=tr[u].ls,tr[u].ls=0;if(tr[u].la)tr[u<<1].la+=tr[u].la,tr[u<<1|1].la+=tr[u].la,tr[u<<1].add+=tr[u].la,tr[u<<1|1].add+=tr[u].la,tr[u].la=0;
}
void build(int u,int l,int r){tr[u]={l,r};if(l==r)return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);}
void add(int u,int l,int r,int d){if(tr[u].l>=l&&tr[u].r<=r)return tr[u].add+=d,tr[u].la+=d,void();pd(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)add(u<<1,l,r,d);if(r>mid)add(u<<1|1,l,r,d);pushup(u);
}
void adds(int u,int l,int r,int d){if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum+=d,tr[u].ls+=d,void();pd(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid)adds(u<<1,l,r,d);if(r>mid)adds(u<<1|1,l,r,d);pushup(u);
}
int gtad(int u,int x){if(tr[u].l==tr[u].r)return tr[u].add;pd(u);int mid=tr[u].l+tr[u].r>>1;return (x<=mid?gtad(u<<1,x):gtad(u<<1|1,x));
}
int gtsum(int u,int l,int r){if(!l&&!r)return 0;if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;pd(u);int mid=tr[u].l+tr[u].r>>1,mn=1e16;if(l<=mid)mn=min(mn,gtsum(u<<1,l,r));if(r>mid)mn=min(mn,gtsum(u<<1|1,l,r));return mn;
}
int askad(int u,int l,int r,int d){if(tr[u].add<d||tr[u].l>r||tr[u].r<l)return 0;if(tr[u].l==tr[u].r)return tr[u].l;pd(u);int w=askad(u<<1,l,r,d);return (w?w:askad(u<<1|1,l,r,d));
}
int asksum(int u,int l,int r,int d){if(tr[u].sum>d||tr[u].l>r||tr[u].r<l)return 0;if(tr[u].l==tr[u].r)return tr[u].l;pd(u);int w=asksum(u<<1|1,l,r,d);return (w?w:asksum(u<<1,l,r,d));
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,q,c0=0,c1=0;cin>>n>>m>>q;for(int i=1,opt,l,r,c,k;i<=q;i++){cin>>opt>>l>>r;if(opt==1)cin>>num[++c0]>>k,g[l].push_back(oper{1,c0,k}),g[r+1].push_back(oper{1,c0,-k});else if(opt==2)++c0,cin>>k,g[l].push_back(oper{2,c0,-k}),g[r+1].push_back(oper{2,c0,k});else a[l].push_back(oper{3,++c1,c0,r});}build(1,1,c0);for(int i=1;i<=n;i++){for(oper j:g[i]){if(j.opt==1)add(1,j.id,c0,j.k);adds(1,j.id,c0,j.k);}for(oper j:a[i]){int mn=gtsum(1,1,j.k);int beg=(mn<0?asksum(1,1,j.k,mn):0);ans[j.id]=num[askad(1,beg+1,j.k,gtad(1,j.k)-gtsum(1,j.k,j.k)+gtsum(1,beg,beg)+j.c)];}}for(int i=1;i<=c1;i++)cout<<ans[i]<<endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=32423

相关文章:

  • SPP question regarding Issues Due To Gaming Spoofers
  • 类型安全ORM的高并发场景解决方案 - 实践
  • L06_mybatis读取MySQL数据库(懵逼版)
  • 提供给第三方接口的验证方法
  • 【2025最新】6款免费DLL修复工具推荐:彻底解决“XXX.dll缺失”问题!
  • 2025 年注浆管生产厂家最新推荐排行榜:聚焦 0.3mm 精度与国企合作案例,助力基建企业精准挑选优质供应商
  • 2025 年试验箱厂家 TOP 企业品牌推荐排行榜,氙灯老化 / 紫外老化 / 冷热冲击 / 恒温恒湿 / 高低温 / 快速温变 / 盐水喷雾 / 高温老化 / 砂尘 / 淋雨试验箱公司推荐!
  • 系统修复
  • 什么是vibe ?
  • 2025年10月试验箱厂家最新推荐排行榜:氙灯老化试验箱,紫外老化试验箱,冷热冲击试验箱,恒温恒湿试验箱公司推荐!
  • AI时代我们需要更多开发者:Shalini Kurapati的技术洞察
  • 新一代虚拟助手AI技术挑战赛启动
  • CSS各种选择器
  • adobe illustrator中鼠标拖动移动幅度大
  • python的字符串方法示例
  • 经典视觉跟踪算法的MATLAB实现
  • aardio 调用vb函数
  • 2025年玻璃杯趋势:某某科技圆润咖啡杯引领健康饮水新潮流
  • 2025 年密封线优质厂家最新推荐榜:权威甄选螺纹、高强度等多类型密封线质量与技术双优企业液态/亚麻/防腐/耐高温密封线厂家推荐
  • 微算法科技(MLGO)发布隐私与能量感知联盟博弈算法,重塑边缘摄像头网络架构,推动物联网智能演进
  • adobe illustrator中设置键盘增量
  • 焦虑
  • 从此,不再开口就紧张
  • 基于Qt实现百度地图路径规划功能
  • 求职,从大一开始
  • 基于C#的湿度上位机实现方案
  • 2025 年珠澳宠物托运公司联系方式推荐:爱宠国际,港澳内地宠物运输的安全专业之选
  • 男人要懂心理学
  • 斩获双项第一,天翼云问鼎中国医学影像云解决方案市场!
  • 2025 年铝单板厂家最新推荐榜:聚焦西南及全国头部企业,精选 实力品牌助力项目采购