結果
| 問題 | No.8110 WIP Editorial |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2024-04-01 22:09:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,086 bytes |
| コンパイル時間 | 1,575 ms |
| コンパイル使用メモリ | 109,760 KB |
| 最終ジャッジ日時 | 2025-02-20 19:11:30 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 8 |
ソースコード
#ifdef NACHIA#define _GLIBCXX_DEBUG#else#define NDEBUG#endif#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <queue>#include <array>#include <cmath>#include <atcoder/modint>namespace nachia{template<class S,class F,S op(S l, S r),F composition(F f, F x),S mapping(F f, S x)>struct LazySegtree {private:struct Node { S s; F f; bool propagated; };int N;int logN;int xN;std::vector<Node> A;void mapf(Node& a, F f){a.propagated = false;a.f = composition(f, a.f);a.s = mapping(f, a.s);}void mergev(int i){if(i<N) A[i].s = op(A[i*2].s, A[i*2+1].s);}void spread(int i){if(A[i].propagated || !(i < N)) return;mapf(A[i*2], A[i].f);mapf(A[i*2+1], A[i].f);A[i].f = A[0].f;A[i].propagated = true;}// bool cmp(S)template<class E>int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1){static S x;if(i == -1){ a=0; b=N; i=1; x = A[0].s; }if(r <= a) return a;if(b <= r){S nx = op(A[i].s, x);if(cmp(nx)){ x = nx; return a; }}if(b-a == 1) return b;spread(i);int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);if(q > (a+b)/2) return q;return minLeft2(r, cmp, a, (a+b)/2, i*2);}// bool cmp(S)template<class E>int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1){static S x;if(i == -1){ a=0; b=N; i=1; x = A[0].s; }if(b <= l) return b;if(l <= a){S nx = op(x, A[i].s);if(cmp(nx)){ x = nx; return b; }}if(b - a == 1) return a;spread(i);int q = maxRight2(l, cmp, a, (a+b)/2, i*2);if(q < (a+b)/2) return q;return maxRight2(l, cmp, (a+b)/2, b, i*2+1);}public:LazySegtree() : N(0), logN(-1), xN(0){}LazySegtree(int n, S e, F id){N=1; logN=0; xN=n;while(N<n){ N *= 2; logN++; }A.assign(N*2, { e, id, true });}LazySegtree(const std::vector<S>& a, S e, F id): LazySegtree(a.size(), std::move(e), std::move(id)){for(std::size_t i=0; i<a.size(); i++) A[i+N].s = a[i];for(int i=N-1; i>=1; i--) mergev(i);}void set(int p, S x){p += N;for(int d=logN; d; d--) spread(p >> d);A[p].s = x;for(int d=1; d<=logN; d++) mergev(p >> d);}S get(int p){p += N;for(int d=logN; d; d--) spread(p >> d);return A[p].s;}void apply(int p, F f){ set(p, mapping(f, get(p))); }void apply(int l, int r, F f){if(!(l < r)) return;if(l == 0 && r == N){ mapf(A[1], f); return; }l += N; r += N;for(int d=logN; d; d--){if((l >> d) << d != l) spread(l >> d);if((r >> d) << d != r) spread(r >> d);}int lp = l, rp = r;while(l < r){if(l&1){ mapf(A[l++], f); } l /= 2;if(r&1){ mapf(A[--r], f); } r /= 2;}for(int d=1 ; d<=logN; d++){if((lp >> d) << d != lp) mergev(lp >> d);if((rp >> d) << d != rp) mergev(rp >> d);}}S prod(int l, int r){if(!(l < r)) return A[0].s;l += N; r += N;for(int d=logN; d; d--){if((l >> d) << d != l) spread(l >> d);if((r >> d) << d != r) spread(r >> d);}S q1 = A[0].s, q2 = A[0].s;while(l < r){if(l&1){ q1 = op(q1, A[l++].s); } l /= 2;if(r&1){ q2 = op(A[--r].s, q2); } r /= 2;}return op(q1, q2);}S allProd() const { return A[1].s; }// bool cmp(S)template<class E>int minLeft(int r, E cmp){return minLeft2(r, cmp);}// bool cmp(S)template<class E>int maxRight(int l, E cmp){int x = maxRight2(l, cmp);return x > xN ? xN : x;}};} // namespace nachia;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<int(n); i++)#define repr(i,n) for(int i=int(n)-1; i>=0; i--)using Modint = atcoder::static_modint<998244353>;using namespace std;struct Node { i64 x; i64 c; };Node op(Node l, Node r){ return Node{ l.x + r.x, l.c + r.c }; }Node mapping(Node f, Node x){ return Node{ f.x * x.x + f.c * x.c, x.c }; }Node composition(Node f, Node x){ return Node{ f.x * x.x, f.c + f.x * x.c }; }int main(){ios::sync_with_stdio(false); cin.tie(nullptr);i64 N; cin >> N;using Lst = nachia::LazySegtree<Node, Node, op, composition, mapping>;vector<i64> pf = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,57,59,61,67,71,73,79,83,89,97};auto factor = [&](i64 a) -> vector<i64> {vector<i64> res(pf.size());rep(d,pf.size()){i64 p = pf[d];i64 e = 0;while(a%p == 0){ a /= p; res[d]++; }}return res;};auto lst = vector<Lst>(pf.size()); {vector<vector<Node>> init(pf.size(), vector<Node>(N, {0,1}));rep(i,N){i64 a; cin >> a;auto f = factor(a);rep(d,f.size()) init[d][i].x = f[d];}rep(i,pf.size()) lst[i] = Lst(init[i], {0,0}, {1,0});}i64 Q; cin >> Q;rep(qi,Q){i64 t; cin >> t;if(t == 1){i64 l,r,a; cin >> l >> r >> a; l--;auto f = factor(a);rep(d,pf.size()) lst[d].apply(l,r,{0,f[d]});}else if(t == 2){i64 l,r,a; cin >> l >> r >> a; l--;auto f = factor(a);rep(d,pf.size()) lst[d].apply(l,r,{1,f[d]});}else if(t == 3){i64 l,r,a; cin >> l >> r >> a; l--;vector<i64> rq(pf.size());rep(d,pf.size()) if(pf[d] <= a) rq[d] = lst[d].prod(l,r).x;i64 ans = 1;for(auto d : rq) ans *= d+1;cout << ans << "\n";}}return 0;}