题意
你需要维护一个任务列表，有 (q) 次操作，每次操作形如以下四种：
-
set a x：设置任务 (a) 的优先级为 (x)，如果任务列表中没有 (a) 则加进来。 -
remove a：将任务 (a) 移除列表。 -
query a：求出有多少个任务的优先级比 (a) 的小，如果 (a) 不在列表里输出 (-1)。 -
undo d：撤销这次操作之前的 (d) 个操作。
注意撤销操作可以撤销之前的撤销操作。
( exttt{Data Range:}1leq qleq 10^5,1leq xleq 10^9,1leqvert avertleq 15)
题解
我又是一个不看数据范围的屑 >_<
为什么这场的 D 比 E 还难写啊
好久没写可持久化数据结构了，来写个题解复习一下。
一看到什么撤销操作估计跟可持久化数据结构分不开了。
看到 query 操作其实可以开一棵可持久化权值线段树来维护一下，然后 set 的话需要一个可持久化数组来维护每个任务的优先级。
然后按照题意模拟就得了，因为这题的 (xleq 10^9) 所以不写结构体式线段树可以免去建树的空间开销。
注意一下空间问题即可通过，这里可能要根据数据范围估算一下空间开销。
代码
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51;
map<string,ll>mp;
ll n,totn,totid,x,id,p,limit=1e9;
string op,str;
ll rt[MAXN<<2],rt2[MAXN<<2],sm[MAXN<<6],ls[MAXN<<6],rs[MAXN<<6];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline ll getId(string s)
{
return mp.find(s)==mp.end()?mp[s]=++totid:mp[s];
}
inline void update(ll node)
{
sm[node]=sm[ls[node]]+sm[rs[node]];
}
inline ll add(ll l,ll r,ll pos,ll val,ll node)
{
ll cur=++totn;
ls[cur]=ls[node],rs[cur]=rs[node];
if(l==r)
{
return sm[cur]=sm[node]+val,cur;
}
ll mid=(l+r)>>1;
if(pos<=mid)
{
ls[cur]=add(l,mid,pos,val,ls[node]);
}
else
{
rs[cur]=add(mid+1,r,pos,val,rs[node]);
}
return update(cur),cur;
}
inline ll query(ll l,ll r,ll ql,ll qr,ll node)
{
if(ql<=l&&qr>=r)
{
return sm[node];
}
ll mid=(l+r)>>1,res=0;
res+=ql<=mid?query(l,mid,ql,qr,ls[node]):0;
res+=qr>mid?query(mid+1,r,ql,qr,rs[node]):0;
return res;
}
int main()
{
n=read();
for(register int i=1;i<=n;i++)
{
cin>>op,rt[i]=rt[i-1],rt2[i]=rt2[i-1];
if(op=="set")
{
cin>>str,x=read(),id=getId(str),p=query(1,limit,id,id,rt2[i]);
p?rt[i]=add(1,limit,p,-1,rt[i]):1;
rt[i]=add(1,limit,x,1,rt[i]),rt2[i]=add(1,limit,id,x-p,rt2[i]);
}
if(op=="remove")
{
cin>>str,id=getId(str),p=query(1,limit,id,id,rt2[i]);
p?rt[i]=add(1,limit,p,-1,rt[i]):1,rt2[i]=add(1,limit,id,-p,rt2[i]);
}
if(op=="undo")
{
x=read(),rt[i]=rt[i-x-1],rt2[i]=rt2[i-x-1];
}
if(op=="query")
{
cin>>str,id=getId(str),p=query(1,limit,id,id,rt2[i]);
cout<<(p==0||p==1?p-1:query(1,limit,1,p-1,rt[i]))<<endl;
}
}
}