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

牛客多校第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;
}
上一篇:转载: 开源整理:Android App新手指引开源控件


下一篇:记一次令人发狂的 bug Eclipse 开不开 tomcat 7.0