題目描述
Problem Description
N個氣球排成一排,從左到右依次編号為1,2,3…N.每次給定2個整數a b(a <= b),lele便為騎上他的“小飛鴿"牌電動車從氣球a開始到氣球b依次給每個氣球塗一次顔色。但是N次以後lele已經忘記了第I個氣球已經塗過幾次顔色了,你能幫他算出每個氣球被塗過幾次顔色嗎?
Input
每個測試執行個體第一行為一個整數N,(N <= 100000).接下來的N行,每行包括2個整數a b(1 <= a <= b <= N)。
當N = 0,輸入結束。
Output
每個測試執行個體輸出一行,包括N個整數,第I個數代表第I個氣球總共被塗色的次數。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
題目分析
看到題目:區間染色,計數區間點染色次數。模拟大法登場模不得,這麼做就沒意思了。
我們回顧一個經典的知識點:
字首和與差分
(這裡厚顔無恥的推薦自己的學習筆記:字首和與差分)
也許你立即反應出來了,這不就是差分的模闆題?
将指定序列的區間内的每個元素加,其差分序列的變化即為即為,其餘位置保持不變。下面給出證明:
設序列有個元素,在給定區間進行區間染色操作,染色深度為;
設序列為的差分序列,則差分序列為:;
是以;
AC Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int ball[N], n;
int main(){
ios_base::sync_with_stdio(false);
while (cin >> n && n){
memset(ball, 0, sizeof(ball));
for (int i = 1; i <= n; i++){
int a, b; cin >> a >> b;
ball[a]++, ball[b + 1]--;
}
for (int i = 1; i <= n; i++){
ball[i] += ball[i - 1];
cout << ball[i];
if(i != n) cout << ' '; else cout << endl;
}
}
return 0;
}