Hello, I tried segment tree with lazy propagation on this problem. Implementation is taken from this article. I got TLE on test#7.
In my opinion, my solution is nlog(n). updateRange works in log(n) time and I call it q times hence qlog(n). Then I call n times queryRange, it's runtime also log(n) hence nlog(n). Overall complexity is nlog(n) + qlog(n). It should work well in given constraints but unfortunately I got TLE.
So what I am missing?
Your problem is that
void build(vector<long long> a, int node, int start, int end)makes a copy of the vector over and over. To not make a copy use
void build(vector<long long> &a, int node, int start, int end)