↵
↵
<spoiler summary = "problem statement">↵
Time Limit : 2 sec <br>↵
You have a long street of length N, and you want to install some lamps to light some segments of the↵
road. So you will be given Q queries of two kinds:↵
↵
1 L R : Install a lamp that can light the segment from L to R.↵
↵
2 L R : What is the minimum number of installed lamps needed to light the segment [L, R], more formally,↵
find the number of the smallest group of installed lamps such that the combined segments they light up↵
fully cover the segment from point L to point R.↵
↵
↵
Input↵
-----↵
↵
The first line contains one integer N (1 ≤ N ≤ 2 × 10^5). The length of the street.↵
↵
The second line contains one integer Q (2 ≤ Q ≤ 2 × 10^5). The number of queries.↵
↵
Then follows Q lines. The i-th line contains three integers ti Li Ri. (ti ∈ {1, 2}, 1 ≤ Li ≤ Ri ≤ N), which↵
represents the i-th query.↵
↵
It is guaranteed that there is at least one query of type 2.↵
↵
↵
Output↵
------↵
↵
For each query of type 2, output one line containing its answer or -1 if the answer doesn’t exist.↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary = "Code">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAXN = 200000;↵
int n, q, B; ↵
int val[MAXN + 2]; ↵
int lazy[(MAXN+450)/450 + 2]; ↵
↵
void addLamp(int L,int R){ ↵
int bl = L / B , br = R / B;↵
↵
if (bl == br){ ↵
for (int i=L;i<=R;++i) val[i] = max(val[i], R);↵
return;↵
}↵
↵
int endL = (bl+1)*B - 1;↵
for (int i=L;i<=endL;++i) val[i] = max(val[i], R);↵
↵
for (int b=bl+1;b<br;++b)↵
lazy[b] = max(lazy[b], R);↵
↵
int startR = br*B;↵
for (int i=startR;i<=R;++i) val[i] = max(val[i], R);↵
}↵
↵
int minLamps(int L,int R){ ↵
int cur=L, ans=0;↵
while (cur <= R){↵
int b = cur / B;↵
int best = max(val[cur], lazy[b]); ↵
if (best < cur) return -1; ↵
++ans;↵
cur = best + 1; ↵
}↵
return ans;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cin >> n >> q;↵
B = int(sqrt(n)) + 1;↵
fill(val, val+n+2, -1);↵
fill(lazy, lazy+ (n+B-1)/B + 2, -1);↵
while (q--){↵
int t,L,R; cin >> t >> L >> R;↵
--L; --R; ↵
if (t==1) addLamp(L,R);↵
else cout << minLamps(L,R) << '\n';↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
I'm solving a problem where I can insert lamps on a street segment [L, R], and later need to answer queries like:↵
“What’s the minimum number of lamps needed to fully cover [L, R]?”↵
↵
In my solution (which passed all tests), each query walks from L to R using a greedy jump to the farthest lamp covering the current position. In the worst case — like when every lamp covers only one position — this query can walk every single position in [L, R], so O(N) per query.↵
↵
Since there can be up to Q = N = 2·10⁵ such queries, isn’t the total worst-case complexity O(N²)?↵
↵
Yet the solution is accepted .↵
Why does it pass if O(N²) time is theoretically possible?↵
Does the test data avoid this case? Or is there something I’m missing in the analysis?
↵
<spoiler summary = "problem statement">↵
Time Limit : 2 sec <br>↵
You have a long street of length N, and you want to install some lamps to light some segments of the↵
road. So you will be given Q queries of two kinds:↵
↵
1 L R : Install a lamp that can light the segment from L to R.↵
↵
2 L R : What is the minimum number of installed lamps needed to light the segment [L, R], more formally,↵
find the number of the smallest group of installed lamps such that the combined segments they light up↵
fully cover the segment from point L to point R.↵
↵
↵
Input↵
-----↵
↵
The first line contains one integer N (1 ≤ N ≤ 2 × 10^5). The length of the street.↵
↵
The second line contains one integer Q (2 ≤ Q ≤ 2 × 10^5). The number of queries.↵
↵
Then follows Q lines. The i-th line contains three integers ti Li Ri. (ti ∈ {1, 2}, 1 ≤ Li ≤ Ri ≤ N), which↵
represents the i-th query.↵
↵
It is guaranteed that there is at least one query of type 2.↵
↵
↵
Output↵
------↵
↵
For each query of type 2, output one line containing its answer or -1 if the answer doesn’t exist.↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary = "Code">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAXN = 200000;↵
int n, q, B; ↵
int val[MAXN + 2]; ↵
int lazy[(MAXN+450)/450 + 2]; ↵
↵
void addLamp(int L,int R){ ↵
int bl = L / B , br = R / B;↵
↵
if (bl == br){ ↵
for (int i=L;i<=R;++i) val[i] = max(val[i], R);↵
return;↵
}↵
↵
int endL = (bl+1)*B - 1;↵
for (int i=L;i<=endL;++i) val[i] = max(val[i], R);↵
↵
for (int b=bl+1;b<br;++b)↵
lazy[b] = max(lazy[b], R);↵
↵
int startR = br*B;↵
for (int i=startR;i<=R;++i) val[i] = max(val[i], R);↵
}↵
↵
int minLamps(int L,int R){ ↵
int cur=L, ans=0;↵
while (cur <= R){↵
int b = cur / B;↵
int best = max(val[cur], lazy[b]); ↵
if (best < cur) return -1; ↵
++ans;↵
cur = best + 1; ↵
}↵
return ans;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cin >> n >> q;↵
B = int(sqrt(n)) + 1;↵
fill(val, val+n+2, -1);↵
fill(lazy, lazy+ (n+B-1)/B + 2, -1);↵
while (q--){↵
int t,L,R; cin >> t >> L >> R;↵
--L; --R; ↵
if (t==1) addLamp(L,R);↵
else cout << minLamps(L,R) << '\n';↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
I'm solving a problem where I can insert lamps on a street segment [L, R], and later need to answer queries like:↵
“What’s the minimum number of lamps needed to fully cover [L, R]?”↵
↵
In my solution (which passed all tests), each query walks from L to R using a greedy jump to the farthest lamp covering the current position. In the worst case — like when every lamp covers only one position — this query can walk every single position in [L, R], so O(N) per query.↵
↵
Since there can be up to Q = N = 2·10⁵ such queries, isn’t the total worst-case complexity O(N²)?↵
↵
Yet the solution is accepted .↵
Why does it pass if O(N²) time is theoretically possible?↵
Does the test data avoid this case? Or is there something I’m missing in the analysis?
