[JSOI2008] 最大数
2024年12月25日大约 2 分钟
树状数组
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int m, d;
// 单点变大、前缀最值查询
int T[MAXN + 5];
void update(int x, int y)
{
for (int i = x; i <= m; i += (i & -i))
T[i] = max(T[i], y);
}
int query(int x)
{
int res = -1;
for (int i = x; i >= 1; i -= (i & -i))
res = max(res, T[i]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> d;
for (int i = 1; i <= m; i++)
T[i] = -1;
int t = 0;
int len = 0;
for (int i = 1; i <= m; i++)
{
char op;
long long x;
cin >> op >> x;
if (op == 'A')
{
// 在末尾插入一个数
// 强制在线:插入的数为(上一次查询的答案+x)%d
x = ((t + x) % d + d) % d;
len++;
// 插入到正序的第len个,树状数组中就是从最后位置m倒序的第len个
update(m - len + 1, x);
}
if (op == 'Q')
{
// 查询末尾 x 个数的最大值
t = query(m - (len - x + 1) + 1);
cout << t << "\n";
}
}
return 0;
}
线段树
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int m;
long long d;
// 区间赋值、区间最值查询
namespace SegTree
{
int t[MAXN * 4 + 5];
// 表示当前节点对应区间全部都要赋值为 tag[now]
// 如果 tag[now] 为 -1,即没有全部赋值
int tag[MAXN * 4 + 5];
void build(int now, int l, int r)
{
tag[now] = -1;
if (l == r)
{
// 如果是基于 a[] 建树,就改成 t[now]=a[l];
t[now] = -1;
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid);
build(now * 2 + 1, mid + 1, r);
t[now] = max(t[now * 2], t[now * 2 + 1]);
}
// 下传一层懒标记
void down(int now, int l, int r)
{
if (l == r || tag[now] == -1)
return;
t[now * 2] = tag[now];
tag[now * 2] = tag[now];
t[now * 2 + 1] = tag[now];
tag[now * 2 + 1] = tag[now];
tag[now] = -1;
}
// a[x]~a[y] 赋值为 z
void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
t[now] = z;
tag[now] = z;
return;
}
down(now, l, r);
int mid = (l + r) / 2;
if (x <= mid)
update(now * 2, l, mid, x, y, z);
if (mid + 1 <= y)
update(now * 2 + 1, mid + 1, r, x, y, z);
t[now] = max(t[now * 2], t[now * 2 + 1]);
}
// 查询 a[x]~a[y] 的最大值
int query(int now, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return t[now];
down(now, l, r);
int res = -1; // 设置为小于所有数的值
int mid = (l + r) / 2;
if (x <= mid)
res = max(res, query(now * 2, l, mid, x, y));
if (mid + 1 <= y)
res = max(res, query(now * 2 + 1, mid + 1, r, x, y));
return res;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> d;
SegTree::build(1, 1, m);
int t = 0;
int len = 0;
for (int i = 1; i <= m; i++)
{
char op;
long long x;
cin >> op >> x;
if (op == 'A')
{
// 在末尾插入一个数
// 强制在线:插入的数为(上一次查询的答案+x)%d
x = ((t + x) % d + d) % d;
len++;
SegTree::update(1, 1, m, len, len, x);
}
if (op == 'Q')
{
// 查询末尾 x 个数的最大值
t = SegTree::query(1, 1, m, len - x + 1, len);
cout << t << "\n";
}
}
return 0;
}