洛谷 P3870 [TJOI2009]开关

落日映苍穹つ 2021-10-29 12:24 393阅读 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 条评论，393人围观）

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

相关阅读

相关洛谷——P1876 开灯

P1876 开灯题目背景该题的题目是不是感到很眼熟呢? 事实上，如果你懂的方法，该题的代码简直不能再短。但是如果你不懂得呢？那。。。（自己去想）题目

喜欢ヅ旅行/ 2023年10月02日 12:19/ 0 赞/ 20 阅读

相关洛谷——P1161 开灯

P1161 开灯题目描述在一条无限长的路上，有一排无限长的路灯，编号为1,2,3,4,…1,2,3,4,…。每一盏灯只有两种可能的状态，开或者关。如果按一下

太过爱你忘了你带给我的痛/ 2023年10月02日 11:03/ 0 赞/ 26 阅读

相关 [洛谷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 赞/ 380 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关洛谷 P3870 [TJOI2009]开关

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

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

相关 [洛谷 P1377] TJOI2011 树的序

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

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

相关洛谷P3870开关题解

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

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