// Design Excel Sum Formula #define FOR(i, a, b) for (remove_cv::type>::type i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) class Excel { vector> a, c, d; vector>>> b; long tick = 0; pair f(string x) { return {atoi(x.c_str()+1)-1, x[0]-'A'}; } long get_sum(const vector>& xs, bool t = true) { long sum = 0; t && tick++; for (auto& r: xs) FOR(i, std::get<0>(r), std::get<2>(r)) FOR(j, std::get<1>(r), std::get<3>(r)) sum += get_cell(i, j); return sum; } long get_cell(int x, int y) { if (a[x][y] != LONG_MAX) return a[x][y]; if (d[x][y] == tick) return c[x][y]; d[x][y] = tick; return c[x][y] = get_sum(b[x][y], false); } public: Excel(int H, char W) { a = vector>(H, vector(W-'A'+1)); b.resize(H); REP(i, H) b[i].resize(W); c = vector>(H, vector(W-'A'+1)); d = vector>(H, vector(W-'A'+1)); } void set(int r, char c, int v) { a[r-1][c-'A'] = v; } int get(int r, char c) { tick++; return get_cell(r-1, c-'A'); } int sum(int r, char c, vector strs) { r--; c -= 'A'; a[r][c] = LONG_MAX; b[r][c].clear(); for (auto& s: strs) { string::size_type g; int x0, y0, x1, y1; if ((g = s.find(':')) != string::npos) { tie(x0, y0) = f(s.substr(0, g)); tie(x1, y1) = f(s.substr(g+1)); } else tie(x0, y0) = tie(x1, y1) = f(s); b[r][c].emplace_back(x0, y0, x1+1, y1+1); } return get_sum(b[r][c]); } };