結果
| 問題 |
No.3026 Range LCM (Online Version)
|
| コンテスト | |
| ユーザー |
 t98slider
|
| 提出日時 | 2025-02-15 01:44:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,293 bytes |
| コンパイル時間 | 5,215 ms |
| コンパイル使用メモリ | 284,536 KB |
| 実行使用メモリ | 316,708 KB |
| 最終ジャッジ日時 | 2025-02-15 01:45:50 |
| 合計ジャッジ時間 | 75,160 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 TLE * 8 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = atcoder::modint998244353;
#define BL 58
#define BL2 447
// 59 ~ 447
//2次元セグ木(自動座圧)
template <class S, S (*op)(S, S), S (*e)(), class C = long long int> struct segtree2D_lite {
int H, logH;
std::vector<int> logW, W;
std::vector<C> Yc;
std::vector<std::vector<int>> parent;
std::vector<std::vector<std::pair<int, int>>> child;
std::vector<std::vector<C>> Xc;
std::vector<std::pair<C, C>> preorder;
std::vector<std::vector<S>> d;
segtree2D_lite() {}
void insert(C y, C x){
preorder.emplace_back(y, x);
}
void build(){
std::sort(preorder.begin(), preorder.end());
Yc.resize(preorder.size());
for(int i = 0; i < (int)(preorder.size()); i++)Yc[i] = preorder[i].first;
Yc.erase(std::unique(Yc.begin(), Yc.end()), Yc.end());
logH = ceil_pow2(Yc.size());
H = 1 << logH;
Xc.resize(2 * H), d.resize(2 * H);
logW.resize(2 * H), W.resize(2 * H);
parent.resize(2 * H), child.resize(H);
for(int i = 0, y_id = 0; i < (int)(preorder.size()); i++){
while(Yc[y_id] < preorder[i].first)y_id++;
Xc[y_id + H].emplace_back(preorder[i].second);
}
for(int y = 2 * H - 1; y >= H; y--){
Xc[y].erase(std::unique(Xc[y].begin(), Xc[y].end()), Xc[y].end());
parent[y].resize(Xc[y].size());
logW[y] = ceil_pow2(Xc[y].size());
W[y] = 1 << logW[y];
d[y].resize(2 * W[y], e());
}
for(int y = H - 1; y >= 1; y--){
int Ly_id = 2 * y, Ry_id = 2 * y + 1;
int Lx_id = 0, Rx_id = 0;
while(Lx_id < Xc[Ly_id].size() && Rx_id < Xc[Ry_id].size()){
if(Xc[Ly_id][Lx_id] == Xc[Ry_id][Rx_id]){
parent[Ly_id][Lx_id] = parent[Ry_id][Rx_id] = Xc[y].size();
Xc[y].emplace_back(Xc[Ly_id][Lx_id]);
child[y].emplace_back(Lx_id + W[Ly_id], Rx_id + W[Ry_id]);
Lx_id++, Rx_id++;
}else if(Xc[Ly_id][Lx_id] < Xc[Ry_id][Rx_id]){
parent[Ly_id][Lx_id] = Xc[y].size();
Xc[y].emplace_back(Xc[Ly_id][Lx_id]);
child[y].emplace_back(Lx_id + W[Ly_id], 0);
Lx_id++;
}else{
parent[Ry_id][Rx_id] = Xc[y].size();
Xc[y].emplace_back(Xc[Ry_id][Rx_id]);
child[y].emplace_back(0, Rx_id + W[Ry_id]);
Rx_id++;
}
}
while(Lx_id < Xc[Ly_id].size()){
parent[Ly_id][Lx_id] = Xc[y].size();
Xc[y].emplace_back(Xc[Ly_id][Lx_id]);
child[y].emplace_back(Lx_id + W[Ly_id], 0);
Lx_id++;
}
while(Rx_id < Xc[Ry_id].size()){
parent[Ry_id][Rx_id] = Xc[y].size();
Xc[y].emplace_back(Xc[Ry_id][Rx_id]);
child[y].emplace_back(0, Rx_id + W[Ry_id]);
Rx_id++;
}
parent[y].resize(Xc[y].size());
logW[y] = ceil_pow2(Xc[y].size());
W[y] = 1 << logW[y];
d[y].resize(2 * W[y], e());
}
}
void set(C py, C px, S v){
int y = std::lower_bound(Yc.begin(), Yc.end(), py) - Yc.begin();
y += H;
int x = std::lower_bound(Xc[y].begin(), Xc[y].end(), px) - Xc[y].begin(), nxt_x = parent[y][x];
x += W[y];
d[y][x] = v;
while(x >>= 1)updateX(y, x);
while(y >>= 1){
x = nxt_x, nxt_x = parent[y][x];
d[y][x + W[y]] = op(d[2 * y][child[y][x].first], d[2 * y + 1][child[y][x].second]);
x += W[y];
while(x >>= 1)updateX(y, x);
}
}
S get(C py, C px){
int y = std::lower_bound(Yc.begin(), Yc.end(), py) - Yc.begin();
y += H;
int x = std::lower_bound(Xc[y].begin(), Xc[y].end(), px) - Xc[y].begin();
return d[y][x + W[y]];
}
S prod(C lpy, C lpx, C rpy, C rpx){
int ly = std::lower_bound(Yc.begin(), Yc.end(), lpy) - Yc.begin();
int ry = std::lower_bound(Yc.begin(), Yc.end(), rpy) - Yc.begin();
S sml = e(), smr = e();
ly += H, ry += H ;
while (ly < ry) {
if (ly & 1) sml = op(sml, yline_prod(lpx, rpx , ly++));
if (ry & 1) smr = op(yline_prod(lpx, rpx , --ry), smr);
ly >>= 1, ry >>= 1;
}
return op(sml, smr);
}
S yline_prod(C lpx, C rpx, int y){
int lx = std::lower_bound(Xc[y].begin(), Xc[y].end(), lpx) - Xc[y].begin();
int rx = std::lower_bound(Xc[y].begin(), Xc[y].end(), rpx) - Xc[y].begin();
S sml = e(), smr = e();
lx += W[y], rx += W[y] ;
while (lx < rx) {
if (lx & 1) sml = op(sml, d[y][lx++]);
if (rx & 1) smr = op(d[y][--rx], smr);
lx >>= 1, rx >>= 1;
}
return op(sml, smr);
}
private:
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
void updateX(int yi, int xi) { d[yi][xi] = op(d[yi][2 * xi], d[yi][2 * xi + 1]); }
};
template <class T, T (*op)(T, T), T (*e)()> struct SparseTable {
int n, LOGV;
std::vector<std::vector<T>> table;
std::vector<int> log_table;
SparseTable() {}
SparseTable(const std::vector<T> &v) : n(v.size()), LOGV(std::__lg(std::max(n, 1)) + 1),
log_table(n + 1), table(LOGV, std::vector<T>(n)) {
std::copy(v.begin(), v.end(), table[0].begin());
for(int i = 1; i < LOGV; i++) {
for(int j = 0; j + (1 << i) <= n; j++) {
table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
for(int i = 2; i <= n; i++) {
log_table[i] = log_table[i >> 1] + 1;
}
}
T prod(int l, int r){
assert(0 <= l && l <= r && r <= n);
if(l == r) return e();
int b = log_table[r - l];
return op(table[b][l], table[b][r - (1 << b)]);
}
};
mint op(mint lhs, mint rhs){ return lhs * rhs; }
mint e(){return mint::raw(1);}
int op2(int lhs, int rhs){return max(lhs, rhs);}
constexpr int e2(){return 1;}
ll op3(ll lhs, ll rhs){return lhs | rhs;}
constexpr ll e3(){return 0;}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
constexpr int r = 200000;
vector<int> id(r + 1), tb(r + 1), cnt(r + 1), p2, a(n, 1), pre(r + 1, -1);
tb[0] = tb[1] = -1;
int pcnt = 0;
for(int i = 2; i <= r; i++){
if(tb[i] != 0) continue;
if(i <= BL) id[i] = pcnt++;
else if(i <= BL2){
id[i] = p2.size();
p2.emplace_back(i);
}
for(int j = i; j <= r; j += i){
if (tb[j] == 0) tb[j] = i;
}
}
const int m = pcnt;
vector<vector<int>> seg2(m, vector<int>(n, 1));
vector<vector<ll>> seg3(3, vector<ll>(n));
segtree2D_lite<mint, op, e, int> seg;
for(int i = 0; i < n; i++){
int v;
cin >> v;
while(v != 1){
if(tb[v] <= BL) seg2[id[tb[v]]][i] *= tb[v];
else if(tb[v] <= BL2){
int mi = id[tb[v]] / 24, si = 2 * (id[tb[v]] % 24);
if(seg3[mi][i] >> si & 1) seg3[mi][i] |= 1ll << (si + 1);
else seg3[mi][i] |= 1ll << si;
}
else a[i] = tb[v];
v /= tb[v];
}
if(a[i] != 1){
if(++cnt[a[i]] >= 2){
if(cnt[a[i]] == 2){
seg.insert(pre[a[i]], pre[a[i]]);
}
seg.insert(pre[a[i]], i);
seg.insert(i, i);
}
pre[a[i]] = i;
}
}
fill(pre.begin(), pre.end(), -1);
seg.build();
vector<mint> tmp(n, mint::raw(1));
for(int i = 0; i < n; i++){
if(a[i] != 1){
if(cnt[a[i]] >= 2){
seg.set(i, i, a[i]);
if(pre[a[i]] != -1){
seg.set(pre[a[i]], i, mint::raw(a[i]).inv());
}
pre[a[i]] = i;
}else{
tmp[i] = mint::raw(a[i]);
}
}
}
vector<segtree<int, op2, e2>> seg4(m);
vector<segtree<ll, op3, e3>> seg5(3);
segtree<mint, op, e> seg6(tmp);
for(int i = 0; i < m; i++) seg4[i] = segtree<int, op2, e2>(seg2[i]);
for(int i = 0; i < 3; i++) seg5[i] = segtree<ll, op3, e3>(seg3[i]);
int Q;
cin >> Q;
mint ans = 1;
while(Q--){
int a, b;
cin >> a >> b;
int l = (a * ans).val() % n, r = (b * ans).val() % n;
if(l > r) swap(l, r);
r++;
ans = seg.prod(l, l, r, r) * seg6.prod(l, r);
for(int i = 0; i < m; i++) ans *= seg4[i].prod(l, r);
for(int i = 0; i < 3; i++){
ll S = seg5[i].prod(l, r);
for(int j = 0; j < 24; j++){
if(S >> (2 * j) & 1) ans *= p2[j + i * 24];
if(S >> (2 * j + 1) & 1) ans *= p2[j + i * 24];
}
}
cout << ans.val() << '\n';
}
}