結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
👑 ![]() |
提出日時 | 2023-07-28 21:47:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 344 ms / 2,000 ms |
コード長 | 3,080 bytes |
コンパイル時間 | 708 ms |
コンパイル使用メモリ | 81,436 KB |
最終ジャッジ日時 | 2025-02-15 20:13:59 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#line 1 "..\\Main.cpp"#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>#line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\dual-segment-tree.hpp"#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\dual-segment-tree.hpp"namespace nachia{template<class F,F composition(F f, F x)>struct DualSegtree {struct Node { F f; bool propagated; };int N;int logN;std::vector<Node> A;void mapf(Node& a, F f) {a.propagated = false;a.f = composition(f, a.f);}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] = A[0];}DualSegtree(int n, F id) {N=1; logN=0;while(N<n){ N *= 2; logN++; }A.assign(N*2, { id, true });}DualSegtree(const std::vector<F>& a) : DualSegtree(a.size()) {for(int i=0; i<a.size(); i++){ A[i+N].f = a[i]; A[i+N].propagated = false; }}void clear(int p) {p += N;for(int d=logN; d; d--) spread(p >> d);A[p] = A[0];}F get(int p){p += N;for(int d=logN; d; d--) spread(p >> d);return A[p].f;}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);}while(l < r){if(l&1){ mapf(A[l++], f); } l /= 2;if(r&1){ mapf(A[--r], f); } r /= 2;}}void apply(int p, F f){p += N;for(int d=logN; d; d--) spread(p >> d);mapf(A[p], f);}};} // namespace nachia;#line 8 "..\\Main.cpp"using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;//using Modint = atcoder::static_modint<998244353>;using Modint = atcoder::modint;struct F{Modint YY=1, XY=0, ZY=0, XX=1, ZX=0, ZZ=1, Xadd=0;};F composition(F f, F x){return {x.YY*f.YY,x.XX*f.XY + x.XY*f.YY,x.ZZ*f.ZY + x.ZX*f.XY + x.ZY*f.YY,x.XX*f.XX,x.ZZ*f.ZX + x.ZX*f.XX,x.ZZ*f.ZZ,f.Xadd + x.Xadd};}int main(){int N; cin >> N;int B; cin >> B;Modint::set_mod(B);int Q; cin >> Q;auto rq = nachia::DualSegtree<F, composition>(N, F());rep(q,Q){int l,m,r; cin >> l >> m >> r; l--; m--;rq.apply(l, r, {3,2,2,3,3,3,1});auto g = rq.get(m);auto x = g.Xadd + 1;auto y = g.XY + g.YY + g.ZY;auto z = g.ZZ;cout << x.val() << ' ' << y.val() << ' ' << z.val() << '\n';}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;