北京八十中 TEST1 数列

北京八十中 TEST1 数列

​​ 【题目描述】 一个序列有 N 个数，最初每个数均为正无穷大。一共进行 Q 次事件。事件有两种类型： 1. ‘M’ X A 将第 A 个数修改为 X； 2. ‘D’ Y B 查询当前从 B 到 N 的第一个小于或等于 Y 的数的位置，无解返回-1。 已知每个数最多被修改一次（即，数据中所有 1 类事件的 A 互不相同） 。

【输入格式】 输入文件名为 deda.in。 第一行，两个整数 N, Q。 接下来 Q 行，每行描述一次事件。

【输出格式】 输出文件名为 deda.out。 输出若干行，每行一个整数，依次表示每次查询事件的结果。

【样例输入 1】 3 4 M 10 3 M 5 1 D 20 2 D 5 1

【样例输出 1】 3 1

【样例解释 1】 两次修改事件后，序列变成 5, +oo, 10。第一次查询事件(‘D’ 20 2)，返回第 3 个数。第二次查询事件(‘D’ 5 1)，返回第 1 个数。

【样例输入 2】 10 10 M 20 10 D 1 9 M 2 3 D 17 10 M 20 2 D 8 2 M 40 1 D 25 2 M 33 9 D 37 9

5

【样例输出 2】 -1 -1 3 2 9

【数据规模与约定】 对于 40%的数据，2 ≤ N, Q ≤ 5000. 对于 100%的数据，2 ≤ N, Q ≤ 2*105, 1 ≤ A, B ≤ N, 1 ≤ X, Y ≤ 109.

数据结构题 维护一下区间最小值 然后每次去二分找到这个位置以后的第一个小于等于y

#include#includeusing namespace std;#define N 110000#define inf 0x3f3f3f3finline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}struct node{ int left,right,min;}tree[N<<2];struct node1{ int pos,min;};int num;void build(int &x,int l,int r){ x=++num;tree[x].min=inf; if (l==r) return; int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].min=min(tree[l].min,tree[r].min);}void insert1(int x,int l,int r,int p,int v){ if (l==r) {tree[x].min=v;return;} int mid=l+r>>1; if (p<=mid) insert1(tree[x].left,l,mid,p,v);else insert1(tree[x].right,mid+1,r,p,v); update(x);}node1 query(int x,int l,int r,int pos,int v){ node1 tmp; if (tree[x].min==inf) {tmp.min=inf;return tmp;} if (l==r) { tmp.min=tree[x].min;tmp.pos=l;return tmp; } int mid=l+r>>1;node1 res;res.min=inf; if (mid>=pos&&tree[tree[x].left].min<=v) { tmp=query(tree[x].left,l,mid,pos,v); if (tmp.min

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。