Recently, I tried to solve the problem: [Meteors](https://www.spoj.com/problems/METEORS/)↵
↵
It is a well-known problem that is usually solved using Parallel Binary Search.↵
↵
However, before learning about that technique, I attempted to solve it in my own way. Surprisingly, my solution somehow passed within the time limit, even though I expected it to get TLE based on my complexity estimation.↵
↵
↵
↵
<spoiler summary="MY CODE">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define endl "\n"↵
using namespace std;↵
#define memo(a,b) memset(a,b,sizeof(a))↵
↵
const ll N=3e5+5;↵
vector<pair<ll,ll>> t[2 * N];↵
ll sz;↵
↵
vector<ll> node;↵
void crn_node(ll p) {↵
for (p += sz; p >= 1; p >>= 1) ↵
if (!t[p].empty()) node.push_back(p); ↵
}↵
↵
void input(ll l, ll r, ll val, ll id) { // range [l, r) so r is r+1↵
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {↵
if (l & 1) ↵
{↵
ll pre=0;↵
if(t[l].size())pre=t[l][t[l].size()-1].second;↵
t[l++].push_back({id,val+pre});↵
}↵
if (r & 1)↵
{↵
--r;↵
ll pre=0;↵
if(t[r].size())pre=t[r][t[r].size()-1].second;↵
t[r].push_back({id,val+pre});↵
}↵
}↵
}↵
↵
int main ()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
↵
ll n,m; cin>>n>>m;↵
sz=m+1; // sz is the size if seg and seg is 1 base by ignoring 0 ↵
vector<ll>val[n+1];↵
for(ll i=1;i<=m;i++){ll x; cin>>x; val[x].push_back(i);}↵
↵
ll need[n+1];↵
for(ll i=1;i<=n;i++)cin>>need[i];↵
↵
ll q; cin>>q; // I named k as q from problem↵
for(ll i=1;i<=q;i++)↵
{↵
ll l,r;cin>>l>>r;↵
ll qv;cin>>qv;↵
if(l>r){ input(l,sz,qv,i); input(1,r+1,qv,i);}↵
else input(l,r+1,qv,i);↵
}↵
↵
// This is the part Im confused about ↵
for(ll i=1;i<=n;i++)↵
{↵
for(auto v:val[i])crn_node(v);↵
ll s=1; ll e=q; ll ans=-1;↵
while(s<=e)↵
{↵
ll mid=s+(e-s)/2;↵
ll sum=0;↵
for(auto v:node)↵
{↵
auto it = upper_bound(t[v].begin(), t[v].end(), make_pair(mid,LLONG_MAX));↵
if(it!=t[v].begin())↵
{↵
--it;↵
sum+=it->second;↵
if(sum>=need[i])break;↵
}↵
}↵
if(sum>=need[i]){ ans=mid;e=mid-1;}↵
else s=mid+1;↵
}↵
node.clear();↵
if(ans==-1)cout<<"NIE"<<endl;↵
else cout<<ans<<endl;↵
}↵
↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
At first, I estimated my code’s complexity as: `(n + m) * log(m) * log(q)^2`↵
↵
↵
The part that confuses me is the binary search: inside it, I loop over a `node vector` of size roughly `log(m)`. At the same time, the total size of all vectors could be around `q * log(m)`, as far as I understand.↵
↵
Does the segment tree structure somehow reduce the number of iterations or the effective number of values processed, or am I misunderstanding the actual complexity?↵
↵
For context, the `input` function is implemented as an iterative segment tree. Each query stores a prefix sum over a range, and the `crn_node` function is used to collect all the relevant node indices along the path for a given position `p`.↵
↵
To my understanding, I would have needed to remove at least one or more `log` factors from the complexity just to pass the time limits. ↵
↵
↵
If there’s some good reason why it passed, then this kind of trick could be really useful for other problems as well. I’d love to understand it properly and learn how and why. Any insights or guidance would be greatly appreciated:)↵
↵
**update:** [ I don’t really care whether people upvote or downvote, I just want to understand the reason. I’ll most probably delete the blog after I get the answer. If anyone know why it passed, please let me know.↵
I’ve even asked several AIs about this, but none of them gave a convincing explanation. Most of the time they just hallucinated answers, and when I tried to argue with the reasoning, the explanation kept changing every time, which made it even more confused ]
↵
It is a well-known problem that is usually solved using Parallel Binary Search.↵
↵
However, before learning about that technique, I attempted to solve it in my own way. Surprisingly, my solution somehow passed within the time limit, even though I expected it to get TLE based on my complexity estimation.↵
↵
↵
↵
<spoiler summary="MY CODE">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵
#define endl "\n"↵
using namespace std;↵
#define memo(a,b) memset(a,b,sizeof(a))↵
↵
const ll N=3e5+5;↵
vector<pair<ll,ll>> t[2 * N];↵
ll sz;↵
↵
vector<ll> node;↵
void crn_node(ll p) {↵
for (p += sz; p >= 1; p >>= 1) ↵
if (!t[p].empty()) node.push_back(p); ↵
}↵
↵
void input(ll l, ll r, ll val, ll id) { // range [l, r) so r is r+1↵
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {↵
if (l & 1) ↵
{↵
ll pre=0;↵
if(t[l].size())pre=t[l][t[l].size()-1].second;↵
t[l++].push_back({id,val+pre});↵
}↵
if (r & 1)↵
{↵
--r;↵
ll pre=0;↵
if(t[r].size())pre=t[r][t[r].size()-1].second;↵
t[r].push_back({id,val+pre});↵
}↵
}↵
}↵
↵
int main ()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
↵
ll n,m; cin>>n>>m;↵
sz=m+1; // sz is the size if seg and seg is 1 base by ignoring 0 ↵
vector<ll>val[n+1];↵
for(ll i=1;i<=m;i++){ll x; cin>>x; val[x].push_back(i);}↵
↵
ll need[n+1];↵
for(ll i=1;i<=n;i++)cin>>need[i];↵
↵
ll q; cin>>q; // I named k as q from problem↵
for(ll i=1;i<=q;i++)↵
{↵
ll l,r;cin>>l>>r;↵
ll qv;cin>>qv;↵
if(l>r){ input(l,sz,qv,i); input(1,r+1,qv,i);}↵
else input(l,r+1,qv,i);↵
}↵
↵
// This is the part Im confused about ↵
for(ll i=1;i<=n;i++)↵
{↵
for(auto v:val[i])crn_node(v);↵
ll s=1; ll e=q; ll ans=-1;↵
while(s<=e)↵
{↵
ll mid=s+(e-s)/2;↵
ll sum=0;↵
for(auto v:node)↵
{↵
auto it = upper_bound(t[v].begin(), t[v].end(), make_pair(mid,LLONG_MAX));↵
if(it!=t[v].begin())↵
{↵
--it;↵
sum+=it->second;↵
if(sum>=need[i])break;↵
}↵
}↵
if(sum>=need[i]){ ans=mid;e=mid-1;}↵
else s=mid+1;↵
}↵
node.clear();↵
if(ans==-1)cout<<"NIE"<<endl;↵
else cout<<ans<<endl;↵
}↵
↵
↵
}↵
~~~~~↵
</spoiler>↵
↵
At first, I estimated my code’s complexity as: `(n + m) * log(m) * log(q)^2`↵
↵
↵
The part that confuses me is the binary search: inside it, I loop over a `node vector` of size roughly `log(m)`. At the same time, the total size of all vectors could be around `q * log(m)`, as far as I understand.↵
↵
Does the segment tree structure somehow reduce the number of iterations or the effective number of values processed, or am I misunderstanding the actual complexity?↵
↵
For context, the `input` function is implemented as an iterative segment tree. Each query stores a prefix sum over a range, and the `crn_node` function is used to collect all the relevant node indices along the path for a given position `p`.↵
↵
To my understanding, I would have needed to remove at least one or more `log` factors from the complexity just to pass the time limits. ↵
↵
↵
If there’s some good reason why it passed, then this kind of trick could be really useful for other problems as well. I’d love to understand it properly and learn how and why. Any insights or guidance would be greatly appreciated:)↵
↵
**update:** [ I don’t really care whether people upvote or downvote, I just want to understand the reason. I’ll most probably delete the blog after I get the answer. If anyone know why it passed, please let me know.↵
I’ve even asked several AIs about this, but none of them gave a convincing explanation. Most of the time they just hallucinated answers, and when I tried to argue with the reasoning, the explanation kept changing every time, which made it even more confused ]
