CodeForces 916D Jamie and To-do List

题意

你需要维护一个任务列表，有 \(q\) 次操作，每次操作形如以下四种：

set a x：设置任务 \(a\) 的优先级为 \(x\)，如果任务列表中没有 \(a\) 则加进来。
remove a：将任务 \(a\) 移除列表。
query a：求出有多少个任务的优先级比 \(a\) 的小，如果 \(a\) 不在列表里输出 \(-1\)。
undo d：撤销这次操作之前的 \(d\) 个操作。

注意撤销操作可以撤销之前的撤销操作。

\(\texttt{Data Range:}1\leq q\leq 10^5,1\leq x\leq 10^9,1\leq\vert a\vert\leq 15\)

题解

我又是一个不看数据范围的屑 >_<

为什么这场的 D 比 E 还难写啊

好久没写可持久化数据结构了，来写个题解复习一下。

一看到什么撤销操作估计跟可持久化数据结构分不开了。

看到 query 操作其实可以开一棵可持久化权值线段树来维护一下，然后 set 的话需要一个可持久化数组来维护每个任务的优先级。

然后按照题意模拟就得了，因为这题的 \(x\leq 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;

        }

    }

}

巴特西

CodeForces 916D Jamie and To-do List

题意

题解

代码

最新文章

热门文章