Ciao, stavo provando a svolgere rangetree1 ma ottengo un output errato in tutti i test tranne il primo,
l’idea è molto semplice, uso un segment tree e in ogni nodo mantengo il conteggio delle teste, quando avviene un flip inverto il numero di teste e di croci. Ho ricontrollato varie volte il codice e
sospetto sia un errore di implementazione, tuttavia non riesco a trovarlo, qualcuno ha qualche suggerimento?
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
struct SegmentTree{
int sz;
vector <bool> array;
struct Node{
ll sum;
int lzset;
int nodi;
Node(){
sum=0;
lzset=-1;
}
void set(bool a){
sum=a;
nodi=1;
lzset=-1;
}
void merge(Node a,Node b){
sum=a.sum+b.sum;
nodi=a.nodi+b.nodi;
}
};
vector <Node> segTree;
void make(vector <bool> a){
array=a;
sz=1;
while(sz<a.size())sz*=2;
segTree.resize(sz*2);
build(1,0,sz-1);
}
void build(int p,int l,int r){
if(r==l){
segTree[p].set(array[l]);
}
else{
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
segTree[p].merge(segTree[p*2],segTree[p*2+1]);
}
}
int get_sum(int l,int r){
return get_sum2(1,l,r,0,sz-1);
}
void propagate(int p){
if(segTree[p].lzset==-1)return;
if(segTree[p].nodi==1){
segTree[p].lzset=-1;
return;
}
else{
segTree[p*2].sum=segTree[p*2].nodi-segTree[p*2].sum;
segTree[p*2+1].sum=segTree[p*2+1].nodi-segTree[p*2+1].sum;
segTree[p*2].lzset=segTree[p].lzset;
segTree[p*2+1].lzset=segTree[p].lzset;
segTree[p].lzset=-1;
}
}
void flip2(int p,int l,int r,int tl,int tr){
if(tr<l || tl>r) return ;
propagate(p);
if(tl>=l && tr<=r){
segTree[p].sum=segTree[p].nodi-segTree[p].sum;
segTree[p].lzset=1;
return;
}
else{
int mid=(tl+tr)/2;
flip2(p*2,l,r,tl,mid);
flip2(p*2+1,l,r,mid+1,tr);
}
segTree[p].merge(segTree[p*2],segTree[p*2+1]);
}
void flip(int l,int r){
flip2(1,l,r,0,sz-1);
}
int get_sum2(int p,int l,int r,int tl,int tr){
if(tl>tr) return 0;
if(tr<l || tl>r) return 0;
propagate(p);
if(tl>=l && tr<=r){
return segTree[p].sum;
}
int mid=(tl+tr)/2;
return get_sum2(p*2,l,r,tl,mid)+get_sum2(p*2+1,l,r,mid+1,tr);
}
};
void compute(){
ll n,q;
cin>>n>>q;
vector <bool> a;
for(int i=0;i<n;i++)a.pb(0);
SegmentTree si;
si.make(a);
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==0){
int a,b;
cin>>a>>b;
si.flip(a,b);
}
else{
int a,b;
cin>>a>>b;
cout<<si.get_sum(a,b)<<'\n';
}
}
}