洛谷 P3870 [TJOI2009]开关

落日映苍穹つ 2021-10-29 12:24 261阅读 0赞

看题面可以目测得出本题要求对01区间进行区间修改和查询。

查询区间和，就直接维护区间和。在修改时，就用总灯数（长度）减去当前开着的灯数（当前区间和）作为新的答案。

考虑修改两次相当于没修改，所以\\(lazytag\\)就累计操作数，如果是偶数则不用更新呢，奇数反之。

其余部分与线段树模板基本相同。

#include<iostream> #define int long long using namespace std; const int MAXN=100005; int n,m,a[MAXN],seg[MAXN<<2],tag[MAXN<<2]; int u,v,w; inline void upd(int x) { seg[x]=seg[x<<1]+seg[x<<1|1]; } inline int push_down(int x,int l,int r) { tag[x<<1]+=tag[x];tag[x<<1|1]+=tag[x]; int mid=(l+r)>>1; if(tag[x]&1) { seg[x<<1]=(mid-l+1)-seg[x<<1]; seg[x<<1|1]=(r-mid)-seg[x<<1|1]; } tag[x]=0; } inline int query(int x,int l,int r,int ql,int qr) { int temp=0,mid=(l+r)>>1; if(ql<=l&&r<=qr) return seg[x]; push_down(x,l,r); if(ql<=mid) temp+=query(x<<1,l,mid,ql,qr); if(mid<qr) temp+=query(x<<1|1,mid+1,r,ql,qr); return temp; } inline void modify(int x,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { seg[x]=(r-l+1)-seg[x]; tag[x]+=1; } else { push_down(x,l,r); int mid=(l+r)>>1; if(ql<=mid) modify(x<<1,l,mid,ql,qr); if(mid<qr) modify(x<<1|1,mid+1,r,ql,qr); upd(x); } } signed main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u>>v>>w; if(u==0) modify(1,1,n,v,w); else cout<<query(1,1,n,v,w)<<"\n"; } return 0; }

转载于:https://www.cnblogs.com/ehznehc/p/11296852.html

发表评论取消回复

表情：

评论列表（有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 322 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 317 阅读

相关 [洛谷P5205]【模板】多项式开根

题目大意：给你$n$项多项式$A(x)$，求出$B(x)$满足$B^2(x)\\equiv A(x)\\pmod\{x^n\}$ 题解：考虑已经求出$B\_0(x)$满足$B

不念不忘少年蓝@/ 2021年12月22日 04:15/ 0 赞/ 270 阅读

相关【洛谷 P3975】 [TJOI2015]弦论（后缀自动机）

[题目链接][Link 1] 建出后缀自动机。 T=0，每个子串算一次，否则每个子串算该子串的\\(endpos\\)集合大小次。用\\(f\[i\]\\)表示结

桃扇骨/ 2021年12月21日 06:39/ 0 赞/ 199 阅读

相关洛谷P1220 关路灯【区间dp】

题目：[https://www.luogu.org/problemnew/show/P1220][https_www.luogu.org_problemnew_show_P12

我就是我/ 2021年12月12日 15:43/ 0 赞/ 265 阅读

相关洛谷 P2051 [AHOI2009]中国象棋

题目描述这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清

心已赠人/ 2021年11月22日 08:12/ 0 赞/ 300 阅读

相关洛谷 P4571 BZOJ 2257 [JSOI2009]瓶子和燃料

[bzoj题目链接][bzoj] > 上面hint那里是选择第2个瓶子和第3个瓶子 Time limit 10000 ms Memory limit 131072 kB

淡淡的烟草味﹌/ 2021年11月02日 00:20/ 0 赞/ 219 阅读

相关洛谷 P3870 [TJOI2009]开关

看题面可以目测得出本题要求对01区间进行区间修改和查询。查询区间和，就直接维护区间和。在修改时，就用总灯数（长度）减去当前开着的灯数（当前区间和）作为新的答案。考虑修改

落日映苍穹つ/ 2021年10月29日 12:24/ 0 赞/ 262 阅读

相关 [洛谷 P1377] TJOI2011 树的序

问题描述众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：1、空树中加入一个键值k，则变为只有一个结点的二叉查找树，此结点的键值即为k；2、在非空树中插入一

我不是女神ヾ/ 2021年10月23日 12:22/ 0 赞/ 543 阅读

相关洛谷P3870开关题解

我们先看题面，一看是一个区间操作，再看一下数据范围，就可以很轻松地想到是用一个数据结构来加快区间查询和修改的速度，所以我们很自然的就想到了线段树。但是这个题还跟普通的线段树

「爱情、让人受尽委屈。」/ 2021年10月01日 03:52/ 0 赞/ 385 阅读