LRU management

There are multiple cases. The first line of the input contains a single positive integer $\ T$ , indicating the number of cases.

For each case, the first line of the input contains two integers $\ Q$ and $M\ (1 \leq Q, \ M \leq 500000)$ , denoting the number of operations and the capacity of the array. The following $\ Q$ lines each contain an integer $opt \ (0 \le opt \le 1)$ , a string $s \ (1 \leq |s| \leq 10)$ and an integer $\ v$ , separated by single spaces, describing an operation.

If $\ opt = 0$ , then $\ |v| < 10$ , and the operation is that the CPU wants to access a block. If this access misses (which means you can't find a block in the array with the name $\ s$ ), add a block at the end of the array with the name $\ s$ and the data $\ v$ , and the result of the operation is $\ v$ . If this access hits, the result of the operation is the data of the block you found (ignore $\ v$ in this case). Don't forget to move that block to the end of the array.

If $\ opt = 1$ , then $\ v$ will be $\ -1,0$ or $\ 1$ , and the operation is that you should answer ZYB's question. Let $\ k$ be the index of the block with the name $\ s$ in the array. Then the result of this operation is the data of the block with the index $\ k+v$ in the array. If such block doesn't exist, please output ``Invalid'' (without quotation marks) instead.

Note that ZYB's questions (operations of type $\ 1$ ) don't count as access and don't cause the array to be updated.

It is guaranteed that the sum of $\ Q$ over all cases does not exceed $\ 1000000$ , and that $\ s$ only contains digits (i.e. `0' - `9').

C++(g++ 7.5.0) 解法, 执行用时: 908ms, 内存消耗: 17968K, 提交时间: 2022-10-05 14:51:50

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	string s;
	int v;
};
list<node> l;
map<string,list<node>::iterator> mp;
void solve()
{
	int q,m;
	cin>>q>>m;
	mp.clear();l.clear();
	while(q--){
		int op;
		string s;
		int v;
		cin>>op>>s>>v;
		if(!op){
			if(mp.count(s)){
				auto it=mp[s];
				cout<<it->v<<"\n";
				l.push_back({s,it->v});
				l.erase(it);
				mp[s]=prev(l.end());
			}
			else{
				l.push_back({s,v});
				mp[s]=prev(l.end());
				cout<<v<<"\n";
				if(l.size()>m){
					string t=l.front().s;
					l.pop_front();
					mp.erase(t);
				}
			}
		}
		else{
			if(!mp.count(s)){
				cout<<"Invalid\n";
			}
			else{
				auto it=mp[s];
				if(v==-1){
					if(it==l.begin()) cout<<"Invalid\n";
					else cout<<prev(it)->v<<"\n";
				}
				else if(v==0){
					cout<<it->v<<"\n";
				}
				else{
					if(next(it)==l.end()) cout<<"Invalid\n";
					else cout<<next(it)->v<<"\n";
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--){
		solve();
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 714ms, 内存消耗: 20728K, 提交时间: 2019-07-26 15:53:23

#include<bits/stdc++.h>
using namespace std;
struct node{
	string s,v;
	node(){}
	node(string _s,string _v){
		s=_s; v=_v; 
	}
};
int m,q;
list<node> lt;
unordered_map<string,list<node>::iterator> mp;
void solve(string s){
	char v[20];scanf("%s",v);
	if (mp.find(s)!=mp.end()){
		auto it=mp[s];
		strcpy(v,it->v.data());
		lt.erase(it);
	}
	node tmp; tmp.s=s; tmp.v=v;
	lt.emplace_back(tmp);
	mp[s]=prev(lt.end());
	printf("%s\n",v);
	if (lt.size()>m){
		mp.erase(lt.begin()->s);
		lt.pop_front();
	}
}
void solve2(string s){
	int v;scanf("%d",&v);
	if (mp.find(s)==mp.end()){
		printf("Invalid\n");
		return ;
	}
	auto it=mp[s];
	if (it==lt.begin() && v==-1 || next(it)==lt.end() && v==1){
		printf("Invalid\n");
		return ;
	}
	if (v==1) it=next(it);
	else if (v==-1) it=prev(it);
	printf("%s\n",it->v.data());
}
int main(){
	int t,op;scanf("%d",&t);
	char s[30];
	while (t--){
		lt.clear();mp.clear();
		scanf("%d%d",&q,&m);
		while (q--){
			scanf("%d",&op);
			scanf("%s",&s);
			if (op==0) solve(s);
			else solve2(s);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 663ms, 内存消耗: 19620K, 提交时间: 2019-07-25 20:32:17

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct Node{
	string s,v;
	Node() {};
	Node(string s,string v): s(s), v(v){}
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q,m,t;
	cin>>t;
	while(t--){
		list<Node> it;
		unordered_map<string,list<Node>::iterator> mp;
		cin>>q>>m;
		while(q--){
			int op;
			string a,b;
			cin>>op>>a>>b;
			if(op==0){
				if(mp.find(a)!=mp.end()){
					auto lv=mp[a];
					b=lv->v;
					it.erase(lv);
				}
				it.emplace_back(a,b);
				mp[a]=prev(it.end());
				cout<<b<<"\n";
				if(it.size()>m){
					mp.erase(it.begin()->s);
					it.pop_front();
				}
			}else{
				if(mp.find(a)==mp.end()){
					cout<<"Invalid\n";
				}else{
					auto pos=mp[a];
					if((pos==it.begin()&&b=="-1")||(pos==prev(it.end())&&b=="1"))	cout<<"Invalid\n";
					else{
						
						if(b=="1") pos=next(pos);
						if(b=="-1") pos=prev(pos);
						cout<<pos->v<<"\n";
					}
				}
			}
		}
	}
	return 0;
}

详情