【UOJ UNR #1】火车管理

时间:2022-09-23 18:48:58

来自FallDream的博客,未经允许,请勿转载,谢谢。


题面

考虑用可持久化线段树直接维护每个点在不同时刻,第一辆车的编号。

这样3操作就变成了区间赋值,1操作变成区间和

2操作的话,只需要查询一下现在这辆车的编号,再到历史版本去查一下上一辆车的编号就行了。

#include<iostream>
#include<cstdio>
#define MN 500000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,ty,rt[MN+],cnt=,num[MN+];
struct Tree{
int l,r,sum,val;
}T[MN*];
inline int newnode(int x,int flag=){if(flag)return x;T[++cnt]=T[x];return cnt;}
inline void Mark(int x,int len,int v){T[x].val=v;T[x].sum=len*num[v];}
inline void pushdown(int x,int lt,int rt)
{
int mid=lt+rt>>;
Mark(T[x].l=newnode(T[x].l),mid-lt+,T[x].val);Mark(T[x].r=newnode(T[x].r),rt-mid,T[x].val);T[x].val=;
} int Build(int l,int r)
{
int x=++cnt;
if(l!=r) T[x].l=Build(l,l+r>>),T[x].r=Build((l+r>>)+,r);
return x;
} int Query(int x,int l,int r,int lt,int rt)
{
if(l==lt&&r==rt) return T[x].sum;int mid=lt+rt>>;
if(T[x].val) pushdown(x,lt,rt);
if(r<=mid) return Query(T[x].l,l,r,lt,mid);
else if(l>mid) return Query(T[x].r,l,r,mid+,rt);
else return Query(T[x].l,l,mid,lt,mid)+Query(T[x].r,mid+,r,mid+,rt);
} int Query(int x,int k,int lt,int rt)
{
if(lt==rt) return T[x].val;int mid=lt+rt>>;
if(T[x].val) pushdown(x,lt,rt);
if(k>mid) return Query(T[x].r,k,mid+,rt);
else return Query(T[x].l,k,lt,mid);
} void Modify(int x,int l,int r,int lt,int rt,int v)
{
if(l==lt&&r==rt) {Mark(x,rt-lt+,v);return;}
int mid=lt+rt>>,flag=T[x].val;
if(T[x].val) pushdown(x,lt,rt);
if(r<=mid) Modify(T[x].l=newnode(T[x].l,flag),l,r,lt,mid,v);
else if(l>mid) Modify(T[x].r=newnode(T[x].r,flag),l,r,mid+,rt,v);
else Modify(T[x].l=newnode(T[x].l,flag),l,mid,lt,mid,v),
Modify(T[x].r=newnode(T[x].r,flag),mid+,r,mid+,rt,v);
T[x].sum=T[T[x].l].sum+T[T[x].r].sum;
}
int last=;
int main()
{
n=read();m=read();ty=read();rt[]=Build(,n);
for(int i=;i<=m;++i)
{
int op=read();rt[i]=newnode(rt[i-]);
if(op==) {int l=(read()+last*ty)%n+,r=(read()+last*ty)%n+;printf("%d\n",last=Query(rt[i],min(l,r),max(l,r),,n));}
if(op==) {int x=(read()+last*ty)%n+,y=Query(rt[i],x,,n);if(y!=) Modify(rt[i],x,x,,n,Query(rt[y-],x,,n));}
if(op==) {int l=(read()+last*ty)%n+,r=(read()+last*ty)%n+;num[i]=read();Modify(rt[i],min(l,r),max(l,r),,n,i);}
}
return ;
}

