Hello Codeforces!
Today I was solving one problem from codeforces edu
My code
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
struct segtree {
vector<int> tree;
int size;
const int zero = 0;
void init(int n) {
size = 1;
while (size < n)size *= 2;
tree.assign(size * 2 - 1, 0);
}
void build(vector<int> &a, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < a.size())
tree[x] = a[lx];
} else {
int mid = (lx + rx) >> 1;
build(a, 2 * x + 1, lx, mid);
build(a, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
}
void build(vector<int> &a) {
init(a.size());
build(a, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = v;
return;
}
int mid = (lx + rx) >> 1;
if (i < mid)set(i, v, 2 * x + 1, lx, mid);
else set(i, v, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int find(int k, int x, int lx, int rx) {
if (rx - lx == 1) {
return lx;
}
int m = (lx + rx) >> 1;
if (k < tree[2 * x + 1])return find(k, 2 * x + 1, lx, m);
else return find(k - tree[2 * x + 1], 2 * x + 2, m, rx);
}
int find(int k) {
find(k, 0, 0, size);
}
};
int32_t main() {
fast
int n, q;
cin >> n >> q;
vector<int> a(n);
for (auto &i: a)cin >> i;
segtree st;
st.build(a);
while (q--) {
int c;
cin >> c;
if (c == 1) {
int i;
cin >> i;
st.set(i, 1 - a[i]);
a[i] = 1 - a[i];
} else {
int k;
cin >> k;
cout << st.find(k) << endl;
}
}
return 0;
}
/*
* @Nargulyev
*/
Can someone tell me how I can solve this problem? (Sorry for my English)
Thanks!
Let's change the problem statement, find the prefix where the sum is k+1(since it starts counting from 0), now it's a famous problem with segment trees, and try to solve it for the general case(not 01) assuming there always exists a prefix
but for this problem in particular(I'm not going to solve the question above but give another approach(which is kinda similar))
maintain a segment tree where
seg[idx] = the sum of its rangeand it's obvious that where r-l < 1 seg[idx] = a[l]I'm just assuming the counting starts from 1(increment k), you start from the root, if seg[left] <= k traverse to left otherwise right, and if (node.right — node.left) was less than 1 you've found the element.
for the update function, it's like incrementing a[i] by 1,-1 which you should be able to do, but in case not:
starting form the root, if that element was in the left child u traverse to that otherwise right, when (r — l < 1) you simply do a[i] ^= 1(toggle it), and rebuild the segment tree from the bottom.
smth like this:
thank you but everything you said I have already done in my program.
you can check it
I corrected and got accepted with your code.
Oh my God, thank you, but could you explain to me why this is the right
the since the big find function(the actual one) returns a number, in the second one you're calling it and it does it's job perfectly fine, but you're not returning it.
take this:
and expecting the code to output 25,
instead you should've used
cout << add(10, 15) << endl;thanks