J. Jewel Grab

Tartarus
_Wallace_

---

轉化詢問：對于一個詢問 [s,k]，找到一個最長的區間 [s,t]，滿足區間中出現次數超過一次的元素，的出現次數減一，的和，不超過 k。

對于該區間[s,t] 區間數顏色：也就是每種顏色只算一個權值求最大和（顯然每種顏色都取最大的權值）于是有下面轉化：對于所有區間中出現次數超過一次的元素，找出其中權值最大的求和；對其他的元素（僅僅出現一次）直接求和。計算最終結果。

---

區間數顏色顯然要維護一個pre[x]數組表示前一個出現c[x]的位置在哪？

首先我們考慮如何找到區間的端點t，也就是找到[s,t]這個區間。由于k非常小，考慮一次只忽略一個寶石，也就是每次找到第一個 pre[x]>s 的 x 即可，那么由于pre[x]和x都在所考慮區間內部，于是就需要多一次忽略。

顯然c[x]就是出現次數超過一次的元素 于是只需要記錄mc[c[x]]每次選擇最大的。而對于[cur,x)這段區間都是其他的元素（僅僅出現一次）直接區間求和即可計算貢獻。

---

考慮如何修改？

每當修改一個位置的顏色最多會有3個位置的pre[]發生改變：

• 該位置pre一定改變
• 原顏色后面位置的pre（可能）改變
• 新顏色后面位置的pre（可能）改變

可以考慮用一個雙鏈表pre[],nxt[]維護一下。詳細參考代碼，代碼都是抄第一篇博客的。

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=200010;int n,m; int pre[N],last[N],nxt[N]; int c[N];ll v[N],mc[N]; set<int> cp[N]; void prework() {memset(last,-1,sizeof last);for(int i=n;i>=1;i--){nxt[i]=last[c[i]];last[c[i]]=i;}memset(last,-1,sizeof last);for(int i=1;i<=n;i++) {pre[i]=last[c[i]];last[c[i]]=i;cp[c[i]].insert(i);} } struct node {int l,r;int v;ll s; }t[N<<2]; void pushup(int u) {t[u].v=max(t[u<<1].v,t[u<<1|1].v);t[u].s=t[u<<1].s+t[u<<1|1].s; } void build(int u,int l,int r) {t[u]={l,r};if(l==r){t[u].v=pre[l];t[u].s=v[l];return;}int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u); } void modify(int u,int p) {if(t[u].l==t[u].r) {t[u].v=pre[p];t[u].s=v[p];return;}int mid=t[u].l+t[u].r>>1;if(p<=mid) modify(u<<1,p);else modify(u<<1|1,p);pushup(u); } ll query(int u,int l,int r) {if(l<=t[u].l&&t[u].r<=r) return t[u].s;int mid=t[u].l+t[u].r>>1;ll v=0;if(l<=mid) v+=query(u<<1,l,r);if(r>mid) v+=query(u<<1|1,l,r);return v; } int find(int u,int s,int p) {if(t[u].l==t[u].r) return t[u].l;int mid=t[u].l+t[u].r>>1;int pos=-1;if(t[u<<1].v>=s&&p<=mid) pos=find(u<<1,s,p);if(pos!=-1) return pos;if(t[u<<1|1].v>=s)pos=find(u<<1|1,s,p);return pos; } int main() {n=rd(),m=rd();for(int i=1;i<=n;i++) c[i]=rd(),v[i]=rd();prework();build(1,1,n);while(m--){int op=rd();if(op==1){int x=rd(),c0=rd(),v0=rd();cp[c[x]].erase(x);// 最后一次出現的c[x]的位置if(last[c[x]]==x) last[c[x]]=pre[x];v[x]=v0;c[x]=c0;// 刪除的修改// 鏈表的一些刪除操作if(nxt[x]!=-1) {if(pre[x]!=-1) {nxt[pre[x]]=nxt[x];pre[nxt[x]]=pre[x];modify(1,nxt[x]);// nxt[x]的pre[]發生改變需要維護}else{pre[nxt[x]]=-1;modify(1,nxt[x]);}}else{if(pre[x]!=-1) nxt[pre[x]]=-1;}// 插入的修改int pos;set<int>::iterator it;it=cp[c0].lower_bound(x);// 插入在末尾if(it==cp[c0].end()){nxt[x]=-1;pre[x]=last[c0];if(pre[x]!=-1) nxt[pre[x]]=x;modify(1,x);}else{pos=*it;if(pre[pos]!=-1) //插入不在開頭{nxt[pre[pos]]=x;pre[x]=pre[pos];modify(1,x);}// 插入在開頭else{pre[x]=-1;modify(1,x);}nxt[x]=pos;pre[pos]=x;modify(1,pos);}cp[c0].insert(x);last[c0]=max(last[c0],x);}else{int s=rd(),k=rd();vector<int> col;int cur=s;ll ans=0;for(int j=0;j<=k&&cur<=n;j++){int pos=find(1,s,cur);if(pos==-1) {ans+=query(1,cur,n);break;}col.push_back(c[pos]);if(j<k){// 出現一次直接選if(mc[c[pos]]==0) mc[c[pos]]=v[pre[pos]];// 出現第二次考慮與第一次出現的比較if(v[pos]>mc[c[pos]]){ans-=mc[c[pos]];ans+=v[pos];mc[c[pos]]=v[pos];}}ans+=query(1,cur,pos-1);// [cur,pos-1]都是第一次出現cur=pos+1;}printf("%lld\n",ans);for(int u:col) mc[u]=0;}}return 0; }

太難了吧。。
要加油哦~

總結

以上是生活随笔為你收集整理的The 2020 ICPC Asia Macau Regional Contest J. Jewel Grab（数颜色+链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

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