DooIt's blog

By DooIt, history, 9 years ago, In English

I've encountered some interesting problems but I couldn't solve them. I really need some help.

First problem is: Given 3 integers N, M, X (1 <= N, M <= 105, 1 <= X <= M). Calculate the number of ways to create N segments [L1, R1], [L2, R2], …, [LN, RN] (Li <= Hi) such that they satisfy two conditions:

  • there is no i and k (i != k) that Li <= Lk <= Hk <= Hi
  • There is at least one segment which has Li = X
Two ways are different if there exists j such that segment j in two ways are different.

Second problem is: Given a tree with 4 nodes 1, 2, 3 and 4. Node 1 is root. Nodes 2, 3 and 4 are leaf nodes. Diameter of the tree is the longest path on the tree. We have Q queries (1 <= Q <= 5 * 105). For each query, we are given a leaf node v (1 <= v <= N, N is the number of nodes in the tree). Then we add two new nodes N + 1 and N + 2 to the tree, create two edges (v, N + 1) and (v, N + 2). Output after each query is the diameter of the tree.

Thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DooIt (previous revision, new revision, compare).