csu 1770按钮控制彩灯实验(树状数组)

1770: 按钮控制彩灯实验

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 194 Solved: 65
[Submit][Status][Web Board]

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

Sample Output

0 0 1

区间更新+单点求值 水,时间复杂度O(n*log(n)).

#include <iostream>

#include <cstring>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

const int N = ;

int a[N];

int c[N],n,m;

int lowbit(int i){

    return i&(-i);

}

void update(int idx,int v){

    for(int i=idx;i<=n;i+=lowbit(i)){

        c[i]+=v;

    }

}

int getsum(int idx){

    int sum = ;

    for(int i=idx;i>=;i-=lowbit(i)){

        sum+=c[i];

    }

    return sum;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF){

        memset(c,,sizeof(c));

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

        }

        while(m--){

            int l,r;

            scanf("%d%d",&l,&r);

            update(l,);

            update(r+,-);

        }

        for(int i=;i<n;i++){

            if(getsum(i)%==){

                if(a[i]==) printf("1 ");

                else printf("0 ");

            }else {

                printf("%d ",a[i]);

            }

        }

        if(getsum(n)%==){

            if(a[n]==) printf("1\n");

            else printf("0\n");

        }else printf("%d\n",a[n]);

    }

    return ;

}

秒客网