題目鏈接：點擊查看

題目大意：模擬實現 $n$ 次操作，每次操作共有四種類型：

$set{a}_i{x}_i$：設置 $a_i$ 的優先級為 $x_i$

$remove{a}_i$：刪除 $a_i$

$query{a}_i$：查詢有多少個事情的優先級小于 $a_i$ 的優先級，如果 $a_i$ 不存在，輸出 $?1$

$undox$：撤銷最后的 $x$ 次操作（不包括本次）

題目分析：看到第四個操作的撤銷應該不難想到使用主席樹去維護吧，因為主席樹最大的特點就是可以訪問歷史版本，不過訓練的時候想了半天總是感覺維護的有點麻煩或者不太可以維護，于是就去做找規律的題直到結束，補題的時候發現其實同時維護兩棵主席樹加一個 $map$ 就足夠了

具體實現如下：

$map$ 用于記錄所有 $a_i$ 的 $id$

第一個主席樹下標是 $id$，權值為 $id$ 的優先級，如果權值為 $0$ 代表該 $id$ 沒有出現

第二個主席樹下標是優先級，權值是相應的 $id$

說到這里應該不難去實現了吧，碼就完事了

關于數組大小，操作涉及到更新操作最多的時候也就是 $set$ 操作每次會增加三條鏈，又因為區間范圍我都設置的是 $[1,inf]$，所以數組范圍最小需要開 $3?32?N$ 大概 $100?N$

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9) write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; struct Node {int l,r,ls,rs,sum; }tree[N*100]; int root1[N],root2[N],cnt,id; map<string,int>mp; void update(int &k,int l,int r,int pos,int val) {tree[++cnt]=tree[k],k=cnt,tree[k].sum+=val,tree[k].l=l,tree[k].r=r;if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) update(tree[k].ls,l,mid,pos,val);else update(tree[k].rs,mid+1,r,pos,val); } int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) return 0;if(tree[k].l>=l&&tree[k].r<=r) return tree[k].sum;return query(tree[k].ls,l,r)+query(tree[k].rs,l,r); } int get_id(string s) {if(!mp.count(s)) mp[s]=++id;return mp[s]; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++){//root1:下標為事情,權值為優先級//root2:下標為優先級,權值為事情的個數root1[i]=root1[i-1],root2[i]=root2[i-1];string s,name;cin>>s;if(s=="set")//將name優先級設置為val{cin>>name;int val,id=get_id(name);read(val);int pre=query(root1[i],id,id);if(pre) update(root1[i],1,inf,id,val-pre),update(root2[i],1,inf,pre,-1),update(root2[i],1,inf,val,1);//如果有這個數else update(root1[i],1,inf,id,val),update(root2[i],1,inf,val,1);//沒有這個數}else if(s=="remove")//刪掉id{cin>>name;int id=get_id(name);int pre=query(root1[i],id,id);if(!pre) continue;//沒出現過update(root1[i],1,inf,id,-pre);update(root2[i],1,inf,pre,-1);}else if(s=="query"){cin>>name;int id=get_id(name);int pre=query(root1[i],id,id);if(!pre) puts("-1");else write(query(root2[i],1,pre-1)),putchar('\n');fflush(stdout);}else if(s=="undo"){int x;read(x);root1[i]=root1[i-x-1],root2[i]=root2[i-x-1];}}return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 916D Jamie and To-do List(主席树+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。