思路

  此问题是一个区间问题，对于每一个x都是一个删除区间，在没有其他删除的情况下区间即为[x,x+y-1]，当x所在位置在其他删除区间中，那么整体往右移，直至不在删除区间中，当删除区间的右部在其他删除区间中，那么就要进行删除区间的融合，改变y的值，将后一个删除区间的长度加上，循环操作，直至右部没有在其他删除区间中，用map记录删除区间的左右端点

代码

python

from collections import defaultdict

T = int(input())
mp = {}

while T > 0:
    T -= 1

    x, y = map(int, input().split())
    l = max((key for key in mp if key <= x), default=None)

    while l is not None and mp[l] >= x:
        x = mp[l] + 1
        l = max((key for key in mp if key <= x), default=None)

    r = min((key for key in mp if key > x), default=None)
    if r is not None:
        while r is not None and r <= x + y - 1:
            temp = mp[r]
            del mp[r]
            y += temp - r + 1
            r = min((key for key in mp if key > r), default=None)

    mp[x] = x + y - 1
    print(x + y - 1)

java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        TreeMap<Long, Long> map = new TreeMap<>();

        while (T-- > 0) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            Long l = map.floorKey(x);

            while (l != null && map.get(l) >= x) {
                x = map.get(l) + 1;
                l = map.floorKey(x);
            }
            Long r = map.higherKey(x);
            if (r != null) {
                while (r != null && r <= x + y - 1) {
                    long temp = map.get(r);
                    map.remove(r);
                    y += temp - r + 1;
                    r = map.higherKey(r);
                }
            }

            map.put(x, x + y - 1);
            System.out.println(x + y - 1);
        }
    }
}

题目内容

小美有一个无限长的正整数序列[$1,2,3,...$]，现在有$q$次询问，每次询问给出两个数字$x$和$y$。

对于每一次询问，小美会执行$y$次删除操作，然后输出最后一个被删除的数字。

删除操作是指，找到第一个大于等于$x$的数字，然后将其从序列中永久删除。

输入描述

第一行输入一个整数q(1≤q≤10^5)代表询问次数。

接下来$q$行，每行输入两个整数$x,y$($1≤x,y≤10^9$)，其含义已在题目中说明。

输出描述

对于每一个询问，在一行上输出一个整数，代表在这次操作中最后被删除的那个数字

样例1

输入

3
3 3
3 3
2 1 

输出

5 
8 
2

说明

序列初始为[$1,2,3,4,5,6,7,8,9,...$]。

• 对于第$1$次询问，依次删除$3,4,5$，序列变为[$1,2,6,7,8,9,...$]。
• 对于第$2$次询问，依次删除$6,7,8$，序列变为[$1,2,9,...$]。
• 对于第$3$次询问，删除$2$，序列变为[$1,9,...$]。