[](#pC "pC")pC
==============

[](#題目 "題目")題目
--------------

疫情期間口罩是每個人的必備之物，但傻瓜國的人總是特別笨，都等到口罩用完時才會出門去買，這導致每個人在排隊買口罩時都沒有戴口罩，讓傻瓜國的疫情一年比一年嚴重。

今天在傻瓜國有Y個人在排隊買口罩，編號1~Y，其中有人陰性，有人陽性，但每個確診者的傳染力都不盡相同，假設一個確診者的傳染力為xxx，那麼他可能會傳染給排在他前xxx個及後xxx個的這些人。過幾天後，這Y個人各自到檢測站做PCR篩檢，有些人的結果為陰轉陽，傻瓜國的政府為了控制疫情，他們想知道這些新確診者的所有可能感染原個數(別忘了他們是傻瓜國，他們不會想去追朔是被誰傳染的)，請你幫幫傻瓜國的政府計算新確診者的可能感染源個數。

假設病毒傳染只會發生在沒有戴口罩的時候，所以確診者只考慮被當天買口罩的這N個人感染，且不考慮在當天排隊時的二次傳染，也就是只考慮被已知確診者傳染。

### [](#輸入說明 "輸入說明")輸入說明:

> 第一行會有兩個數字N、M，N代表已知確診者(在排隊買口罩時已確診)，M代表新確診者(被已知確診者傳染的人)。接下來會有N行，每一行有兩個數字Pi、Xi，Pi代表已知確診者在排隊時的位置，Xi代表該確診者的傳染力。最後一行會有M個數，代表新確診者在排隊時的位置Qi，且按照位置順序排列。保證不會有已知確診者及新確診者為同一位的情況。

N M
P1 X1
P2 X2
.
.
.
PN XN
Q1 Q2 ... QM

### [](#輸出說明 "輸出說明")輸出說明:

> 依照輸入順序輸出每個新確診者的可能傳染原個數。

* 1<=N，M<=1^4
* 1<=Pi，Xi，Qi<=10^18

### [](#子任務 "子任務")子任務:

> 30% : Pi<=1000，Xi<=50，M=1
> 60% : Pi<=1000，Xi<=50
> 90% : Pi<=100000，xi<=10^9
> 100% : 無限制

* * *

範例輸入:

5 4
3 10
5 2
7 6
10 8
999 1
1 4 8 100

範例輸出:

2 4 3 0

輸出說明:

1號可能被3號及7號傳染，故為2
4號可能被3號、5號、7號及10號傳染，故為4
8號可能被3號、7號及10號傳染，故為3
沒有已知確診者可以傳染到第100位，故為0

* * *

範例輸入:

2 4
100000000000 10
100000000005 2

100000000001 100000000003 100000000008 100000000011

範例輸出:

1 2 1 0

* * *

範例輸入:

1 2
999999999999999999 10
999999999999999988
1000000000000000000

範例輸出:

0 1

* * *

[](#Solutions "Solutions")Solutions
-----------------------------------

### [](#Subtask-1 "Subtask-1")Subtask 1:

由於只有一位新確診者，因此我們只要把所有已知確診者找一遍，如果可以傳染到此確診者位置的話答案就+1。
時間複雜度:O(N)=O(10000)

Code

#include <bits/stdc++.h>
using namespace std;

int main(){
int n,m;
cin >> n >> m;

vector<int> p(n),x(n);
for(int i=0;i<n;i++) cin >> p[i] >> x[i];

int target;
cin >> target;

int ans=0;
for(int i=0;i<n;i++){
if(p[i]-x[i]<=target && target<=p[i]+x[i]) ans++;
}
cout << ans << '\n';
}

### [](#Subtask-2 "Subtask-2")Subtask 2:

但依照上面的方法在subtask 2就不管用了，因為時間複雜度是O(N\*M)，O(10^8)會超時，這時候就可以換個角度思考，站在已知確診者的視角，把所有可能被我感染的人都做上記號，這樣在查詢新感染者的時候就可以馬上得知傳染源個數了。
時間複雜度:O(N\*2Xi)=O(1000000)

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000
int cnt[MAXN+5];

int main(){
int n,m;
cin >> n >> m;

vector<int> p(n),x(n);
for(int i=0;i<n;i++) cin >> p[i] >> x[i];

for(int i=0;i<n;i++){
for(int j=max(p[i]-x[i],1);j<=min(p[i]+x[i],MAXN);j++){
cnt[j]++;
}
}

for(int i=0;i<m;i++){
int q;
cin >> q;
cout << cnt[q] << ' ';
}
}

### [](#Subtask-3 "Subtask-3")Subtask 3:

但要把所有的已知確診者可能傳染給的所有位置都做上記號也太耗時了:O(N\*Max\_Pi)，這時候就可以用線性的方法來優化(黃宥嘉學長教過)。假設要把\[x,y\]區間做上記號，可以把x做一個加1的標記，y+1做一個減1的標記，這樣就只要跑一遍並依照記號改動就可以得知每個位置的感染原數了。
時間複雜度:O(Max\_Pi)+O(100000)

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
int cnt[MAXN+5];

int main(){
int n,m;
cin >> n >> m;

for(int i=0;i<n;i++){
int p,x;
cin >> p >> x;
cnt[max(p-x,1)]++;
cnt[min(p+x,MAXN)+1]--;
}
for(int i=1;i<=MAXN;i++) cnt[i]+=cnt[i-1];

for(int i=0;i<m;i++){
int q;
cin >> q;
cout << cnt[q] << ' ';
}
}

### [](#Subtask-4 "Subtask-4")Subtask 4:

但由於數字太大無法開一個陣列並做上記號，這時候就要用到離散化 : 重新排列，使數字與數字間沒有空隙。再給予新編號後就可以使用Subtask 3方法100%解決此題。
時間複雜度:O(2N+M)=O(30000)

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(a) (a).begin(),(a).end()
#define MAXN 30000

int cnt[MAXN+5];

vector<ll> dis; //discretization:離散化
set<ll> used;

int getID(ll x){
return lower_bound(all(dis),x)-dis.begin()+1;
}

void Push(ll x){
if(!used.count(x)){
dis.push_back(x);
used.insert(x);
}
}

int main(){
int n,m;
cin >> n >> m;

vector<pair<ll,ll>> pos;

for(int i=0;i<n;i++){
ll x,r;
cin >> x >> r;
pos.push_back({x-r,1});
pos.push_back({x+r+1,-1});
Push(x-r);
Push(x+r+1);
}

vector<ll> q(m);
for(int i=0;i<m;i++){
cin >> q[i];
Push(q[i]);
}

sort(dis.begin(),dis.end());
sort(pos.begin(),pos.end());

for(int i=0;i<n*2;i++){
int newPos=getID(pos[i].first);
cnt[newPos]+=pos[i].second;
}
for(int i=1;i<=MAXN;i++) cnt[i]+=cnt[i-1];

for(int i=0;i<m;i++){
int newPos=getID(q[i]);
cout << cnt[newPos] << ' ';
}
}

Solution 2
也可不用陣列標記，直接做也是一個方法 : 把在哪個位置標記的記號丟進一個vector並排序，並照順序改變當前的可能感染原個數，再判斷此區間是否屬於某個新確診者，此方法也可100%解決此題。
時間複雜度:O(2N)=O(20000)

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1e18

signed main(){
int n,m;
cin >> n >> m;

vector<pair<ll,int>> pos;

for(int i=0;i<n;i++){
ll x,r;
cin >> x >> r;
pos.push_back({max(x-r,1ll),1});
pos.push_back({x+r+1,-1});
}

//border
pos.push_back({1ll,0});
pos.push_back({2*MAX+1,0});
n++;

sort(pos.begin(),pos.end());

queue<ll> q;
for(int i=0;i<m;i++){
ll x;
cin >> x;
q.push(x);
}

int cnt=0;
for(int i=0;i<n*2;){
if(q.empty()) break;

do{
cnt+=pos[i++].second;
}while(i<n*2 && pos[i-1].first==pos[i].first);

ll l=pos[i-1].first;
ll r=pos[i].first;

while(!q.empty() && l<=q.front() && q.front()<r){
cout << cnt << ' ';
q.pop();
}
}
}