(CSU - 1770)按鈕控制彩燈實驗

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 344 Solved: 130

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

思路：一種很自然的思路就是對于一次區間[l,r]可以對[1,r]操作一次，在對[1,l-1]操作一次，然後最後隻要知道每個點操作了幾次就行。這就可以用樹狀數組在nlogn時間複雜度下實作，區間跟新，單點查詢，又我下面代碼的樹狀數組的update操作是更新x<=i<=n的點，是以是先對[l,n]操作一次，在對[r+1,n]操作一次。

當然這個題目還有一種更簡單的做法：就是記錄每個點左邊有多少個區間端點，注意左端點在這個點上算，而右端點在這個點上不算。

樹狀數組方法：

#include<cstdio>
#include<cstring>
using namespace std; 

const int maxn=;
int a[maxn],c[maxn];
int n,t;

int lowbit(int x)
{
    return x&-x;
}

void update(int x,int d)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=d;
}

int getsum(int x)
{
    int sum=;
    for(;x>;x-=lowbit(x)) sum+=c[x]; 
    return sum;
}
int main()
{
    while(~scanf("%d%d",&n,&t))
    {
        memset(c,,sizeof(c));
        for(int i=;i<=n;i++) scanf("%d",a+i);
        while(t--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            update(l,);
            update(r+,-);
        }
        for(int i=;i<=n;i++)
        {
            int ans=getsum(i);
            if(ans&) printf("%d",a[i]^);
            else printf("%d",a[i]);
            if(i!=n) printf(" ");
            else printf("\n");
        }
    }
    return ;
}
           

數端點數做法：

#include<cstdio>
#include<cstring>
using namespace std; 

const int maxn=;
int a[maxn],num[maxn];

int main()
{
    int n,t;
    while(~scanf("%d%d",&n,&t))
    {
        memset(num,,sizeof(num));
        for(int i=;i<=n;i++) scanf("%d",a+i);
        while(t--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            num[l]++;
            num[r+]++;
        }
        for(int i=;i<=n;i++)
        {
            num[i]+=num[i-];
            if(num[i]&) printf("%d",a[i]^);
            else printf("%d",a[i]);
            if(i!=n) printf(" ");
            else printf("\n");
        }
    }
    return ;
}