社区讨论
求助QAQ(玄2关)
P2846[USACO08NOV] Light Switching G参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lyzipg5u
- 此快照首次捕获于
- 2024/07/24 15:23 2 年前
- 此快照最后确认于
- 2024/07/24 16:09 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
struct Node{
int js=0,len=0;
bool bj;
}a[800000];
void New_Tree(int p,int l,int r){
a[p].len=r-l+1;
a[p].js=0;
a[p].bj=0;
if(a[p].len==1){
return;
}
int mid=l+r>>1;
New_Tree(p*2+1,mid+1,r);
New_Tree(p*2,l,mid);
}
void work(int p,int l,int r,int x,int y){
int mid=l+r>>1;
if(x<=l&&y>=r){
a[p].bj=!a[p].bj;
return;
}
if(x>mid){
work(p*2+1,mid+1,r,x,y);
}
else if(y<=mid){
work(p*2,l,mid,x,y);
}
else{
work(p*2,l,mid,x,y);
work(p*2+1,mid+1,r,x,y);
}
}
void push_down(int p){
a[2*p].bj=!a[2*p].bj;
a[2*p+1].bj=!a[2*p+1].bj;
}
void push_up(int p){
if(a[2*p].bj){
a[2*p].bj=!a[2*p].bj;
a[2*p].js=a[2*p].len-a[2*p].js;
push_down(2*p);
}
if(a[2*p+1].bj){
a[2*p+1].bj=!a[2*p+1].bj;
a[2*p+1].js=a[2*p+1].len-a[2*p+1].js;
push_down(2*p+1);
}
if(a[p].len>1){
a[p].js=a[2*p].js+a[2*p+1].js;
}
}
int ans(int p,int l,int r,int x,int y){
if(a[p].bj){
a[p].bj=!a[p].bj;
a[p].js=a[p].len-a[p].js;
push_down(p);
}
if(x<=l&&y>=r){
return a[p].js;
}
int mid=l+r>>1;
if(x>mid){
return ans(p*2+1,mid+1,r,x,y);
}
else if(y<=mid){
return ans(p*2,l,mid,x,y);
}
else{
return ans(p*2,l,mid,x,y)+ans(p*2+1,mid+1,r,x,y);
}
push_up(p);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
New_Tree(1,1,n);
for(int i=1;i<=m;i++){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==0){
work(1,1,n,x,y);
}
else{
printf("%d\n",ans(1,1,n,x,y));
}
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...