题目描述

有一条无限长的数轴。

数轴上有 $n$ 个机器人和 $m$ 个尖刺，它们分别位于数轴上的特定点。第 $i$ 个机器人位于位置 $a_i$，第 $i$ 个尖刺位于位置 $b_i$。只要机器人碰到尖刺，它就会阵亡。

共有 $k$ 条指令传达给机器人，每条指令要么让机器人向左移动一格，要么向右移动一格。

对于每个 $i$ ($1 \le i \le k$)，请输出在执行完前 $i$ 条指令后，还有多少机器人幸存。

输入格式

第一行输入一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n, m, k \le 2 \cdot 10^5$) —— 机器人数量、尖刺数量和指令数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) —— 机器人所在的位置。保证 $a$ 中所有元素互不相同。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($0 \le b_i \le 10^9$) —— 尖刺所在的位置。保证 $b$ 中所有元素互不相同。

第四行是长度为 $k$ 的字符串，表示传给机器人的指令。每个字符要么是 L，表示向左移动一格，要么是 R，表示向右移动一格。

保证所有测试用例中 $n, m, k$ 的总和不超过 $2 \cdot 10^5$。

额外约束： 保证机器人和尖刺不会出现在同一个位置。

输出格式

输出 $k$ 个整数，第 $i$ 个整数表示执行完前 $i$ 条指令后幸存的机器人数量。

Python 用户注意： 提交时请选用 PyPy3 / PyPy2（取决于你用的 Python 版本），不要用 Python3 或 Python2。

样例

输入

Plaintext

3
2 1 3
0 1
2
LRR
2 3 3
2 4
1 3 5
LRL
3 2 3
1 3 7
9 6
RRL

输出

Plaintext

2 2 1
0 0 0
3 2 2

样例说明

• 对于第一个测试用例：
  • 第一个机器人会移动到 $0 \to -1 \to 0 \to 1$，因此不会阵亡。
  • 第二个机器人会移动到 $1 \to 0 \to 1 \to 2$，执行第三条指令后会碰到位置 $2$ 的尖刺，阵亡。
• 对于第二个测试用例：
  • 两个机器人移动一次后都会阵亡。

题目思路

每个机器人找到左右两边最近能撞死的钉子，然后开一个“死亡笔记”：记录位移量达到多少可以创死该机器人。然后开始模拟询问，在这个地方创死过机器人以后就不用重复检查了。

参考代码

C++

#include<iostream>  
#include<vector>  
#include<set>  
#include<map>  
#include<algorithm>  

using namespace std;  

void solve(){  
    int n, m, k;  
    cin >> n >> m >> k;  
    
    set<int> a;  
    for(int i = 0; i < n; i++){  
        int x; 
        cin >> x;  
        a.insert(x);  
    }  
    
    vector<int> b;  
    for(int i = 0; i < m; i++){  
        int x; 
        cin >> x;  
        b.push_back(x);  
    }  
    
    map<int, vector<int>> death_note;  
    
    for(int x : a){  
        int idx = lower_bound(b.begin(), b.end(), x) - b.begin();  
        
        if(idx < m){  
            int dist = b[idx] - x;  
            if(abs(dist) <= k){  
                death_note[dist].push_back(x);  
            }  
        }  
        
        if(idx > 0){  
            int dist = b[idx-1] - x;  
            if(abs(dist) <= k){  
                death_note[dist].push_back(x);  
            }  
        }  
    }  
    
    string s; 
    cin >> s;  
    
    int curr = 0;  
    for(auto c : s){  
        if(c == 'L') curr--;  
        else curr++;  
        
        if(death_note.count(curr)){  
            for(auto robot : death_note[curr]){  
                a.erase(robot);  
            }  
            death_note.erase(curr);  
        }  
        
        cout << a.size() << " ";  
    }  
    cout << endl;  
}  
  
int main(){  
    int t; 
    cin >> t;  
    while(t--) solve();  
}