Help in an Assignment problem

#1

https://codeforces.com/contest/369/problem/E

Please share a segment tree code for this. and kindly explain a bit. thanks in advance

#2

Hi @utkarsh.lal9430310535
sorry for the late reply.
u can refer to dis solution


in this we r basically doing this in every query,
let query= 1 4 7 i.e find segment with either 1,4,or 7.
in the code, we are basically finding those segments which starts and end from

  1. start=2,3 end=2,3
    2)start=5,6 end=5,6
    3)start=8,MAX end=8,Max
    basically finding answer to above queries, we find those segments which donot contain 1,4, and 7.
    hence we can get the answer by subtracting above answer from n and hence getting those segments which contains 1 ,4, and 7
    Hope dis helps.
    if u still face any difficulties, feel free to post ur doubt here.
#3

thanks got it. But I tried using a seg tree to do +1 on each point and then for every given seg range I tried to find the sum, if it’s positive then some point lies inside it. but this gave TLE. I even tried BIT for optimization but again the same result . What is the difference in time complexity of our code can you tell? Thank you in advance.

#4

can u pls share ur code.

#5
#6

in dis part of ur code
while(m–){
int q;
cin>>q;
int x[q];
for(int i=0;i<q;i++){
cin>>x[i];
modify(x[i],+1);
}

m and q are of range 10^5 hence O(m*q) complexity will give tle.