#include<bits/stdc++.h>
#include "game.h"
using namespace std;
template<class B, class T>
struct persistent_dynamic_segment_tree_2d{
B n, m; // exclusive upper bound of coordinate
vector<int> xleft, xright, yleft, yright;
vector<T> data;
function<T(T, T)> TT; // monoid operation (always adjacent)
T T_id; // monoid identity
function<T(B, B, B, B)> T_init; // monoid default element for the interval [xl, xr) x [yl, yr)
persistent_dynamic_segment_tree_2d(){ }
persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id): persistent_dynamic_segment_tree_2d(n, m, TT, T_id, [&](auto, auto, auto, auto){ return 0LL; }){ }
persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id, function<T(B, B, B, B)> T_init): n(n), m(m), TT(TT), T_id(T_id), T_init(T_init){
new_state(-1, -1, -1, -1, T_init(0, n, 0, m));
}
int last_state(){
return (int)data.size() - 1;
}
int new_state(int xv, int xw, int yv, int yw, T x){
xleft.push_back(xv), xright.push_back(xw), yleft.push_back(yv), yright.push_back(yw), data.push_back(x);
return last_state();
}
void xextend(int u, B xl, B xr){
if(!~xleft[u]){
B xm = xl + (xr - xl >> 1);
xleft[u] = new_state(-1, -1, -1, -1, T_init(xl, xm, 0, m)); // Separate this on C++14 or below to avoid UB
xright[u] = new_state(-1, -1, -1, -1, T_init(xm, xr, 0, m)); // Separate this on C++14 or below to avoid UB
}
}
void yextend(int u, B xl, B xr, B yl, B yr){
if(!~yleft[u]){
B ym = yl + (yr - yl >> 1);
yleft[u] = new_state(-1, -1, -1, -1, T_init(xl, xr, yl, ym)); // Separate this on C++14 or below to avoid UB
yright[u] = new_state(-1, -1, -1, -1, T_init(xl, xr, ym, yr)); // Separate this on C++14 or below to avoid UB
}
}
int set(int u, B p, B q, T x){ // set a[p][q] = x at state u, O(log n)
function<int(int, B, B)> xrecurse = [&](int u, B xl, B xr){
function<int(int, B, B)> yrecurse = [&](int u, B yl, B yr){
if(yr - yl == 1) return new_state(-1, -1, -1, -1, x);
yextend(u, xl, xr, yl, yr);
B ym = yl + (yr - yl >> 1);
int v = yleft[u], w = yright[u];
if(q < ym) v = yrecurse(v, yl, ym);
else w = yrecurse(w, ym, yr);
return new_state(xleft[u], xright[u], v, w, TT(data[v], data[w]));
};
if(xr - xl == 1) return yrecurse(u, 0, m);
xextend(u, xl, xr);
B xm = xl + (xr - xl >> 1);
int v = xleft[u], w = xright[u];
if(p < xm) v = xrecurse(v, xl, xm);
else w = xrecurse(w, xm, xr);
return yrecurse(new_state(v, w, yleft[u], yright[u], data[u]), 0, m);
};
return xrecurse(u, 0, n);
}
T query(int u, B xql, B xqr, B yql, B yqr){ // find sum{ql<=i<qr}(v[i]) at state u, O(log n)
function<T(int, B, B)> xrecurse = [&](int u, B xl, B xr){
if(xqr <= xl || xr <= xql) return T_id;
function<T(int, B, B)> yrecurse = [&](int u, B yl, B yr){
if(yqr <= yl || yr <= yql) return T_id;
if(yql <= yl && yr <= yqr) return data[u];
yextend(u, xl, xr, yl, yr);
B ym = yl + (yr - yl >> 1);
return TT(yrecurse(yleft[u], yl, ym), yrecurse(yright[u], ym, yr));
};
if(xql <= xl && xr <= xqr) return yrecurse(u, 0, m);
xextend(u, xl, xr);
B xm = xl + (xr - xl >> 1);
return TT(xrecurse(xleft[u], xl, xm), xrecurse(xright[u], xm, xr));
};
return xrecurse(u, 0, n);
}
};
long long gcd2(long long X, long long Y) {
assert(0 <= X && 0 <= Y);
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
persistent_dynamic_segment_tree_2d<int, long long> ds;
int state;
void init(int R, int C){
ds = {R, C, [&](auto x, auto y){ return gcd2(x, y); }, 0};
state = ds.last_state();
}
void update(int P, int Q, long long K){
state = ds.set(state, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return ds.query(state, P, U + 1, Q, V + 1);
}
Compilation message
game.cpp: In instantiation of 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]':
game.cpp:98:31: required from here
game.cpp:44:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
44 | B ym = yl + (yr - yl >> 1);
| ~~~^~~~
game.cpp:52:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
52 | B xm = xl + (xr - xl >> 1);
| ~~~^~~~
game.cpp: In instantiation of 'T persistent_dynamic_segment_tree_2d<B, T>::query(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:102:43: required from here
game.cpp:67:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
67 | B ym = yl + (yr - yl >> 1);
| ~~~^~~~
game.cpp:72:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
72 | B xm = xl + (xr - xl >> 1);
| ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::yextend(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:43:5: required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:98:31: required from here
game.cpp:34:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
34 | B ym = yl + (yr - yl >> 1);
| ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::xextend(int, B, B) [with B = int; T = long long int]':
game.cpp:51:4: required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:98:31: required from here
game.cpp:27:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
27 | B xm = xl + (xr - xl >> 1);
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
