Given an array A of N integers answer Q queries of type (L, R). Answer to a query (L, R) is the sum of distinct integers in the range A[L...R]

Constraints: N, Q <= 100000

0 <= L <= R < N

abs(A[i]) <= 1 000 000 000

I read somewhere that this can be done using persistence segment tree.

So, it would be helpful if one can explain that approach.

Other approach are welcome too.

Hi, i was wondering how would we carry out these operation on an array using segment tree.

Formal statement of the problem.

Given an array if N positive integers, and Q queries perform these operations.

1 L R X. Decrease every element in the range [L...R] by by value X

2 L R. Return how many element in the range[L...R] are strictly greater than 0

N, Q <= 10^5

0 <= X <= 10000

Initial values of array can be as large as 1 000 000 000 What information would i have to store in each node ?

Hi there, i was looking to get some insight on the following problem.

Question — What is the probability of n randomly drawn lines intersecting at a point in 2-D space. ? Stated in a different way, what is the probability that a randomly chosen system of n equation in 2 variables yields a result.

Follow up — does this probability equals the probability of n random planes intersecting at a point in 3-D space ? more generally, does this equal to the probability of n random N-dimension hyperplanes intersecting at a point in N-D space ?

I did googled things, but i found this question stacked with some constraint on space, for example, in THIS the space is constrained to a circle and in THIS the spaces is a 3-D grid. these made me thing whether there exist something for general case or not. Please Help. Feel free to ask for any further clarification about the setting of the problem ?

Hi, i was trying to solve this PROBLEM, i am familiar with segment tree and lazy propagation stuff, what i could not see how to perform update operation.

I feel that we need to store the fibonacci sum of segment at each node, or do we need to store something else ? elaborative explanation will be highly appreciated. Thanks in advance.

Hi there, i am stuck at the problem Codeforces Eductional Round 6 I read the tutorial and tried implementing the same, here is my Code. I think the problem is with the lazy propagation, please try to find the mistake.

Problem statement is here and i am getting TLE for this solution. Looks O(31*N) to me, any idea(s) how to improve??

Hi all, i am trying to implement FFT in Python(2.6) and i think i am facing precision issues. I checked the DFT of the coefficient vector at n complex nth roots of unity in a separate program and the values differ just only in precison, but still my FFT program is giving me wrong answer. Do anyone how to circumvent this issue ?. Here is my FFT Program, and here is the checker LINK

Hi, Codeforces folks, i am stuck at this problem LINK, The problem seems to be quite simple, you just have to make a string palindrome adding minimum number of characters at the end, so basically we need to find the longest suffix palindrome and then add the remaining character at the end. My solution implements the same here is the [LINK]

Here is the link to the problem LINK. This is a simple string matching problem. I got AC verdict even with the brute force solution but i am getting TLE when using Z-algorithms in Python. Can anyone figure out why i am getting TLE for THIS solution.Thanks in advance

Hi Codeforces folks, i was wondering whether python has alternative for Bitset(in C++) to use it as flag in sieve, i thought of using a string but it is immutable, so do we have an alternative for bitset in python or are we compelled to make a list?

Hi, I am trying to solve this www.spoj.com/problems/DIVSUM2 but getting TLE . I have pre-calculated primes up-to 10**7 and then for each test-cases i factorize it using O(sqrt(n)) method and then run GP formula for each of the prime factor of the given integer. Here is my solution... http://ideone.com/ZcDbYN... Please Help...