牛客多校第3场 J 思维+树状数组+二分

传送门：https://ac.nowcoder.com/acm/contest/883/J

题意：

给你q个询问，和一个队列容量f

询问有两种操作：

0.访问操作，如果询问的name在队列中存在的话，那么就输出队列中name对应的val值，然后将队列中name对应的元素扔到队列的尾部去，否则就直接将该元素插入到队列的尾部去

1.插入操作，得到队列中对应的name元素的v值为k，查询第k+v个元素的v值是多少

题解：

已知，对于插入操作，我们需要很快的查询对应的name值的val

所以我们考虑map映射，为了解决string过慢的问题，我们将stringhash成一个unsigned long long的值

我们记录有多少个数被插入了，还有每个点的绝对坐标，如果在0操作中 点x被丢弃了，那么我们就对x位置打上标记1，这样，在我们查询第y个操作时，实际上，这个y操作对于的位置就是 查询这个y对应的pos位减去当前位置之前被删掉的数的和加上 v值

我们用tot统计被插入数的数量，因为一开始就是空串，所以tot实际上就代表队列中有多少个数，如果tot>m，我们就丢弃队头的元素

对于每次查询，我们是找当前位置向左的位置，因为我们删除的数实际上只是给打上了一个+1的标记，所以我们需要找到左边真正存在的那个数，这个右端点不太好找，所以我们考虑二分，二分当前位置是否是第r个点

check就直接用二分出来的mid减去mid之前的丢弃的个数，如果这个个数>当前个数，那么就改变二分的上界r，否则改变二分的下界l

然后就可以得到满足真正的pos+1的位置的值的数了

emmm复杂度应该是两个log 被卡map的操作然后有迭代器 实现mp的操作，这样卡过去了 600+ms 海星吧

代码：

#include <set>

#include <map>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#include <assert.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 5e5 + 5;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const double Pi = acos(-1);

const int seed = 1331;

LL quick_pow(LL x, LL y) {

    LL ans = 1;

    while(y) {

        if(y & 1) {

            ans = ans * x % mod;

        } x = x * x % mod;

        y >>= 1;

    } return ans;

}

int lowbit(int x) {

    return x & (-x);

}

int bit[maxn];

void add(int pos, int val) {

    while(pos < maxn) {

        bit[pos] += val;

        pos += lowbit(pos);

    }

}

int query(int pos) {

    int res = 0;

    while(pos) {

        res += bit[pos];

        pos -= lowbit(pos);

    }

    return res;

}

void clear(int pos, int MM) {

    while(pos < MM) {

        bit[pos] = 0;

        pos += lowbit(pos);

    }

}

uLL Hash(char *x) {

    uLL h = 0;

    for(int i = 0; x[i]; i++) {

        h = h * seed + x[i];

    }

    return h;

}

int op;

int v;

int val[maxn];

uLL hname[maxn];

char name[20];

map<uLL, int> mp;

int get_pos(int p, int tot) { //虽然名字是tot，但是要传入index

    int pos = -1;

    int l = 1, r = tot;

    while(r >= l) {

        int mid = (l + r) / 2;

        int num =  mid - query(mid);

        if(num >= p) {

            r = mid - 1;

            pos = mid;

        } else {

            l = mid + 1;

        }

    }

    assert(pos != -1);

    return pos;

}

map<uLL, int>:: iterator iter;

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        mp.clear();

        int m, k;

        scanf("%d%d", &k, &m);

        memset(bit, 0, sizeof(bit));

        int Index = 0;

        int tot = 0;

        for(int i = 1; i <= k; i++) {

            scanf("%d%s%d", &op, name, &v);

            uLL h = Hash(name);

            iter = mp.find(h);

            if(op == 0) {

                if(iter != mp.end()) {

                    int pos = iter->second;

                    printf("%d\n", val[pos]);

                    add(pos, 1);

                    Index++;//charu

                    hname[Index] = h;

                    val[Index] = val[pos];

                    iter->second = Index;

                } else {

                    printf("%d\n", v);

                    tot++;

                    if(tot > m) {

                        tot--;

                        int pos = get_pos(1, Index);

                        add(pos, 1);

                        iter = mp.find(hname[pos]);

                        if(iter != mp.end())mp.erase(iter);

                    }

                    Index++;

                    mp[h] = Index;

                    hname[Index] = h;

                    val[Index] = v;

                }

            } else {

                if(iter == mp.end()) {

                    printf("Invalid\n");

                    continue;

                }

                int vv = iter->second;

                int pos = vv - query(vv - 1);

                pos += v;

                if(pos > tot || pos < 1) {

                    printf("Invalid\n");

                } else {

                    pos = get_pos(pos, Index);

                    printf("%d\n", val[pos]);

                }

            }

        }

    }

    return 0;

}