AC日记——最大数 洛谷 P1198 [JSOI2008]
2024-04-09 22:27:25
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入输出格式
输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入样例#1：
5 100
A 96
Q 1
A 97
Q 1
Q 2
输出样例#1：
96
93
96
说明
[JSOI2008]
思路：
离线做法，先把所有的操作都给存下来
分别记录查询和添加
然后按添加的操作数建树
然后剩下的不断进行查询操作同时也不断的更新单点
轻松ac
来，上代码：
#include <cstdio>
#include <iostream> using namespace std; class node {
public: int l,r,mid; long long int dis; void mid_()
{
mid=(l+r)>>;
}
};
class node tree[]; int m,d,num_q=,q_l[],q_r[];
int num_a,a_[],cnt=; long long int t; inline void tree_up(int now)
{
if(tree[now<<].dis>tree[now<<|].dis)
{
tree[now].dis=tree[now<<].dis;
}
else tree[now].dis=tree[now<<|].dis;
} void tree_build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r;
if(l==r)
{
tree[now].dis=a_[++cnt];
return ;
}
tree[now].mid_();
tree_build(now<<,l,tree[now].mid);
tree_build(now<<|,tree[now].mid+,r);
tree_up(now);
} void tree_change(int now,int to)
{
if(tree[now].l==tree[now].r&&tree[now].l==to)
{
tree[now].dis=(tree[now].dis+t)%d;
return ;
}
if(to>tree[now].mid) tree_change(now<<|,to);
else tree_change(now<<,to);
tree_up(now);
} long long int tree_query(int now,int l,int r)
{
if(tree[now].l==l&&tree[now].r==r)
{
return tree[now].dis;
}
if(l>tree[now].mid) return tree_query(now<<|,l,r);
else if(r<=tree[now].mid) return tree_query(now<<,l,r);
else return max(tree_query(now<<,l,tree[now].mid),tree_query(now<<|,tree[now].mid+,r));
} int main()
{
char ch;
int now_;
scanf("%d%d",&m,&d);
for(int i=;i<=m;i++)
{
cin>>ch>>now_;
if(ch=='Q')
{
num_q++;
q_l[num_q]=num_a-now_+;
q_r[num_q]=num_a;
}
else
{
num_a++;
a_[num_a]=now_;
}
}
tree_build(,,num_a);
cnt=;
for(int i=;i<=num_q;i++)
{
while(cnt<q_r[i])
{
tree_change(,++cnt);
}
t=tree_query(,q_l[i],q_r[i]);
printf("%d\n",t);
}
return ;
}
最新文章
- cookie 和session 的区别详解
- NUMA架构的CPU -- 你真的用好了么？
- hibernate简单注释（一）
- SpringMVC类型转换、数据绑定详解[附带源码分析]
- hiho一下116周 网络流
- Git入门详解
- 通过css代码使边框变圆角（ie9以下浏览器不支持）
- jq 7种实例化
- 【HDOJ】1160 FatMouse's Speed
- POJ 3294 Life Forms（后缀数组+二分答案）
- 【iOS】7.4 定位服务->2.1.3.3 定位 - 官方框架CoreLocation 功能3:区域监听
- 4. leetcode 461. Hamming Distance
- POJ 3625 最小生成树 Prim C++
- 第5章 不要让线程成为脱缰的野马（Keeping your Threads on Leash） ----初始化一个线程
- Docker（三）：Docker仓库配置
- docker基本命令使用
- hibernate 和mybatis
- jQuery操作下拉框的text值和val值
- Use GDB to debug a C++ program called from a shell script
- c需要注意的细节