题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L 不超过当前数列的长度。(L > 0)
2、 插入操作。
语法：A n
功能：将 n 加上 t，其中 t 是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数 D 取模，将所得答案插入到数列的末尾。
限制：n 是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入格式
第一行两个整数，M 和 D，其中 M 表示操作的个数，D 如上文中所述。
接下来的 M 行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入 #1
5 100
A 96
Q 1
A 97
Q 1
Q 2
输出 #1
96
93
96
数据范围
代码
板子题
普通线段树
#include<iostream> using namespace std; const int N = 200010; #define int long long int m, p; struct node { int l, r; int v; }tr[4 * N]; void pushup(int u) { tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v); } 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); return ; } int query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1; int v = 0; if(l <= mid) v = query(u << 1, l, r); if(r > mid) v = max(v, query(u << 1 | 1, l, r)); return v; } void modify(int u, int x, int v) { if(tr[u].l == x && tr[u].r == x) tr[u].v = v; else { int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } return ; } signed main() { int n = 0, last = 0; cin >> m >> p; build(1, 1, m); char op; int x; while(m--) { cin >> op >> x; if(op == 'Q') { last = query(1, n - x + 1, n); cout << last << endl; } else { n += 1; modify(1, n, (last + x) % p); } } return 0; }
- 动态开点
#include <iostream> using namespace std; const int N = 200010; struct node { int l, r; int s; } tr[N << 1]; int n, m, mod, last, root, idx; void pushup(int p) { tr[p].s = max(tr[tr[p].l].s, tr[tr[p].r].s); } void modify(int &p, int l, int r, int ql, int qr, int x) { if(!p) p = ++idx; if(l >= ql && r <= qr) { tr[p].s = x; return ; } int mid = l + r >> 1; if(ql <= mid) modify(tr[p].l, l, mid, ql, qr, x); if(qr > mid) modify(tr[p].r, mid + 1, r, ql, qr, x); pushup(p); } int query(int p, int l, int r, int ql, int qr) { if(!p) return 0; if(l >= ql && r <= qr) return tr[p].s; int mid = l + r >> 1; int v = 0; if(ql <= mid) v = max(v, query(tr[p].l, l, mid, ql, qr)); if(qr > mid) v = max(v, query(tr[p].r, mid + 1, r, ql, qr)); return v; } int main() { cin >> m >> mod; char op; int x; while(m--) { cin >> op >> x; if(op == 'Q') { last = query(root, 1, N, n - x + 1, n); cout << last << endl; } if(op == 'A') { x = ((long long)x + last) % mod; ++n; modify(root, 1, N, n, n, x); } } return 0; }
