洛谷P3870 [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：

输出样例#1：

1

2

思路：还是一道线段树区间异或，思路跟之前做的洛谷P2574和洛谷P2846完全一样。

代码：

#include<cstdio>

#include<cctype>

#define maxn 100007

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

int n,m,sum[maxn<<2],lazy[maxn<<2];

inline int qread() {

  char c=getchar();int num=0,f=1;

  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

  for(;isdigit(c);c=getchar()) num=num*10+c-'0';

  return num*f;

}

inline void pushup(int rt) {

  sum[rt]=sum[ls]+sum[rs];

}

inline void pushdown(int rt, int len) {

  if(lazy[rt]) {

    lazy[ls]^=1;

    lazy[rs]^=1;

    sum[ls]=(len-(len>>1))-sum[ls];

    sum[rs]=(len>>1)-sum[rs];

    lazy[rt]=0;

  }

}

void modify(int rt, int l, int r, int L, int R) {

  if(L>r||R<l) return;

  if(L<=l&&r<=R) {

    lazy[rt]^=1;

    sum[rt]=r-l+1-sum[rt];

    return;

  }

  pushdown(rt,r-l+1);

  int mid=(l+r)>>1;

  modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);

  pushup(rt);

}

int csum(int rt, int l, int r, int L, int R) {

  if(L>r||R<l) return 0;

  if(L<=l&&r<=R) return sum[rt];

  pushdown(rt,r-l+1);

  int mid=(l+r)>>1;

  return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R);

}

int main() {

  n=qread(),m=qread();

  for(int i=1,k,l,r;i<=m;++i) {

    k=qread(),l=qread(),r=qread();

    if(!k) modify(1,1,n,l,r);

    else printf("%d\n",csum(1,1,n,l,r));

  }

  return 0;

}

巴特西

洛谷P3870 [TJOI2009]开关

题目描述

输入输出格式

输入输出样例

最新文章

热门文章