Click to show code.
using namespace std;
using ll = long long;
int main(void)
{
int n, ai;
ll s = 0, ans = 0;
map<ll, int> prefix_count;
cin >> n;
prefix_count[0] = 1;
for (int i = 0; i < n; ++i)
{
cin >> ai;
s = ((s + ai) % n + n) % n;
ans += prefix_count[s];
++prefix_count[s];
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
int main(void)
{
int n, x, ai;
ll s = 0, ans = 0;
map<ll, int> prefix_count;
cin >> n >> x;
prefix_count[0] = 1;
for (int i = 0; i < n; ++i)
{
cin >> ai;
s += ai;
ans += prefix_count[s - x];
++prefix_count[s];
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
int main(void)
{
int n, x, ai;
ll s = 0, ans = 0;
map<ll, int> prefix_count;
cin >> n >> x;
prefix_count[0] = 1;
for (int i = 0; i < n; ++i)
{
cin >> ai;
s += ai;
ans += prefix_count[s - x];
++prefix_count[s];
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
struct FenwickTree2D
{
vector<vector<int>> bit;
int n, m;
FenwickTree2D(vector<vector<int>> a)
{
n = (int)a.size(), m = (int)a.front().size();
bit.assign(n, vi(m, 0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
add(i, j, a[i][j]);
}
int sum(int x, int y)
{
int ret = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
ret += bit[i][j];
return ret;
}
void add(int x, int y, int delta)
{
for (int i = x; i < n; i = i | (i + 1))
for (int j = y; j < m; j = j | (j + 1))
bit[i][j] += delta;
}
int query(int y1, int x1, int y2, int x2)
{
auto ans = sum(x2, y2);
if (x1 > 0)
ans -= sum(x1 - 1, y2);
if (y1 > 0)
ans -= sum(x2, y1 - 1);
if (x1 > 0 and y1 > 0)
ans += sum(x1 - 1, y1 - 1);
return ans;
}
};
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<vi> a(n, vi(n));
for (int row = 0; row < n; ++row)
{
for (int col = 0; col < n; ++col)
{
char ch;
cin >> ch;
a[row][col] = ch == '*';
}
}
FenwickTree2D tree(a);
while (q--)
{
int y1, x1, y2, x2;
cin >> x1 >> y1 >> x2 >> y2;
y1--, x1--, y2--, x2--;
if (x1 > x2)
swap(x1, x2);
if (y1 > y2)
swap(y1, y2);
cout << tree.query(y1, x1, y2, x2) << endl;
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
struct segment_tree
{
int n;
vector<ll> t, lazy;
segment_tree(vi const &a)
{
n = (int)a.size();
t.resize(4 * n, 0);
lazy.resize(4 * n, 0);
build(a, 1, 0, n - 1);
}
void lazy_propagate(int v, int tl, int tr, ll val)
{
t[v] += (tr - tl + 1) * val;
if (tl != tr)
{
lazy[2 * v] += val;
lazy[2 * v + 1] += val;
}
lazy[v] = 0;
}
void build(vi const &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
void update(int v, int tl, int tr, int ql, int qr, int delta)
{
if (lazy[v] != 0)
lazy_propagate(v, tl, tr, lazy[v]);
if (ql > qr)
return;
if (tl == ql and tr == qr)
lazy_propagate(v, tl, tr, delta);
else
{
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, ql, min(tm, qr), delta);
update(v * 2 + 1, tm + 1, tr, max(tm + 1, ql), qr, delta);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
ll query(int v, int tl, int tr, int ql, int qr)
{
if (lazy[v] != 0)
lazy_propagate(v, tl, tr, lazy[v]);
if (ql > qr)
return 0;
if (tl == ql and tr == qr)
return t[v];
else
{
int tm = (tl + tr) / 2;
return query(2 * v, tl, tm, ql, min(tm, qr)) +
query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr);
}
}
};
int main(void)
{
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
segment_tree st(a);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int ql, qr, delta;
cin >> ql >> qr >> delta, ql--, qr--;
st.update(1, 0, n - 1, ql, qr, delta);
}
else
{
int ix;
cin >> ix, ix--;
cout << st.query(1, 0, n - 1, ix, ix) << endl;
}
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
struct segment_tree
{
int n;
vi t;
segment_tree(vi const &a)
{
n = (int)a.size();
t.resize(4 * (int)a.size());
build(a, 1, 0, n - 1);
}
int merge(int a, int b) { return a ^ b; }
void build(vi const &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
auto query(int v, int tl, int tr, int ql, int qr)
{
if (tl == ql and tr == qr)
return t[v];
else if (ql > qr)
return 0;
else
{
int tm = (tl + tr) / 2;
return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
}
}
};
int main(void)
{
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
segment_tree st(a);
while (q--)
{
int ql, qr;
cin >> ql >> qr, ql--, qr--;
cout << st.query(1, 0, n - 1, ql, qr) << endl;
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll INF = 1e17;
struct segment_tree
{
int n;
vector<ll> t;
segment_tree(vi const &a)
{
n = (int)a.size();
t.resize(4 * (int)a.size());
build(a, 1, 0, n - 1);
}
ll merge(ll a, ll b) { return min(a, b); }
void build(vi const &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
void update(int v, int tl, int tr, int ix, int new_val)
{
if (tl == tr and tl == ix)
t[v] = new_val;
else if (tl <= ix and ix <= tr)
{
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, ix, new_val);
update(2 * v + 1, tm + 1, tr, ix, new_val);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
auto query(int v, int tl, int tr, int ql, int qr)
{
if (tl == ql and tr == qr)
return t[v];
else if (ql > qr)
return INF;
else
{
int tm = (tl + tr) / 2;
return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
}
}
};
int main(void)
{
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
segment_tree st(a);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int ix, new_val;
cin >> ix >> new_val, ix--;
st.update(1, 0, n - 1, ix, new_val);
}
else
{
int ql, qr;
cin >> ql >> qr, ql--, qr--;
cout << st.query(1, 0, n - 1, ql, qr) << endl;
}
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
struct segment_tree
{
int n;
vector<ll> t;
segment_tree(vi const &a)
{
n = (int)a.size();
t.resize(4 * (int)a.size());
build(a, 1, 0, n - 1);
}
ll merge(ll a, ll b) { return a + b; }
void build(vi const &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
void update(int v, int tl, int tr, int ix, int new_val)
{
if (tl == tr and tl == ix)
t[v] = new_val;
else if (tl <= ix and ix <= tr)
{
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, ix, new_val);
update(2 * v + 1, tm + 1, tr, ix, new_val);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
auto query(int v, int tl, int tr, int ql, int qr)
{
if (tl == ql and tr == qr)
return t[v];
else if (ql > qr)
return 0LL;
else
{
int tm = (tl + tr) / 2;
return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
}
}
};
int main(void)
{
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
segment_tree st(a);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int ix, new_val;
cin >> ix >> new_val, ix--;
st.update(1, 0, n - 1, ix, new_val);
}
else
{
int ql, qr;
cin >> ql >> qr, ql--, qr--;
cout << st.query(1, 0, n - 1, ql, qr) << endl;
}
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll INF = 1e17;
struct segment_tree
{
int n;
vector<ll> t;
segment_tree(vi const &a)
{
n = (int)a.size();
t.resize(4 * (int)a.size());
build(a, 1, 0, n - 1);
}
ll merge(ll a, ll b) { return min(a, b); }
void build(vi const &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
build(a, 2 * v, tl, tm);
build(a, 2 * v + 1, tm + 1, tr);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
auto query(int v, int tl, int tr, int ql, int qr)
{
if (tl == ql and tr == qr)
return t[v];
else if (ql > qr)
return INF;
else
{
int tm = (tl + tr) / 2;
return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
}
}
};
int main(void)
{
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
segment_tree st(a);
while (q--)
{
int ql, qr;
cin >> ql >> qr, ql--, qr--;
cout << st.query(1, 0, n - 1, ql, qr) << endl;
}
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
ll n, a[NMAX], p[NMAX];
inline ll sum(int l, int r) { return p[r] - p[l - 1]; }
int main(void)
{
int q;
cin >> n >> q;
for (int i = 1; i <= n; ++i)
cin >> a[i], p[i] = a[i] + p[i - 1];
while (q--)
{
int l, r;
cin >> l >> r;
cout << sum(l, r) << endl;
}
return 0;
}