### chokudai's blog

By chokudai, history, 5 weeks ago,

We will hold NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

• +47

 » 5 weeks ago, # |   +31 Great round. Interesting problem F. Also, D and E might be educational for someone.
•  » » 5 weeks ago, # ^ |   +5 As someone who got WA on D and E, I can confirm.
•  » » 5 weeks ago, # ^ |   +17 logic for E was quite simple,tho i got two WA in it bcz i didnt consider case k=0. Can u plz explain F and intuition behind , i was not able to think much in that :( overall awesome contest :)
•  » » 5 weeks ago, # ^ |   +9 The corner case K=0 took me eight times of submissions to find:(
•  » » 5 weeks ago, # ^ |   0 I was able to solve E but I just guessed the corner case for K = 0. Can you tell me why that happens?
 » 5 weeks ago, # | ← Rev. 2 →   +3 I find it hard to not get lost in details while implementing F.Edit: Here is some (notworking) code to illustrate the problem: Codeusing stree=lazy_segtree; /** * Let t1=index of query when row i was last set before query qidx. * Let x be the value that row was set to. * Let sum1=sum of add operations on col j at time t1. * Let sum2=sum of add operations on col j at time qidx. * So, ans for cell i,j in query qidx is * ans=sum2-sum1+x */ void solve() { cini(n); cini(m); cini(q); vvi Q; vector row(n); /* qidx,val of last set-operation in that row */ stree seg(m); /* seg.get(i)=sum of updates in col i */ vector> qq; /* sum1x; /* ,x-sum1 */ int ii=0; for(int qidx=0; qidx(qq[ii])==qidx) { auto [qqidx,x,col]=qq[ii]; ii++; sum1x[{col,qqidx}]=x-seg.get(col); } } } signed main() { solve(); } 
