luogu3870 tjoi2009 开关

luogu3870 tjoi2009 开关

​​ 题目描述

现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，……，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

输入输出格式

输入格式：

第一行有两个整数N和M，分别表示灯的数目和操作的数目。接下来有M行，每行有三个整数，依次为：c, a, b。其中c表示操作的种类，当c的值为0时，表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界（1 ≤ a ≤ b ≤ N）。

输出格式：

每当遇到第二种操作时，输出一行，包含一个整数：此时在查询的区间中打开的灯的数目。

输入输出样例

输入样例#1：

4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4 输出样例#1：

1 2 可怜的我昨天因为这个一看是线段树，就直接按照染色来做了，其实应该取反，计算数目的时候应该用整体，减去当前的数目

tree[x].f表示是否覆盖的标记false 表示还没有下放需要下放，true表示下放过了 实际上下放的应该都是反转操作而不是染色操作 一定要^1因为我有可能对这一段反复修改 假如再对当前相同一段就行操作，那么就不用下放了，下放答案反而错误

#include#define N 110000inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();} return x;}struct node{ bool f;int num,l,r,left,right;}tree[N<<2];int cnt=0;void build(int &x,int l,int r){ x=++cnt;tree[x].l=l;tree[x].r=r;tree[x].f=true; if (l==r){ tree[x].num=tree[x].left=tree[x].right=0; return ; } int mid=(l+r)>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}inline void pushdown(int x){ int l1=tree[x].left,r1=tree[x].right;// tree[l1].f=tree[r1].f=false; tree[l1].f^=1;tree[r1].f^=1; tree[l1].num=tree[l1].r-tree[l1].l+1-tree[l1].num; tree[r1].num=tree[r1].r-tree[r1].l+1-tree[r1].num; tree[x].f=true;}inline int query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r)return tree[x].num; if (tree[x].f==false) pushdown(x); int mid=(tree[x].l+tree[x].r)>>1; int ans1=0,ans2=0; if (l<=mid) ans1=query(tree[x].left,l,r); if (r>mid) ans2=query(tree[x].right,l,r); return ans1+ans2;}inline void updata(int x){ tree[x].num=tree[tree[x].left].num+tree[tree[x].right].num;}inline void change(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r){ tree[x].f^=1; tree[x].num=tree[x].r-tree[x].l+1-tree[x].num; return; } if (tree[x].f==false) pushdown(x); int mid=(tree[x].l+tree[x].r)>>1; if (l<=mid) change(tree[x].left,l,r); if (r>mid) change(tree[x].right,l,r); updata(x);}int n,m,root,op,a,b;void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d\n",tree[x].l,tree[x].r); if (tree[x].right) print(tree[x].right);}int main(){ //freopen("3870.in","r",stdin);// freopen("3870.out","w",stdout); n=read();m=read();build(root,1,n);// print(root); for (int i=1;i<=m;++i){ op=read();a=read();b=read(); if (op) printf("%d\n",query(root,a,b)); else change(root,a,b); // printf("%d\n",tree[root].num); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。