网站初期缺点,杭州seo论坛,网页设计各个部分的尺寸,王烨医生[JSOI2008] 最大数
传送门
题目描述
现在请求你维护一个数列#xff0c;要求提供以下两种操作#xff1a;
查询操作。
语法#xff1a;Q L
功能#xff1a;查询当前数列中末尾 L L L 个数中的最大的数#xff0c;并输出这个数的值。
限制#xff1a; L L L 不超过…[JSOI2008] 最大数
传送门
题目描述
现在请求你维护一个数列要求提供以下两种操作
查询操作。
语法Q L
功能查询当前数列中末尾 L L L 个数中的最大的数并输出这个数的值。
限制 L L L 不超过当前数列的长度。 ( L 0 ) (L 0) (L0)
插入操作。
语法A n
功能将 n n n 加上 t t t其中 t t t 是最近一次查询操作的答案如果还未执行过查询操作则 t 0 t0 t0并将所得结果对一个固定的常数 D D D 取模将所得答案插入到数列的末尾。
限制 n n n 是整数可能为负数并且在长整范围内。
注意初始时数列是空的没有一个数。
输入格式
第一行两个整数 M M M 和 D D D其中 M M M 表示操作的个数 D D D 如上文中所述。
接下来的 M M M 行每行一个字符串描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作你应该按照顺序依次输出结果每个结果占一行。
样例 #1
样例输入 #1
5 100
A 96
Q 1
A 97
Q 1
Q 2样例输出 #1
96
93
96提示
数据规模与约定
对于全部的测试点保证 1 ≤ M ≤ 2 × 1 0 5 1 \leq M \leq 2 \times 10^5 1≤M≤2×105 1 ≤ D ≤ 2 × 1 0 9 1 \leq D \leq 2 \times 10^9 1≤D≤2×109。
注明 以上来自洛谷 以上来自洛谷 以上来自洛谷
解题思路
前置知识
并查集。队列。
正文
将一个数插入单调队列时可以将被删除的数的父亲标记为插入的数在查找时只要找到查找的数的根此时根上的数值即为答案。时间复杂度 O ( n ) O(n) O(n)。
具体题解 如下。这里有一个梗猜猜是啥
AC Code
#includebits/stdc.h
using namespace std;
char buf[1048576], *p1, *p2;
templatetypename Tinline void Quick_Write(T x) {if (x 0) putchar(-), x -x;if (x 9) Quick_Write(x / 10);putchar(x % 10 0);return;
}
struct node {long long x;int y;
} Arry[200005];
int m;
long long d, x;
int Total, Length_Count, f[200005];
long long Temp, T[200005];
char ch[3];
inline int Find(int x) {if (x ! f[x]) f[x] Find(f[x]);return f[x];
}
signed main() {scanf(%d%lld, m, d);for (register int i 1; i m; i) {getchar(), scanf(%s, ch), scanf(%lld, x);if (ch[0] A) {x Temp, x % d, Total, T[Total] x, f[Total] Total;while (x Arry[Length_Count].x Length_Count) f[Arry[Length_Count].y] Total, Length_Count--;Arry[Length_Count].x x, Arry[Length_Count].y Total;} else {x Total - x 1;int y Find(x);Temp T[y], Quick_Write(Temp), puts();}}return 0;
}