【UOJ UNR #1】火车管理的更多相关文章

  1. UNR &num;1 火车管理

    很简单 用一个线段树维护 1.答案 2.当前栈顶是什么时候push进来的 然后用一棵以时间为版本的可持久化线段树维护每个操作之后第一个覆盖到他的操作是哪个 就可以了 询问直接在线段树上询问,修改在两棵 ...

  2. 【UNR &num;1】火车管理

    题目描述 uoj 旗下有一个火车站,用来管理属于 uoj 的小火车. 火车站一共有 nn 条编号为 1,…,n1,…,n 的,只有一端的用来存放小火车的铁路,由于小火车特殊的构造,每条铁路可以停放无数 ...

  3. 【UNR &num;1】火车管理(主席树)

    [UNR #1]火车管理(主席树) 好好的代码被 \(extra\ test\) 卡常了...我就放一个目前最快的版本吧... 题意简化: 有 \(n\) 个栈,\(m\) 次操作. 将 \(x\) ...

  4. 「UOJ218」火车管理

    「UOJ218」火车管理 解题思路:观察发现,在弹出 \(x\) 之前,它前面这个元素都是保持不变的,所以可以用一棵可持久化线段树维护每一个栈顶元素的插入时间,每次找到当前时间\(-1\) 的版本就可 ...

  5. UOJ&num;218&period; 【UNR &num;1】火车管理 线段树 主席树

    原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ218.html 题解 如果我们可以知道每次弹出栈之后新的栈顶是什么,那么我们就可以在一棵区间覆盖.区间求和 ...

  6. UOJ &num;218&period; 【UNR &num;1】火车管理

    Description Solution 实际上添加问题就是一个线段树区间覆盖问题,打标记就好 对于弹栈操作比较难搞,实际上也就是一个历史查询,我们不需要保存栈中的每一个元素,我们通过查找历史状态就可 ...

  7. 【UOJ UNR &num;1】火车管理 可持久化线段树

    用可持久化线段树维护每个站的第一辆车和每个站的前一次更新的位置即可. #include<iostream> #include<cstring> #include<cstd ...

  8. Uoj &num;218&period; 【UNR &num;1】火车管理 可持久化线段树&plus;思维

    Code: #include<bits/stdc++.h> #define maxn 500005 using namespace std; int n,Q,ty,lastans=0; i ...

  9. UOJ 218 火车管理

    http://uoj.ac/problem/218 思路:建立一个可持久化线段树,代表这个位置的火车是哪辆,然后再弄一个线段树维护答案. 如果询问,直接询问线段树. 如果区间压入,直接在主席树上面压入 ...

随机推荐

  1. 电商系统中的商品模型的分析与设计&mdash&semi;续

    前言     在<电商系统中的商品模型的分析与设计>中,对电商系统商品模型有一个粗浅的描述,后来有博友对货品和商品的区别以及属性有一些疑问.我也对此做一些研究,再次简单的对商品模型做一个介 ...

  2. oracle---包--laobai

    包(package) 作用:逻辑对象的一种.对相关存储过程.函数.变量的封装. a 封装,便于调用 b 统一授权 系统内置包:dbms_output.用于输出. standard:常用的函数.异常的定 ...

  3. 【转载&sol;修改】ScrollLayout代码修正,追加模仿viewpager滚动速度

    组件作用为类似ViewPager但直接插视图的横向滚动容器. 修改自:http://blog.csdn.net/yaoyeyzq/article/details/7571940 在该组件基础上修正了滚 ...

  4. XSD (xml Schema Definition)

    .xsd文件是定义DataSet的XML文件,利用XML文件的结构优势容易可视化地设计DataSet,设计完它会生成相应的.cs文件,里面的内容就是对应的类型化的DataSet.你的代码里的DataA ...

  5. 如何自定义JSR-303标准的validator

    在web应用中为了保证数据的有效性而对用户提交的表单数据是必需的,而前台客户端的验证例如javascript并不总是那么安全和可靠,这样我们就需要一个健壮的后台验证框架来处理这个问题.好在java发布 ...

  6. QQ信鸽推送

    闲来无事,看看腾讯的信鸽推送! 优点: 1.毕竟大腿出的东西,不会太差 2.集成快 3.推送效率高,功能强,APP后台被杀的情况下同样能接受到推送. 废话少说,直接上代码: 源代码.zip

  7. SQL Server 数据恢复到指点时间点&lpar;完整恢复&rpar;

    SQL Server 数据恢复到指点时间点(完整恢复) 高文龙关注2人评论944人阅读2017-03-20 12:57:12 SQL Server 数据恢复到指点时间点(完整恢复) 说到数据库恢复,其 ...

  8. mount 命令用法

    mount 功能: 加载指定的文件系 统:mount可将指定设备中指定的文件系统加载到 Linux目录下(也就是装载点).可将经常使用的设备写入文件/etc/fastab,以使系 统在每次启动时自动加 ...

  9. fastscript例子一

    fastscript例子一   fastscript例子一 unit Unit1; interface usesWinapi.Windows, Winapi.Messages, System.SysU ...

  10. WPS 2019 去除自动升级 和 广告、及优化的点

    搜狗输入法 里面的快捷键会影响wps的快捷键功能,需要关掉"搜狗输入法"里面的快捷键 1. 2.去除自动升级功能 3.去除 广告 WPS 2019 流程图(断网): 思维导图: 流 ...