Ciao a tutti, ho bisogno di aiuto per risolvere il problema Flipping Coins.
ho provato a implmentare un segment tree con lazy propagation, ma ricevo 10/100.
nel vector lazy mi salvo se per il rispettivo nodo devo fare un flip o no.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, S = 1;
vector<ll>ST, LAZY;
void push(int attN, int sL, int sR){
if(LAZY[attN] == 0) return;
LAZY[attN] = 0;
ST[attN] = (sR - sL + 1) - ST[attN];
if(sL == sR) return;
LAZY[2 * attN] = (LAZY[2 * attN] + 1) % 2;
LAZY[2 * attN + 1] = (LAZY[2 * attN + 1] + 1) % 2;
}
void flip(int qL, int qR, int attN = 1, int sL = 0, int sR = N - 1){
if(qL > sR or qR < sL) return;
push(attN, sL, sR);
if(sL >= qL and qR >= sR){
LAZY[attN] = (LAZY[attN] + 1) % 2;
push(attN, sL, sR);
return;
}
int mid = (sL + sR) / 2;
flip(qL, qR, 2 * attN, sL, mid);
flip(qL, qR, 2 * attN + 1, mid + 1, sR);
ST[attN] = ST[2 * attN] + ST[2 * attN + 1];
}
ll query(int qL, int qR, int attN = 1, int sL = 0, int sR = N - 1){
if(qL > sR or qR < sL) return 0;
push(attN, sL, sR);
if(qL <= sL and qR >= sR){
return ST[attN];
}
int mid = (sL + sR) / 2;
return query(qL, qR, 2 * attN, sL, mid) +
query(qL, qR, 2 * attN + 1, mid + 1, sR);
}
int main(){
int Q;
cin >> N >> Q;
while(S < N) S <<= 1;
ST.assign(2 * S, 0);
LAZY = ST;
while(Q--){
int t, a, b;
cin >> t >> a >> b;
//a--; b--;
if(t == 0){
flip(a, b);
}else{
cout << query(a, b) << endl;
}
}
}
Grazie mille in anticipo!
