洛谷——P2574 XOR的艺术
2024-10-01 01:34:05
P2574 XOR的艺术
很久之前就想挑战一下这道题了,线段树下传标记的入门题,跟区间加法下传标记类似。
#include<bits/stdc++.h>
#define N 1000005
#define LL long long
#define RE register
#define IN inline using namespace std; IN void in(int &x){
int flg=;RE char ch=getchar();x=;
for(;ch>''||ch<'';){if(ch=='-') flg=-;ch=getchar();}
for(;ch<=''&&ch>='';ch=getchar()) x=x*+ch-'';
x*=flg;
} struct node{
int l,r,w,f;
}tr[N];
int n,m,ans,X,tot;
int e[N]; IN void build(int k,int l,int r){
tr[k].l=l;tr[k].r=r;
if(l==r){
tr[k].w=e[l];
return;
}int mid=(l+r)/;
build(k*,l,mid);build(k*+,mid+,r);
tr[k].w=tr[k*].w+tr[k*+].w;
} IN void down(int k){
tr[k].f^=;
tr[k*].w=(tr[k*].r-tr[k*].l+)-tr[k*].w;
tr[k*+].w=(tr[k*+].r-tr[k*+].l+)-tr[k*+].w;
tr[k*].f^=;
tr[k*+].f^=;
} IN void ask_interval(int k,int l,int r){
int ll=tr[k].l,rr=tr[k].r,mid=(ll+rr)/;
if(ll>=l&&rr<=r){
ans+=tr[k].w;
return;
}if(tr[k].f) down(k);
if(l<=mid) ask_interval(k*,l,r);
if(r>mid) ask_interval(k*+,l,r);
tr[k].w=tr[k*].w+tr[k*+].w;
} IN void change_interval(int k,int l,int r){
int ll=tr[k].l,rr=tr[k].r,mid=(ll+rr)/;
if(ll>=l&&rr<=r){
tr[k].w=(rr-ll+)-tr[k].w;
tr[k].f^=;
return;
}if(tr[k].f) down(k);
if(l<=mid) change_interval(k*,l,r);
if(r>mid) change_interval(k*+,l,r);
tr[k].w=tr[k*].w+tr[k*+].w;
} int main()
{
in(n);in(m);
for(int i=;i<=n;i++)
scanf("%1d",&e[i]);
build(,,n);
while(m--){
int p,l,r;
in(p);in(l);in(r);
if(p==){
change_interval(,l,r);
}else {
ans=,ask_interval(,l,r);
printf("%d\n",ans);
}
}return ;
}
最新文章
- sql server cross/outer apply 用法
- Leetcode Insert Interval
- jquery的blur之后,focus获取不到焦点的解决办法
- PHP: How to print a debug log?
- TSQL的连乘
- 009 The Interfaces In JAVA(官网文档翻译)
- c编程之排序
- 【转载】Android使用Application总结
- HTTP状态码——对照表
- iOS 开发学习35 本地化
- [USACO12JAN]爬山Mountain Climbing
- 带着萌新看springboot源码8(spring ioc源码上)
- If you did this already, delete the swap file ";.git/.MERGE_MSG.swp";
- HTTPS笔记:使用 SSLEngine 为 aioserver 服务器提供 SSL 访问支持
- bzoj2819 DFS序 + LCA + 线段树
- Spring+Hibernate 多数据源不同事务创建
- Win10+Ubuntu 二三事
- 综合数据api接口使用
- [系统软件]Ubuntu 18.04中的Shutter禁用了“编辑”选项解决
- C# System.IO.File