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 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;
}
Click to show code.
using namespace std;
using ii = pair<int, int>;
int main(void)
{
int n, ai;
stack<ii> S;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> ai;
while (!S.empty() and S.top().first >= ai)
S.pop();
if (S.empty())
cout << "0 ";
else
cout << S.top().second + 1 << " ";
S.push({ai, i});
}
return 0;
}