为什么这个代码能过:
#include<bits/stdc++.h>
using namespace std;
const int N=8e5+10;
struct Tree{
int l,r;
int sum;
bool lazy;
}tr[N];
int n,m;
void pushup(int u) {
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
return;
}
void pushdown(int u) {
if(tr[u].lazy) {
tr[u<<1].lazy=!tr[u<<1].lazy,tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
tr[u<<1|1].lazy=!tr[u<<1|1].lazy,tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
tr[u].lazy=0;
}
return;
}
void build(int u,int l,int r) {
if(l==r)tr[u]={l,r,0,0};
else {
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
return;
}
void change(int u,int l,int r) {
if(l<=tr[u].l&&tr[u].r<=r)tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum,tr[u].lazy=!tr[u].lazy;
else {
pushdown(u);
int mid=tr[u].r+tr[u].l>>1;
if(l<=mid)change(u<<1,l,r);
if(r>mid)change(u<<1|1,l,r);
pushup(u);
}
return;
}
int ask(int u,int l,int r) {
pushdown(u);
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
else {
int res=0,mid=tr[u].r+tr[u].l>>1;
if(l<=mid)res+=ask(u<<1,l,r);
if(r>mid)res+=ask(u<<1|1,l,r);
return res;
}
}
int main() {
cin>>n>>m;
build(1,1,n);
while(m--) {
bool op;
cin>>op;
int l,r;
cin>>l>>r;
if(op)cout<<ask(1,l,r)<<endl;
else change(1,l,r);
}
return 0;
}
但这个不行:
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
struct Tree{
int l,r;
int sum;
bool lazy;
}tr[N];
int n,m;
void pushup(int u) {
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
return;
}
void pushdown(int u) {
if(tr[u].lazy) {
tr[u<<1].lazy=!tr[u<<1].lazy,tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
tr[u<<1|1].lazy=!tr[u<<1|1].lazy,tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
tr[u].lazy=0;
}
return;
}
void build(int u,int l,int r) {
if(l==r)tr[u]={l,r,0,0};
else {
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
return;
}
void change(int u,int l,int r) {
if(l<=tr[u].l&&tr[u].r<=r)tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum,tr[u].lazy=!tr[u].lazy;
else {
pushdown(u);
int mid=tr[u].r+tr[u].l>>1;
if(l<=mid)change(u<<1,l,r);
if(r>mid)change(u<<1|1,l,r);
pushup(u);
}
return;
}
int ask(int u,int l,int r) {
pushdown(u);
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
else {
int res=0,mid=tr[u].r+tr[u].l>>1;
if(l<=mid)res+=ask(u<<1,l,r);
if(r>mid)res+=ask(u<<1|1,l,r);
return res;
}
}
int main() {
cin>>n>>m;
build(1,1,n);
while(m--) {
bool op;
cin>>op;
int l,r;
cin>>l>>r;
if(op)cout<<ask(1,l,r)<<endl;
else change(1,l,r);
}
return 0;
}
差别只有N的值,AC的是8e5+10,RE的是4e5+10
可题目中的n≤105
线段树开4e5不是足够的吗