# [NOIP2005 普及組] 校門外的樹

## 題目描述

某校大門外長度為 l?的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是 1?米。我們可以把馬路看成一個數(shù)軸，馬路的一端在數(shù)軸 0?的位置，另一端在 l的位置；數(shù)軸上的每個整數(shù)點，即0,1,2,...,l，都種有一棵樹。

由于馬路上有一些區(qū)域要用來建地鐵。這些區(qū)域用它們在數(shù)軸上的起始點和終止點表示。已知任一區(qū)域的起始點和終止點的坐標都是整數(shù)，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。

## 輸入格式

第一行有兩個整數(shù)，分別表示馬路的長度 l?和區(qū)域的數(shù)目 m。

接下來 m?行，每行兩個整數(shù) u, v，表示一個區(qū)域的起始點和終止點的坐標。

## 輸出格式

輸出一行一個整數(shù)，表示將這些樹都移走后，馬路上剩余的樹木數(shù)量。

## 樣例 #1

### 樣例輸入 #1

```
500 3
150 300
100 200
470 471
```

### 樣例輸出 #1

```
298
```

## 提示

**【數(shù)據(jù)范圍】**

• 對于?20%?的數(shù)據(jù)，保證區(qū)域之間沒有重合的部分。
• 對于?100%?的數(shù)據(jù)，保證 1≤l≤104，1≤m≤100，0≤u≤v≤l。

**【題目來源】**

NOIP 2005 普及組第二題

n,m=map(int, input().split())
ar=[1 for x in range(n+1)]  #生成0~n個共計n+1棵樹
for i in range(m):a,b=map(int,input().split())for j in range(a,b+1):ar[j]=0  #范圍內(nèi)挖掉的樹置0，若區(qū)間有重合也不過是重復置0
print(sum(ar))

題目描述

在一條無限長的路上，有一排無限長的路燈，編號為?1,2,3,4,…1,2,3,4,…。

每一盞燈只有兩種可能的狀態(tài)，開或者關。如果按一下某一盞燈的開關，那么這盞燈的狀態(tài)將發(fā)生改變。如果原來是開，將變成關。如果原來是關，將變成開。

在剛開始的時候，所有的燈都是關的。小明每次可以進行如下的操作：

指定兩個數(shù)，a,t（a?為實數(shù)，t?為正整數(shù)）。將編號為 ?a?,?2×a?,?3×a?,…,?t×a??的燈的開關各按一次。其中??k??表示實數(shù)?k?的整數(shù)部分。

在小明進行了?n?次操作后，小明突然發(fā)現(xiàn)，這個時候只有一盞燈是開的，小明很想知道這盞燈的編號，可是這盞燈離小明太遠了，小明看不清編號是多少。

幸好，小明還記得之前的?n?次操作。于是小明找到了你，你能幫他計算出這盞開著的燈的編號嗎？

輸入格式

第一行一個正整數(shù)?n，表示?n?次操作。

接下來有?n?行，每行兩個數(shù)，ai?,ti?。其中?ai??是實數(shù)，小數(shù)點后一定有?6?位，ti??是正整數(shù)。

輸出格式

僅一個正整數(shù)，那盞開著的燈的編號。

輸入輸出樣例

輸入 #1復制

3
1.618034 13
2.618034 7
1.000000 21

輸出 #1復制

20

說明/提示

記 T=i=1∑n?ti?=t1?+t2?+t3?+?+tn?。

• 對于?30%?的數(shù)據(jù)，滿足 T≤1000；
• 對于?80%?的數(shù)據(jù)，滿足 T≤200000；
• 對于?100%?的數(shù)據(jù)，滿足 T≤2000000；
• 對于?100%?的數(shù)據(jù)，滿足 n≤5000，1≤ai?<1000，1≤ti?≤T。

數(shù)據(jù)保證，在經(jīng)過?n?次操作后，有且只有一盞燈是開的，不必判錯。而且對于所有的?i?來說，ti?×ai??的最大值不超過?2000000。

n=int(input())
arr=[0 for i in range(2000000)] 
'''
開線段樹 關燈狀態(tài)為0，開燈為1，因為題目說了最后只有一盞燈亮，那么
就找到那一盞燈的編號
'''
for i in range(n):a,t=map(float,input().split())for j in range(1,int(t)+1):#原來亮現(xiàn)在暗if arr[int(j*a)]==0:arr[int(j*a)]=1#原來暗現(xiàn)在亮elif arr[int(j*a)]==1:arr[int(j*a)]=0
print(arr.index(1))