树状数组的解法
这道题y总用的是双指针算法,原因是判断一个帖子是否为热贴只会用到时间差在d-1内的日志,
将日志按时间排序后,可以不断丢弃在时间差外的日志,从而实现O(N)的时间复杂度
选择用树状数组,原因是数据规模较小,只有1e5条日志,但是id以及ts的数据规模也为1e5,(ts,id)序对的可能情
况有1e10种,远远大于1e5。所以实际上id以及ts的分布是十分稀疏分散的。
对某一个帖子,使用树状数组访问其时间差在d-1内的点赞纪录次数复杂度为O(logN),加上
节点的插入操作,实际上总时间复杂度最大约为 (1e5)*( 2*log(1e5) ),远远小于1e8
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ts second
#define id first
using namespace std;
typedef pair<int,int> PII;
const int N=100005;
PII a[N]; //存储日志
int tr[N]; //树状数组,快速查询某一个时间段的点赞次数
int tm=0; //日志中出现的最大时刻
int lowbit(int x)
{
return x&-x;
}
//x对应本题中的ts
void modify(int x)
{
for(int i=x;i<=tm;i+=lowbit(i))
tr[i]++;
}
//查询[1,x]这一个时间段的点赞次数
int query(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i))
sum+=tr[i];
return sum;
}
int main()
{
int n,d,t;
cin>>n>>d>>t;
//读入数据
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i].ts,&a[i].id);
a[i].ts++; //树状数组下标从1开始
tm=max(tm,a[i].ts);
}
//按ts对n条日志进行排序
sort(a,a+n);
int last=a[0].id; //纪录当前访问的贴子id号
int ans[N],cnt=0; //记录答案,cnt为答案数量
for(int i=0;i<n; )
{
memset(tr,0,sizeof tr); //每一个帖子独立使用tr[],需要初始化
//判断当前帖子是否为热帖
while(i<n && a[i].id==last)
{
int ts=a[i].ts;
modify(ts);
int tmp= ts-d>=0 ? ts-d : 0;
if(query(ts)-query(tmp)>=t) //时间段[tmp+1,ts]内的点赞次数是否可以构成热贴
{
ans[cnt++]=a[i].id;
break;
}
i++;
}
while(i<n && a[i].id==last) i++; //过渡到下一个帖子
last=a[i].id; //更新当前的帖子id号
}
//输出结果
sort(ans,ans+cnt);
for(int i=0;i<cnt;i++)
printf("%d\n",ans[i]);
return 0;
}