Help in optimizing this cs academy problem .

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
8	-is-this-fft-	149
9	pajenegod	145
10	BledDest	144

The problem asks to toggle bits in a given range that after certain operations all bits becomes 0 .

My O(N2) solution is for a given light bulb if it is on the switch it off and update all the given ranges , but this will be N^2 complexity . How can we reduce it to O(n) . The last lines of the editorial i couldn't understood , how the author is updating the ranges .

how to do it . ?

Can anyone help me what the author is done in this code

#include <bits/stdc++.h>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef vector<int> vi;

const int MOD = 1e9 + 7;
const int INF = INT_MAX / 2;

int main() {
	int N; cin >> N;
	string s; cin >> s;
	vector<int> r(N), c(N);
	rep(i, N) scanf("%d", &r[i]);
	rep(i, N) scanf("%d", &c[i]);
	vector<int> diff(N + 1);
	int x = 0;
	ll ans = 0;
	rep(i, N) {
		x = (x + diff[i]) % 2;
		if (x != s[i] - '0') {
			ans += c[i];
			x = !x;
			diff[r[i]]++;
		}
	}
	cout << ans << endl;
}

Блог пользователя atlasworld