题解 | #牛客推荐系统开发之动态特征获取#

这题 无非两种操作

1. 一种对于当前的时间 在这个时间 的时间之前的时间操作要舍去
2. 当插入元素后 如果元素数量大于 要舍去优先级最低的 一 个

如果只有上述两种操作， 很明显一个队列模拟即可
只需按时间依次插入，每新到一个时间， 先while 循环从队头删去第一种情况的
然后插入当前元素， 判断数量是否大于 m 大于就再把队头元素减去即可
答案就是再插入前判断当前队列中是否有要的元素

但是他会有另一种操作， 是 改变某个元素的优先级 那么一个简单的队列就做不了了
因为队列本身无序（相对于要查找的来说）所以不能二分, 并且删去这个元素再放入的操作队列也做不了

但是容易发现，上述的操作只会改变队列中的一个元素的位置， 所以可以采用{链表模拟队列}的方法做到 时间修改, 但是如果快速确定元素的位置呢？
可以采用一个数组来存放id 所对应在链表中的指针, 那么就可以做到 O(1) 的时间查询了

但是就会有另一个问题， 那就是如果这么修改会使得队列中的元素不再按时间排序， 那么第一个操作就不可以了再不停的从队列头部删去了

我的解决办法是在另开一个队列，按时间排序（因为本身就是按时间排序的，所以也就是依次插入即可）那么考虑一下这个队列中的元素，有哪几种状态

• 这个元素本身也在链表模拟的队列中， 那么如果要删去这个元素，同时也要删去链表中对应的位置
• 这个元素本身不在链表队列中， 那么我可以直接删去， 不用管他到底是否满足

那么现在只剩下最后一个问题， 如何看 队列中的元素是否再链表模拟中？
可以开一个 num 数组 记录当前 id 的元素 在队列中出现的次数， 如果 num = 1 同时这个id对应的指针不为 0 则是链表中的元素
num != 1 就不是, 然后num在 队列push 的时候 ++, pop的时候-- 即可

(然后比赛的时候我这里想错了，我想成只要存放 id对应的链表中的指针不是 0 就是在链表队列中. 结果一直wa, 因为有一种情况，是队列中有多个相同id(num > 1)， 此时最后一个才是对应在链表中的，就是num = 1 的时候,....tcl.)

时间复杂度 因为要排序

#include <bits stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n, m;
ll y;
pair <ll, pair <int, int>> a[maxn];
// 用来与 id 对应 cun[x] = y 表示 id 为 x 的指针是 y 如果不存在那么y = 0
int cun[10000005];
struct Node {
    int x;
    int pre = 0, nex = 0;
}que[maxn * 2];
int root, last, idx;
bool answer[maxn];
void del(int idx) {
    que[que[idx].pre].nex = que[idx].nex;
    que[que[idx].nex].pre = que[idx].pre;
    if (idx == last) last = que[last].pre;
}
void add(int idx, int id) {
    if (root == last)  last = idx;
    que[idx].pre = root;
    que[idx].nex = que[root].nex;
    que[idx].x = id;
    que[que[root].nex].pre = idx;
    que[root].nex = idx;
}
queue <int> q;
// 记录 q 中的数量
int num[10000007];
int main()
{
    que[0].pre = que[0].nex = 0;
    cin >> n >> m >> y;
    for (int i = 1; i <= n; ++i) {
        int l; ll r;
        scanf("%d%lld", &l, &r);
        a[i] = {r, {l, i}};
    }
    sort(a + 1, a + n + 1);
    // 记录元素数量
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        ll t = a[i].x;
        while (cnt) {
            int id = q.front();
            if (cun[a[id].y.x] == 0) {
                num[a[id].y.x]--;
                q.pop();
                continue;  
            }
               //这种是残存的没用的 
            if (num[a[id].y.x] > 1) {
                   num[a[id].y.x]--;
                   q.pop();
                   continue;
            }
            if (t - a[id].x < y) break;
            q.pop();
            int opp = cun[a[id].y.x];
            cun[a[id].y.x] = 0;
            del(opp);
            cnt--;
            num[a[id].y.x]--;
        }
        // 判断链表队列中是否有这个元素， 可以通过判断cun数组是否为空
        if (cun[a[i].y.x]) {
            int k = cun[a[i].y.x];
            del(k);
            add(++idx, que[k].x);
            cun[a[i].y.x] = idx;
        } else {
            add(++idx, i);
            q.push(i);
            num[a[i].y.x]++;

            cun[a[i].y.x] = idx;
            cnt++;
            answer[a[i].y.y] = true;
            // 多余的时候从链表中减去
            if (cnt > m) {
                int id = que[last].x;       
                cun[a[id].y.x] = 0;
                del(last);
                cnt--;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (answer[i]) puts("YES");
        else puts("NO");
    }
    return 0;
}

</ll,>