結果
問題 |
No.3239 Omnibus
|
ユーザー |
|
提出日時 | 2025-08-15 22:43:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,536 ms / 10,000 ms |
コード長 | 17,054 bytes |
コンパイル時間 | 4,670 ms |
コンパイル使用メモリ | 330,512 KB |
実行使用メモリ | 184,852 KB |
最終ジャッジ日時 | 2025-08-15 22:45:59 |
合計ジャッジ時間 | 96,526 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__) #define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__) #define OVERLOAD_REP(_1, _2, _3, _4, name, ...) name #define REP1(n) for(ll i=0;i<(n);i++) #define REP2(i, n) for (ll i=0;i<(n);i++) #define REP3(i, a, n) for (ll i=a;i<(n);i++) #define REP4(i, a, b, n) for(ll i=a;i<(n);i+=b) #define rep(...) OVERLOAD_REP(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define OVERLOAD_RREP(_1, _2, _3, _4, name, ...) name #define RREP1(n) for(ll i=(n)-1;i>=0;i--) #define RREP2(i, n) for(ll i=(n)-1;i>=0;i--) #define RREP3(i, a, n) for(ll i=(n)-1;i>=(a);i--) #define RREP4(i, a, b, n) for(ll i=(n)-1;i>=(a);i-=(b)) #define rrep(...) OVERLOAD_RREP(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) #define uniq(a) sort(all(a));a.erase(unique(all(a)),end(a)) #define len(n) (long long)(n).size() using ll = long long; using ld = long double; using ull = unsigned long long; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vs = vector<string>; using vvs = vector<vs>; using vvvs = vector<vvs>; using vld = vector<ld>; using vvld = vector<vld>; using vvvld = vector<vvld>; using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>; using pll = pair<ll,ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; ll intpow(ll a,ll b){ ll ans = 1; while (b){ if (b & 1){ ans *= a; } a *= a; b /= 2; } return ans; } ll modpow(ll a,ll b,ll c){ ll ans = 1; while (b){ if (b & 1){ ans *= a; ans %= c; } a *= a; a %= c; b /= 2; } return ans; } template<class... T> void input(T&... a){ (cin >> ... >> a); } #define INT(...) int __VA_ARGS__; input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; input(__VA_ARGS__) #define STR(...) string __VA_ARGS__; input(__VA_ARGS__) #define CHA(...) char __VA_ARGS__; input(__VA_ARGS__) #define VLL(name,length) vll name(length);rep(i,length){cin >> name[i];} #define VVLL(name,h,w) vvll name(h,vll(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLL(name,a,b,c) vvvll name(a,vvll(b,vll(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VI(name,length) vi name(length);rep(i,length){cin >> name[i];} #define VVI(name,h,w) vvi name(h,vi(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVI(name,a,b,c) vvvi name(a,vvll(b,vi(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VLD(name,length) vld name(length);rep(i,length){cin >> name[i];} #define VVLD(name,h,w) vvld name(h,vld(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVLD(name,a,b,c) vvvld name(a,vvld(b,vld(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VC(name,length) vc name(length);rep(i,length){cin >> name[i];} #define VVC(name,h,w) vvc name(h,vc(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVC(name,a,b,c) vvvc name(a,vvc(b,vc(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define VS(name,length) vs name(length);rep(i,length){cin >> name[i];} #define VVS(name,h,w) vvs name(h,vs(w));rep(i,h)rep(j,w){cin >> name[i][j];} #define VVVS(name,a,b,c) vvvs name(a,vvs(b,vs(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];} #define PLL(name) pll name;cin>>name.first>>name.second; #define VPLL(name,length) vpll name(length);rep(i,length){cin>>name[i].first>>name[i].second;} void print(){cout << "\n";} template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } template <typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << "["; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i + 1 < vec.size()) os << ", "; } os << "]"; return os; } template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::vector<std::pair<T1, T2>>& a) { os << "["; for (size_t j = 0; j < a.size(); ++j) { os << "(" << a[j].first << ", " << a[j].second << ")"; if (j + 1 < a.size()) os << ", "; } os << "]"; return os; } template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<std::pair<T1, T2>>>& mat) { os << "["; for (size_t i = 0; i < mat.size(); ++i) { os << "["; for (size_t j = 0; j < mat[i].size(); ++j) { os << "(" << mat[i][j].first << ", " << mat[i][j].second << ")"; if (j + 1 < mat[i].size()) os << ", "; } os << "]"; if (i + 1 < mat.size()) os << ", "; } os << "]"; return os; } template <typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s) { os << "{"; bool first = true; for (const auto& x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template <typename K, typename V> std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) { os << "{"; bool first = true; for (const auto& [key, val] : m) { if (!first) os << ", "; os << key << ": " << val; first = false; } os << "}"; return os; } template<class T, class... Ts> void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} #ifdef LOCAL void debug() { std::cerr << "\n"; } template<class T, class... Ts> void debug(const T& a, const Ts&... b) { std::cerr << a; (std::cerr << ... << (std::cerr << ' ', b)); std::cerr << '\n'; } #else #define debug(...) (void)0 #endif void write(){cout << "\n";} template<class T, class... Ts> void write(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';} void write(vll x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vi x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvi x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvi x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vld x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvld x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvld x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vc x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvc x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvc x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(vs x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}} void write(vvs x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} void write(vvvs x){rep(i,len(x))rep(j,len(x[i]))rep(k,len(x[i][j])){cout << x[i][j][k];if(k!=len(x[i][j])-1){cout << " ";}else if(j!=len(x[i])-1){cout << " | ";}else{cout << '\n';}}} void write(pll x){cout << x.first << ' ' << x.second << '\n';} void write(vpll x){rep(i,len(x)){cout << x[i].first << ' ' << x[i].second << '\n';}} void write(vvpll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j].first << ' ' << x[i][j].second;if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}} template <typename T> T sum(const std::vector<T>& v) { return std::accumulate(v.begin(), v.end(), T(0)); } template<class Set> auto le(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.upper_bound(x); if (it == s.begin()) return ngval; return *prev(it); } template<class Set> auto lt(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.lower_bound(x); if (it == s.begin()) return ngval; return *prev(it); } template<class Set> auto ge(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.lower_bound(x); if (it == s.end()) return ngval; return *it; } template<class Set> auto gt(const Set &s, const typename Set::value_type &x, const typename Set::value_type &ngval = typename Set::value_type(-1)) { auto it = s.upper_bound(x); if (it == s.end()) return ngval; return *it; } template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; } template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; } template<class T, class U> bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; } template<class T, class U> bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; } //https://yukicoder.me/submissions/1106016 //based on https://nyaannyaan.github.io/library/data-structure-2d/fenwick-tree-on-wavelet-matrix.hpp // 使い方: // 1. .add_point(x, y) で加算対象となる点をすべて登録する // 2. .build() を呼び出して構築する // 3. .add(x, y, w) で (x, y) に w を加算 // 4. .sum(l, d, r, u) で半開矩形 [l, r) × [d, u) に含まれる点の総和を取得 struct bit_vector { using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 w = 64; vector<u64> block; vector<u32> count; u32 n, zeros; inline u32 get(u32 i) const { return u32(block[i / w] >> (i % w)) & 1u; } inline void set(u32 i) { block[i / w] |= 1ULL << (i % w); } bit_vector() {} bit_vector(int _n) { init(_n); } void init(int _n) { n = zeros = _n; block.assign(n / w + 1, 0); count.assign(block.size(), 0); } void build() { for (u32 i = 1; i < block.size(); ++i) count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]); zeros = rank0(n); } inline u32 rank0(u32 i) const { return i - rank1(i); } inline u32 rank1(u32 i) const { u32 bidx = i / w; u32 offset = i % w; u64 masked = block[bidx] & ((1ULL << offset) - 1); return count[bidx] + __builtin_popcountll(masked); } }; template <typename S, typename T> struct Point_Add_Rectangle_Sum { using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; struct BIT { u32 N; vector<T> data; BIT() = default; BIT(int size) { init(size); } void init(int size) { N = size; data.assign(N + 1, 0); } void add(u32 k, T x) { for (++k; k <= N; k += k & (-k)) data[k] += x; } T sum(u32 k) const { T ret = T(); for (; k; k -= k & (-k)) ret += data[k]; return ret; } T sum(int l, int r) const { T ret = T(); while (l != r) { if (l < r) { ret += data[r]; r -= r & (-r); } else { ret -= data[l]; l -= l & (-l); } } return ret; } }; using P = pair<S, S>; int n, lg; vector<bit_vector> bv; vector<BIT> bit; vector<P> ps; vector<S> ys; Point_Add_Rectangle_Sum() {} void add_point(S x, S y) { ps.emplace_back(x, y); ys.emplace_back(y); } void build() { sort(ps.begin(), ps.end()); ps.erase(unique(ps.begin(), ps.end()), ps.end()); n = (int)ps.size(); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); vector<u32> cur(n), nxt(n); for (int i = 0; i < n; ++i) cur[i] = yid(ps[i].second); lg = max(1, 32 - __builtin_clz(n)); bv.assign(lg, bit_vector(n)); bit.assign(lg, BIT(n)); for (int h = lg - 1; h >= 0; --h) { for (int i = 0; i < n; ++i) { if ((cur[i] >> h) & 1) bv[h].set(i); } bv[h].build(); auto it = array<decltype(nxt.begin()), 2>{nxt.begin(), nxt.begin() + bv[h].zeros}; for (int i = 0; i < n; ++i) *it[bv[h].get(i)]++ = cur[i]; swap(cur, nxt); } } int xid(S x) const { return lower_bound(ps.begin(), ps.end(), P{x, S()}, [](const P& a, const P& b) { return a.first < b.first; }) - ps.begin(); } int yid(S y) const { return lower_bound(ys.begin(), ys.end(), y) - ys.begin(); } void add(S x, S y, T val) { int i = lower_bound(ps.begin(), ps.end(), P{x, y}) - ps.begin(); for (int h = lg - 1; h >= 0; --h) { int i0 = bv[h].rank0(i); if (bv[h].get(i)) i += bv[h].zeros - i0; else i = i0; bit[h].add(i, val); } } T sum(int l, int r, u32 upper) const { T res = 0; for (int h = lg; h--;) { int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r); if ((upper >> h) & 1) { res += bit[h].sum(l0, r0); l += bv[h].zeros - l0; r += bv[h].zeros - r0; } else { l = l0; r = r0; } } return res; } T sum(S L, S D, S R, S U) const { int l = xid(L), r = xid(R); return sum(l, r, yid(U)) - sum(l, r, yid(D)); } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); auto f = [&](string s){ return (s[0] - 'a') * 100000 + (s[1] - 'a') * 1000 + (s[2] - 'a') * 10; }; LL(n,q); vpll p; STR(s); rep(i,n-2){ string temp; temp += s[i]; temp += s[i+1]; temp += s[i+2]; ll x = f(temp); p.emplace_back(i,x); } string w = s; vll t(q),k(q),l(q),r(q); vc c(q); vs a(q); rep(i,q){ LL(t1); t[i] = t1; if(t1 == 1){ LL(k1); k1--; CHA(c1); k[i] = k1; c[i] = c1; w[k1] = c1; rep(j,k1-2,k1+1){ if(0 <= j && j+2 < n){ string temp; temp += w[j]; temp += w[j+1]; temp += w[j+2]; ll x = f(temp); p.emplace_back(j,x); } } } else{ LL(l1,r1); STR(a1); l[i] = l1-1; r[i] = r1-1; a[i] = a1; } } Point_Add_Rectangle_Sum<ll,ll> pars1,pars2; for(auto [x,y]:p){ pars1.add_point(x,y); pars2.add_point(x,y); } pars1.build(); pars2.build(); rep(i,n-2){ string temp; temp += s[i]; temp += s[i+1]; temp += s[i+2]; ll x = f(temp); //p.emplace_back(i,x); pars1.add(i,x,1); pars2.add(i,x,i+1); } rep(i,q){ ll t1 = t[i]; if(t1 == 1){ ll k1 = k[i]; char c1 = c[i]; rep(j,k1-2,k1+1){ if(0 <= j && j+2 < n){ string temp; temp += s[j]; temp += s[j+1]; temp += s[j+2]; ll x = f(temp); //p.emplace_back(j,x); pars1.add(j,x,-1); pars2.add(j,x,-(j+1)); } } s[k1] = c1; rep(j,k1-2,k1+1){ if(0 <= j && j+2 < n){ string temp; temp += s[j]; temp += s[j+1]; temp += s[j+2]; debug(temp,k1,j); ll x = f(temp); //p.emplace_back(j,x); pars1.add(j,x,1); pars2.add(j,x,j+1); } } } else{ ll l1 = l[i]; ll r1 = r[i]; string a1 = a[i]; ll b = f(a1); ll x = pars1.sum(l1,b,r1-1,b+1); ll y = pars2.sum(l1,b,r1-1,b+1); debug(x,y); print(y - x * l1); } } }