洛谷 3870 [TJOI2009]开关
2024-09-04 03:13:19
【题解】
线段树基础题。对于每个修改操作把相应区间的sum改为区间长度-sum即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
#define rg register
#define N 200010
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((a[u].l+a[u].r)>>1)
#define len(x) (a[x].r-a[x].l+1)
using namespace std;
int n,m;
struct tree{
int l,r,sum,mark;
}a[N<<];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
void build(int u,int l,int r){
a[u].l=l; a[u].r=r;
if(l<r) build(ls,l,mid),build(rs,mid+,r);
}
inline void pushdown(int u){
a[u].mark^=;
a[ls].mark^=; a[ls].sum=len(ls)-a[ls].sum;
a[rs].mark^=; a[rs].sum=len(rs)-a[rs].sum;
}
void update(int u,int r,int l){
if(l<=a[u].l&&a[u].r<=r){
a[u].mark^=;
a[u].sum=len(u)-a[u].sum;
return;
}
if(a[u].mark) pushdown(u);
if(l<=mid) update(ls,r,l);
if(r>mid) update(rs,r,l);
a[u].sum=a[ls].sum+a[rs].sum;
}
int query(int u,int r,int l){
if(l<=a[u].l&&a[u].r<=r) return a[u].sum;
if(a[u].mark) pushdown(u);
int ret=;
if(l<=mid) ret+=query(ls,r,l);
if(r>mid) ret+=query(rs,r,l);
return ret;
}
int main(){
n=read(); m=read(); build(,,n);
while(m--){
int opt=read();
if(opt) printf("%d\n",query(,read(),read()));
else update(,read(),read());
}
return ;
}
最新文章
- [转] eclipse SVN中文件修改后图标不变黑星解决
- sound tips
- Swift - IBOutlet返回nil(fatal error: unexpectedly found nil while unwrapping an Optional value)
- asp.net获取ip地址的方法
- vim 多行注释
- CoreAnimation (CALayer 动画)
- 在Delphi开发的服务中调用指定应用程序
- CentOS 7安装配置Apache HTTP Server
- 【转】关于python中re模块split方法的使用
- deepin系统如何安装deb格式的软件
- JAVA提高十九:WeakHashMap&;EnumMap&;LinkedHashMap&;LinkedHashSet深入分析
- STL中算法分类
- 第一次面试经历(hr面)
- 将labelme 生成的.json文件进行可视化的代码+label.png 对比度处理的matlab代码
- 牛客挑战赛30 小G砍树 树形dp
- PHP开发——数据类型
- 分享 - 27 个机器学习、数学、Python 速查表
- 《Git权威指南》读书笔记
- [java]String和Date、Timestamp之间的转换
- ajax的post请求方式