好久没写题解了，水一篇。
这里主要想讲的是不同的处理方法，在阅读本篇题解前请确保读完题。
详解
一，排序
这很好理解，题目要求将热帖从小到大输出，同时题目中还有相对的时间这一概念，因此将输入的 \(id\) 与 \(ts\) 按照优先 \(id\) 其次 \(ts\) 的排序方式从小到大，排序，这样输出时就没必要刻意去处理顺序。
二，分段
为了将每一个帖子（编号不同）区分开，额外增设三个数组 \(L\)，\(R\)，\(ide\) 与变量 \(block\) 分别表示在排完序后的序列中共有数量为 \(block\) 的帖子，对于每一个 \(L_i\) 与 \(R_i\)，分别表示第 \(i\) 个热帖在序列中从 \(L_i\) 开始到 \(R_i\) 结束，并且第 \(i\) 个帖子的编号为 \(ide_i\)。请注意区分这里第 \(i\) 个帖子与第 \(i\) 个帖子的编号的区别。
部分分段代码展示
sort(s + 1 , s + n + 1 , cmp);
s[0].id = s[n + 1].id = -1;
fr(i , 1 , n)
{
if(s[i].id != s[i - 1].id)
{
R[block] = i - 1;
L[++block] = i;
ide[block] = s[i].id;
}
}
R[block] = n;
注意这里 s[0].id = s[n + 1].id = -1; 的目的是为了防止序列中有零这一编号的存在导致存储出现错误（不加只有八十八分）。最后补齐 \(R_{block}\)。
三，输出
在进行了上面的处理了，输出就变得非常简单了。只需要从 \(1\) 到 \(block\) 遍历一遍所有编号的帖子，判断是否是热帖即可。
四，判断是否为热帖
想必大家都会单调队列吧。不会的话给大家推荐一篇。
而这里我们只需要执行出队操作，将超过时限的点赞消息踢出队列即可，非常简单。
代码
#include<bits/stdc++.h>
#define ll int
#define mod 100000000
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
ll n , d , k;
struct node
{
ll ts , id;
}s[100005];
inline bool cmp(node x , node y)
{
return (x.id != y.id) ? x.id < y.id : x.ts < y.ts;
}
ll L[100005] , R[100005] , block;
ll ide[100005];
ll q[100005];
inline void max_deque(ll l , ll r , ll now_block)
{
ll head = 1 , tail = 0;
fr(i , l , r)
{
while(head <= tail && q[head] + d <= s[i].ts)
{
head++;
}
q[++tail] = s[i].ts;
if(tail - head + 1 >= k)
{
cout << now_block << '\n';
return;
}
}
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> d >> k;
fr(i , 1 , n)
{
cin >> s[i].ts >> s[i].id;
}
sort(s + 1 , s + n + 1 , cmp);
s[0].id = s[n + 1].id = -1;
fr(i , 1 , n)
{
if(s[i].id != s[i - 1].id)
{
R[block] = i - 1;
L[++block] = i;
ide[block] = s[i].id;
}
}
R[block] = n;
// fr(i , 1 , n)
// {
// cout << s[i].ts << ' ' << s[i].id << '\n';
// }
fr(i , 1 , block)
{
// cout << L[i] << ' ' << R[i] << ' ' << ide[i] << '\n';
max_deque(L[i] , R[i] , ide[i]);
}
return 0;
}