思路一：动态前缀和

使用动态前缀和统计所有时间的赞数量，然后按区间查询就能判定是不是热帖。

本来以为最多是TLE，结果是MLE 2333

大概是因为对每个帖子都整了前缀和数组的关系把？

#include <iostream>

using namespace std;

const int N = 10010;

int tr[N][N];

bool st[N];

int n, d, k;

int lb(int x)
{
    return x & -x;
}

void add(int id, int ts)
{
    for(int i = ts; i < N; i += lb(i))
        tr[id][i]++;
}

int query(int id, int ts)
{
    int res = 0;
    for(int i = ts; i > 0; i -= lb(i))
        res += tr[id][i];
    return res;
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    int ts, id;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &ts, &id);
        ts++;
        st[id] = true;
        add(id, ts);
    }

    for(int i = 1; i < N; i++)
    {
        if(!st[i]) continue;
        for(int t = 1; t < N; t++)
        {
            if(query(i, t + d + 1) - query(i, t) >= k)
            {
                cout << i << endl;
                break;
            }
        }
    }
}

思路二：只对单个帖子做前缀和

在思路一上进行改进，主要是想起了1241. 外卖店优先级这题。

把记录通过帖子归类，然后按时间排序，ac了。

就是加了点代码判断是否到新的帖子数据，还有是否已经判断过。

其实还蛮意外的，以为会TLE然而没有，不过要是简单遍历赞数量的话大概就gg了

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

struct Rec
{
    int ts, id;
    bool operator < (const Rec & t)
    {
        if(id == t.id)
            return ts < t.ts;
        return (id < t.id);
    }
} rec[N];

int n, d, k;

int tr[N];
bool st[N];  // 保存处理状态

int lb(int x)
{
    return x & -x;
}

void add(int x)
{
    for(int i = x; i < N; i += lb(i))
        tr[i]++;
}

int query(int x)
{
    if(x <= 0)
        return 0;
    int cnt = 0;
    for(int i = x; i; i -= lb(i))
        cnt += tr[i];
    return cnt;
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);

    int ts, id;

    for(int i = 0; i < n; i++)
        scanf("%d%d", &rec[i].ts, &rec[i].id), rec[i].ts++;

    // 把所有记录按帖子归类
    sort(rec, rec + n);

    // 用来判定是否为同一帖子
    int lst = rec[0].id, cur;
    for(int i = 0; i < n; i++)
    {
        if(st[rec[i].id])
            continue;

        // 不是同一帖子的点赞数据，清空统计数组
        if(lst != rec[i].id)
        {
            memset(tr, 0, sizeof tr);
            lst = rec[i].id;
        }

        cur = rec[i].ts;
        add(cur);

        if(query(cur) - query(cur - d) >= k)
        {
            st[rec[i].id] = true;
            cout << rec[i].id << endl;
            continue;
        }
    }

}

思路三：双指针

来源y总，不过不是很习惯x和y这样粗暴的命名，所以改成题意对应含义了

（感觉思路2的结构体也可以用pair替换掉）

#include <iostream>
#include <algorithm>

using namespace std;

#define ts first
#define id second

typedef pair<int, int> PII;

const int N = 100010;

int n, d, k;
PII rec[N];
int cnt[N];
bool st[N];

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    for(int i = 0; i < n; i++)
        scanf("%d%d", &rec[i].ts, &rec[i].id);

    sort(rec, rec + n);

    for(int i = 0, j = 0; i < n; i++)
    {
        int id = rec[i].id;
        cnt[id]++;

        while(rec[i].ts - rec[j].ts >= d)
        {
            cnt[rec[j].id]--;
            j++;
        }

        if(cnt[id] >= k)
            st[id] = true;
    }

    for(int i = 0; i < N; i++)
        if(st[i])
            cout << i << endl;
}