CF1422F Boring Queries

給定一個長度為$n$的數組$a,(1\le a_i\le 2\times 10^5)$，有$m$次詢問，每次詢問給定$l,r$，要我們求區間$[l,r]$，$a_i$的$lcm$，強制在線。

對于質因子$p$，如果$p^2>2\times 10^5$，那么它在每個數中出現的次數只有兩種可能$0/1$，可以如HH的項鏈的那題，一樣對每個因子維護一個最后出現的乘積。

如果$p^2\le 2\times 10^5$，我們可以考慮用$RMQ$表來維護區間最大值，容易知道最多只要維護$86$個$RMQ$表，所以整體復雜度$O(86\times n\log n)$。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7;int root[N], ls[N * 40], rs[N * 40], sum[N * 40], num;int prime[N], Log[N], inv[M], pre[M], fac[M], a[N], cnt, n, m;vector<int> p[87];bool st[M];struct RMQ {char f[N][18];void init() {for (int j = 1; j < 18; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}}int query(int l, int r) {int s = Log[r - l + 1];return max(f[l][s], f[r - (1 << s) + 1][s]);} }rmq[87];void init() {inv[1] = 1;for (int i = 2; i < M; i++) {inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;if (!st[i]) {prime[++cnt] = i;}for (int j = 1; j <= cnt && 1ll * i * prime[j] < M; j++) {st[i * prime[j]] = 1;if (i % prime[j] == 0) {break;}}}for (int i = 2; i < N; i++) {Log[i] = Log[i / 2] + 1;}for (int j = 1; prime[j] * prime[j] < M; j++) {for (int i = 1; i <= n; i++) {while (a[i] % prime[j] == 0) {a[i] /= prime[j];rmq[j].f[i][0]++;}}rmq[j].init();for (int cur = 1; cur < M; cur *= prime[j]) {p[j].push_back(cur);}}for (int i = 87; i <= cnt; i++) {for (int j = prime[i]; j < M; j += prime[i]) {fac[j] = prime[i];}} }void build(int &rt, int l, int r) {rt = ++num;if (l == r) {sum[rt] = 1;return ;}int mid = l + r >> 1;build(ls[rt], l, mid);build(rs[rt], mid + 1, r);sum[rt] = sum[ls[rt]] * sum[rs[rt]]; }void update(int &rt, int pre, int l, int r, int x, int v) {rt = ++num, ls[rt] = ls[pre], rs[rt] = rs[pre], sum[rt] = 1ll * sum[pre] * v % mod;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid + 1, r, x, v);} }int query(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return sum[rt];}int ans = 1, mid = l + r >> 1;if (L <= mid) {ans = 1ll * ans * query(ls[rt], l, mid, L, R) % mod;}if (R > mid) {ans = 1ll * ans * query(rs[rt], mid + 1, r, L, R) % mod;}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}init();build(root[0], 1, n);for (int i = 1; i <= n; i++) {root[i] = root[i - 1];if (!fac[a[i]]) {continue;}update(root[i], root[i], 1, n, i, fac[a[i]]);if (pre[fac[a[i]]]) {update(root[i], root[i], 1, n, pre[fac[a[i]]], inv[fac[a[i]]]);}pre[fac[a[i]]] = i;}scanf("%d", &m);int ans = 0;for (int i = 1, l, r; i <= m; i++) {scanf("%d %d", &l, &r);l = (ans + l) % n + 1, r = (ans + r) % n + 1;if (l > r) {swap(l, r);}ans = 1;for (int j = 1; j <= 86; j++) {ans = 1ll * ans * p[j][rmq[j].query(l, r)] % mod;}ans = 1ll * ans * query(root[r], 1, n, l, r) % mod;printf("%d\n", ans);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF1422F Boring Queries（ST表 + 主席树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。