CSUOJ-1770按钮控制彩灯实验(区间覆盖)

1770: 按钮控制彩灯实验

Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 295 Solved: 106

Description

应教学安排，yy又去开心的做电学实验了。实验的内容分外的简单一串按钮通过编程了的EEPROM可以控制一串彩灯。然而选择了最low的一种一对一的控制模式，并很快按照实验指导书做完实验的yy马上感觉到十分无趣。于是他手指在一排按钮上无聊的滑来滑去，对应的彩灯也不断的变化着开关。已知每一个按钮按下会改变对应一个彩灯的状态，如此每次yy滑动都会改变一串彩灯的状态。现已知彩灯最初的状态，已经yy n次无聊的滑动的起点和终点l,r。现问彩灯最终的状态。

Input

有多组数据。

每组数据第一行，n(1<=n<=10^5)代表彩灯串长度，t(0<=t<=10^5)代表yy滑动的次数

第二行n个数（0表示灭1表示亮）给出n个彩灯的目前的状态。

之后t行每行两个数li，ri(1<=li<=ri<=n)代表每次滑动的区间。

Output

每组用一行输出最终的串的状态，格式见样例。

Sample Input

3 2

1 0 1

1 3

2 3

Sample Output

0 0 1

Hint

Source

OTTFF

题意：

给定初始01状态，然后每次区间覆盖后状态反转，0变1，1变0，问终止状态

可以转化为被覆盖了多少次，奇数变，偶数不变。

利用树状数组，那么对于每一个L,R，区间[1,R]+1，区间[1,L-1]-1，然后对于每个点getsum即可

然而并不需要那么复杂

可以对L,R，F[L]++,F[R+1]–，每次到达一个位置就res+=F[I],然后判断res奇偶性即可

第一种做法（树状数组）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=+;
int n,t,ax[maxn],c[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int val)
{
   for(int i=x;i>;i-=lowbit(i))
    c[i]+=val;
}
int sum(int x)
{
    int ans=;
    for(int i=x;i<=n;i+=lowbit(i))
        ans+=c[i];
    return ans;
}
int main()
{

    while(scanf("%d%d",&n,&t)!=EOF)
    {
       memset(c,,sizeof(c));
       for(int i=;i<=n;i++)
        scanf("%d",&ax[i]);
       for(int i=;i<t;i++)
       {
           int l,r;
           scanf("%d%d",&l,&r);
           add(l-,-);
           add(r,);
       }
      for(int i=;i<=n;i++)
      {
          if(i!=)
            printf(" ");
         int ans=sum(i);
         if(ans%)
            printf("%d",-ax[i]);
         else
            printf("%d",ax[i]);
      }
      printf("\n");
    }
    return ;
}
           

第二种做法：

#include<cstdio>
#include<cstring>
#include<cstring>
const int N =+;
int a[N],n,m,f[N],l,r;
int main()
{
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    memset(f,,sizeof(f));
    for(int i=;i<=n;++i)scanf("%d",a+i);
    for(int i=;i<=m;++i)
    {
      scanf("%d%d",&l,&r);
      f[l]++;
      f[r+]--;
    }
    int sum=;
    for(int i=;i<=n;++i)
    {
      sum+=f[i];
      if(sum&)a[i]^=;
    }
    for(int i=;i<=n;++i)printf("%d ",a[i]);
    printf("\n");
  }
}