Let's say we have an array of size N(N <= 100000) and Q queries (Q <= 100000), where each query is either:

• Add(l, r, x), add x to every element between l and r

• Query(l, r) — number of elements that are zero between l and r

Each add operation is performed under a certain (fixed) modulo m. Any ideas on how this can be done?

I saw that the version where the graph is directed I can solve it with dynamic programming, any ideas about the undirected one?

We have an N*N matrix, can we achieve better than transposing the matrix into an array, and then sorting it?

I did some online searching and found that quickselect eliminates the log factor, how can we extend quickselect to 2 dimensions?

I came across this problem while practicing, but I didn't solve it, some suggestions for these types of problems would be appreciated. We have a tree with n nodes(n <= 300000), and each node has a number A(1 <= A <= 10^9). The first line of the input consists of two numbers n and A0 (the number of nodes and the number on node 1). Each of the next n-1 lines has two numbers Ai and the parent of node i. For every node except the root, we need to find the number of nodes that have a strictly smaller number than the current node. Then we need to update every node on the path from the current node to the root, set Aj = max(Aj, Ai)

Example:
5 400
350 0
300 1
450 2
420 0
550 3
Answer:
0
0
3
0
4

Given a weighted undirected graph with N nodes and N-1 edges, we are also given S special nodes. For each special node, there is a convoy that is sent to the furthest node for each Si (if there are ties, the ending node is chosen at random). We are asked to find the maximum number of convoys that can't reach their target nodes if we remove one node from the graph and the number of ways to achieve this.

Example:

N = 4
0 1 3
1 2 10
1 3 11
S = 3
0 2 3
Ans: 3 1

We have 3 convoys({0 -> 3}, {2 -> 3}, {3 -> 2}), each of the convoys passes through node 1, so if we remove this node we have 3 convoys that can't get to their ending node, and the number of ways to do this is 1.

Given an array of size n, with elements between 1 and n find the maximum number of elements that occur exactly twice in any subarray. Constraints (1 <= n <= 100000)

6
1 3 1 3 2 1
Output: 2 (subarray 1-4, 1-5)

12
5 5 1 3 9 9 9 1 3 5 2 1
Output: 3 (subarray 1-9, 2-10, 2-11)

I have partial points, running O(n^2) solution shown below.

        int ans = 0;
	for(int i = 0; i < n; i++){
		map<int,int> cnt;
		int cans = 0;
		for(int j = i; j < n; j++){
			cnt[arr[j]]++;
			if(cnt[arr[j]] == 2)
				cans++;
			else if(cnt[arr[j]] == 3)
				cans--;
				
			ans = max(ans, cans);
		}
	}
	cout<<ans<<endl;

Any ideas how to solve the problem in O(n log n).