•  » » 5 weeks ago, # ^ |   +3 I used a persistent segment tree (range update, point query) which helped me avoid a lot of implementation. I did however take a while to understand how to use the persistent segment tree template I found :P Code#include using namespace std; void dbg_out() { cerr << endl; } template void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) using ll = long long; template void smax(S &a, const T &b) { if (a < b) a = b; } template void smin(S &a, const T &b) { if (a > b) a = b; } #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long const int MXN = 2e5 + 5, INF = 1e9 + 5, MXK = 20; // https://github.com/saketh-are/algo-lib/blob/master/data_structures/segment_tree_persistent.cpp template struct segment_tree_persistent { struct node { T v; int left, right; }; struct snapshot { Timestamp t; int root; int data_size; bool operator < (const snapshot &o) const { return t < o.t; } }; int SZ; T identity; AssociativeOperation TT; std::vector data; std::vector history; segment_tree_persistent() {} segment_tree_persistent(int _SZ, T _identity, AssociativeOperation _TT) : identity(_identity), TT(_TT) { SZ = 1 << (32 - __builtin_clz(_SZ - 1)); assert(SZ >= _SZ && __builtin_popcount(SZ) == 1); data.push_back({ identity, -1, -1 }); for (int loc = 1; loc <= __builtin_ctz(SZ); loc++) data.push_back({ TT(data[loc - 1].v, data[loc - 1].v), loc - 1, loc - 1 }); history.push_back({ std::numeric_limits::min(), int(data.size()) - 1, int(data.size()) }); } private: int modify_leaf(int i, T v, int loc, int L, int R, int immutable, bool overwrite) { node updated; if (R - L == 1) { updated = { overwrite ? v : TT(data[loc].v, v), -1, -1 }; } else { int M = L + (R - L) / 2; int left = i < M ? modify_leaf(i, v, data[loc].left, L, M, immutable, overwrite) : data[loc].left; int right = M <= i ? modify_leaf(i, v, data[loc].right, M, R, immutable, overwrite) : data[loc].right; updated = { TT(data[left].v, data[right].v), left, right }; } if (loc < immutable) { loc = int(data.size()); data.push_back(updated); } else { data[loc] = updated; } return loc; } void modify_leaf(int i, T v, Timestamp t, bool overwrite) { int current_root = history.back().root; if (history.back().t == t) history.pop_back(); int immutable = history.back().data_size; int updated_root = modify_leaf(i, v, current_root, 0, SZ, immutable, overwrite); history.push_back({ t, updated_root, int(data.size()) }); } T accumulate(int i, int j, T init, int loc, int L, int R) const { if (L == i && j == R) { init = TT(init, data[loc].v); } else { int M = L + (R - L) / 2; if (i < M) init = accumulate(i, std::min(j, M), init, data[loc].left, L, M); if (M < j) init = accumulate(std::max(i, M), j, init, data[loc].right, M, R); } return init; } public: // Assigns v at index i during moment t void assign(int i, T v, Timestamp t) { assert(0 <= i && i < SZ && history.back().t <= t); modify_leaf(i, v, t, true); } // Replaces the current value at index i with TT(current value, v) during moment t void combine_and_assign(int i, T v, Timestamp t) { assert(0 <= i && i < SZ && history.back().t <= t); modify_leaf(i, v, t, false); } // Accumulates the elements at indices in [first, last) as they were before t (after all assignments with t' < t) T accumulate(int first, int last, Timestamp t) const { if (first >= last) return identity; assert(0 <= first && last <= SZ); int root_before_t = std::prev(std::lower_bound(history.begin(), history.end(), snapshot{ t, -1, -1 }))->root; return accumulate(first, last, identity, root_before_t, 0, SZ); } }; using ll = long long; void solve() { int N, M, Q; cin >> N >> M >> Q; segment_tree_persistent> st(max(N, M) + 5, 0, plus()); vector> row(max(N, M) + 5, make_pair(1, 0)); // {time, new element} for (int iter = 1; iter <= Q; iter++) { ll type; cin >> type; if (type == 1) { ll l, r, x; cin >> l >> r >> x; l--, r--; st.combine_and_assign(l, x, iter); st.combine_and_assign(r + 1, -x, iter); // dbg(st.accumulate(0, 1, Q + 1)); } else if (type == 2) { ll i, x; cin >> i >> x; i--; row[i] = make_pair(iter, x); } else if (type == 3) { ll i, j; cin >> i >> j; i--, j--; auto [time, x] = row[i]; cout << x + st.accumulate(0, j + 1, iter) - st.accumulate(0, j + 1, time) << "\n"; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); } 
•  » » » 5 weeks ago, # ^ |   0 Persistent segment tree! Wonderful idea! In fact I have also considered it during contest but finally give up this idea for two reasons. Reason 1, I remember that persistent segment tree can not deal with interval updating (now I understand that we could use single-element updating instead, and thus this will not be a problem). Reason 2, I can't write it fast and correctly (I only wrote it once when I was trying this problem https://codeforces.com/contest/484/problem/E)Thank you for sharing your idea!
•  » » » » 5 weeks ago, # ^ |   +8 I believe that persistent segment tree CAN deal with interval updates.
•  » » » » » 5 weeks ago, # ^ |   0 I used the primer tree to solve Fsubmission
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thank you for pointing out my mistake. I think I really don't fully understand this technique. I just learned it from this problem https://codeforces.com/contest/484/problem/E, where only single-element updating is involved. Would you like to recommend any good tutorials about this :DUPD: I mean, how to implement interval updating in persistent segment tree :)
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 6 →   0 If you're asking about how to perform range updates and point queries (as opposed to the usual point update, range query) without the use of lazy propagation, here's how to do it:Let's say you want to increment the interval $[L, R]$ by some amount $x$. Let's increment the value at index $L$ by $x$ and increment the value at index $R + 1$ by $-x$. Now, if at any time you want to query the value at index $i$, the answer is the sum of the interval $[0, i]$ (assuming you index from $0$). Essentially, if $L \le i \le R$, then the update at $L$ also adds to $i$'s value. If $R < i$, then both $x$ and $-x$ get added to the effective value at $i$, resulting in a change of $0$. If $i < L$, the update on the interval $[L, R]$ doesn't affect $i$.You can also use this idea to perform range updates and point queries with a Fenwick Tree.
•  » » » » » » » 5 weeks ago, # ^ |   0 Thank you for your detailed and clear explanation! This is such a nice trick to transform between single-element and interval updating.Although my question is in fact to ask how to implement interval updating in persistent segment tree, still thanks a lot!
 » 5 weeks ago, # |   0 Any hints for F ? I am clueless.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Foreach query of type 3 we can more or less simply find the time when the row was last set to X. If we know the sum of col-updates at that point of time, we can calculate ans=sum2-sum1+xWhere sum2 is sum of col updates at time query type 3, sum1 is sum of col updates at last update of row, and x the value that row was set to.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 I did it in offline mode.Firstly stored all queries in one vector For each query of type 3 find index j such that this will follow the conditions : (i) j < i (ii) query type of j is 2 ( row update query ) (iii) Row value for both queries are sameand store the index i to one vector (lets say previous_needed) so previous_needed[j].push_back(i)basically value at point (i,j) depends on the the following values :(i) last row update with row number i (ii) value added to column j before last row updation (iii) value added to column j from startinganswer = (i) + (iii) — (ii)we can find the value of any column at any moment by using segment tree in O(logN)for each type of query 2 at index i: we store the value for all query of type 3 depend on i th query ( basically i th query is the last row updation for such queries ) into map of pair -> intfor each col in previous_needed[query[i].row] store {query[i].row , col} = column value for col (using seg tree) to prev_valuethen for each query of type 3 : answer = last_updation_on_row[query.row] + total_added_value_in_column[query.col] — prev_value[{query.row , query.col}] My Code#include using namespace std; #define ll long long int #define pb push_back #define mod 1000000007 #define bg begin() #define rbg rbegin() #define ed end() #define sz size() #define ff first #define ss second #define fon for(i=0;i void ppp(pair p) {cerr<<"{"; ppp(p.ff); cerr<<','; ppp(p.ss); cerr<<"}";} template void ppp(vector v) {cerr<<"[ ";for(T x:v) ppp(x), cerr<<" ";cerr<<']';} template void ppp(set v){cerr<<"[ ";for(T x:v) ppp(x) , cerr<<" ";cerr<<']';} template void ppp(map m){cerr< ";ppp(x.ss);cerr< void ppp(deque v) {cerr<<"[ ";for(T x:v) ppp(x), cerr<<" ";cerr<<']';} template void ppp(T t, V... v){ppp(t); if (sizeof...(v)) cerr << ", "; ppp(v...);} #ifndef ONLINE_JUDGE #define dbg(x...) cerr << #x << " -> "; ppp(x); cerr< t; ll n; void modify(ll p, ll value) { for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1]; } ll query(ll l, ll r) { dbg(l,r); ll res = 0; r++; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) res = res + t[l++]; if (r&1) res = res + t[--r]; } dbg(res); return res; } int main() { JSM ll m,x,y,p,q,i,j,k,answer=0; cin>>m>>n>>q; t = vector (2*n , 0); vector a(n , 0); vector row_val(m , 0); vector> queries; while(q--){ ll tp; cin>>tp; cin>>x>>y; if(tp == 1){ cin>>p; queries.pb({tp , x , y , p}); } else queries.pb({tp , x , y}); } vector> ref(m + 1); vector> prev_need(queries.sz); q = queries.sz; for(i=q-1;i>=0;i--){ if(queries[i][0] == 2){ for(auto x: ref[queries[i][1]]) prev_need[i].pb(x); ref[queries[i][1]].clear(); } else if(queries[i][0] == 3){ ref[queries[i][1]].pb(queries[i][2]); } } map , ll> prev; for(i=0;i
