1619. Snip Runs From the Chain
A tailor trims a long ribbon of beads stored as the singly linked list head. Each entry cuts[i] = [p, len] removes len consecutive beads starting at the p-th bead (1-based) of the ribbon as it is right now, or fewer if the ribbon ends first; if p is larger than the current length nothing is removed. Cuts are applied in order. Return a long[] whose i-th entry is the sum of the values removed by cut i. The list has up to 100000 nodes with values in [-10^9, 10^9] and there are up to 100000 cuts with 1 <= p, len <= 100000, so walking from the head every time is too slow. Find the p-th surviving node with a Fenwick tree of alive flags, then follow the next links of an index-based doubly linked list, unlinking nodes as they go: O((n + q) log n) time.
Example 1
- Input:
- head = [1,2,3,4,5], cuts = [[2,2],[2,5],[1,1]]
- Output:
- [5,9,1]
- Explanation:
The first cut removes 2 and 3, the second removes 4 and 5 (list ends first), and the last removes 1.
Example 2
- Input:
- head = [10,-4,7], cuts = [[4,1],[3,9]]
- Output:
- [0,7]
- Explanation:
The first cut starts beyond the end and removes nothing; the second removes the last node, 7.
Constraints
1 ≤ length ≤ 105
1 ≤ cuts.length ≤ 105
1 ≤ p, len ≤ 105
-109 ≤ val ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n)