•  » » 5 weeks ago, # ^ |   +3 You can use sqrt decomposition to solve this problem. Naive approach is to maintain $prefix$_$sum$, where $prefix$_$sum[i][j]$ gives sum of $x$ added to column $j$ after first $i$ queries. Suppose in $i_{th}$ query, you want answer for cell $(l,r)$ from , answer is $prefix$_$sum[i][r]-prefix$_$sum[j-1][r]+x[j]$, where row $l$ was last updated in $j_{th}$ query. Note that this solves our problem, but we can't store $prefix$_$sum$ after all queries. So, if you store the $prefix$_$sum$ after $i_{th}$ query iif $i$ is a multiple of $1000$, you end up storing sum for atmost $200$ queries.So time complexity is $O(\frac{m^2}{b} + q \cdot (\frac{m}{b}+ b))$, where $b=1000$.My submission
 » 5 weeks ago, # |   +9 Nice problems and thanks to writers and testers :)Problem D is about application of inclusion-exclusion principle, and maybe good practice for learning how to compute gcd and lcm as well.E is a classic dp problem, which also includes a classic optimization in order to reduce the complexity, and it costs me 2 WAs before I realized the tricky case k=0. Nice trap!For F, I couldn't believe that I got AC before the contest ends, what a miracle! My idea is similar to the editorial, but I think the calculation of S(k,j) is not an easy task. Except for the segment tree part, one should also be very careful of, when and how, to compute S(q,j) and S(q',j). At least, I think my implementation is somehow a little complicated.I read problem G during the last 10 minutes. I think I have got close to the idea mentioned in the editorial, although some part is not correct. Hope that someday, I could solve G and have time to read problem Ex (Yeah, I have never got a chance to read Ex before contest ends :D)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 You can simply use Fenwick Tree instead of segment tree in Problem F. That will be a lot easier.ABC253G is the easiest problem to get the correct idea of all Problem G-s I have ever solved in ABC. But it took me 30mins and a wrong answer attempt to get accepted. I missed many implementation details and took a long time debugging my code. Hope that someday we could solve A-F within 20 minutes as well :) Almost 50 minutes this time. I'll try to be better next time.
•  » » » 5 weeks ago, # ^ |   0 Wow, 50 minutes for A-F, amazing! I finished F after about 90 minutes. There is still a long way for me.
 » 5 weeks ago, # |   0 Am I the only person who thinks that have seen problem F before on codeforces or somewhere? If anyone know the source of the problem please put the link here thanks in advance.
•  » » 5 weeks ago, # ^ |   +3 It is not same but similar. Maybe you remember this.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I found F very similar to this problem
•  » » » 5 weeks ago, # ^ |   0 but F is 2D
 » 5 weeks ago, # |   0 Can someone optimize this code for problem E? submisssion