题解 CF899E Segments Removal
看完题后，可以很快想到，类似于 小熊的果篮，我们可以使用 优先队列 + 链表 完成这道题目。
首先我们预处理出序列里的每一个“块”，并使用链表维护每一个“块”的如下信息：
- 长度，即这一段连续相同数字的个数；
- 数值，即这一个“块”中全部都是这个数；
- 起始位置，为了满足题目要求的先删靠前的“块”这个要求。
接下来，我们用一个 大根堆 维护每一个块，以 长度 为第一关键字，起始位置 为第二关键字。
每次取出堆顶的一个“块”并将其从链表中删除。若删除后，原来与该“块”相邻的两个“块” 数值 相同，则在链表中将后面的那个“块”合并到前面的那个“块”中，并将更新后的前面那个“块”重新入队。
值得注意的是，因为涉及到删除“块”与合并“块”的操作，我们使用一个数组来标记一个“块”是否被删除。
最后“取出堆顶”操作进行的次数即为答案。
#include<bits/stdc++.h>
namespace List{
#define int long long
#define nex(x) link[x][ne]
#define pre(x) link[x][pr]
const int maxn=2e5+5;
template<class T>class list{
private:
T a[maxn];
bool ne,pr;
int tot,h,t,siz;
int link[maxn][2];
inline void swap(T&x,T&y){ T t=y; y=x; x=t; return; }
public:
list(void){ link[h=0][ne=0]=1;
link[t=1][pr=1]=0; tot=1; }
inline void clear(void){
link[h=0][ne=0]=1;
link[t=1][pr=1]=0;
tot=1; return;
}
inline int AddAfter(int k,T x){
nex(++tot)=nex(k); nex(k)=tot;
pre(tot)=k; pre(nex(tot))=tot;
a[tot]=x; ++siz;
return tot;
}
inline int AddBefore(int k,T x){
pre(++tot)=pre(k); pre(k)=tot;
nex(tot)=k; nex(pre(tot))=tot;
a[tot]=x; ++siz;
return tot;
}
inline int AddatHead(T x){ return AddAfter(h,x); }
inline int AddatTail(T x){ return AddBefore(t,x); }
inline void Delete(int k){
nex(pre(k))=nex(k); pre(nex(k))=pre(k); --siz;
return;
}
inline void DeleteAfter(int k){ Delete(nex(k)); }
inline void DeleteBefore(int k){ Delete(pre(k)); }
inline void DeleteatHead(void){ Delete(nex(h)); }
inline void DeleteatTail(void){ Delete(pre(t)); }
inline int GetHead(void){
if(pr) return nex(h);
return nex(t);
}
inline int GetSize(void){ return siz; }
inline bool Empty(void){ return !siz; }
inline int GetTail(void){
if(pr) return t;
return h;
}
inline int GetBack(void){
if(pr) return pre(t);
return pre(h);
}
inline int GetPrev(int k){ return pre(k); }
inline int GetNext(int k){ return nex(k); }
inline T& GetValue(int k){ return a[k]; }
inline void Swap(int x,int y){
swap(a[x],a[y]); return;
}
inline void Reverse(void){ pr^=1; ne^=1; return; }
inline void MakeLoop(void){
nex(pre(t))=nex(h);
pre(nex(h))=pre(t);
return;
}
};
#undef int
#undef nex
#undef pre
} // namespace List
namespace XSC062{
#define int long long
using namespace List;
const int inf=1e18;
const int maxn=2e5+5;
struct _{
int u,d,i; _(){}
_(int U,int D,int I){ u=U; d=D; i=I; }
};
struct __{
int u,d,i,m; __(){}
__(int U,int D,int I,int M){ u=U; d=D; i=I; m=M; }
bool operator<(const __ q)const{
return d==q.d?i>q.i:d<q.d;
}
};
inline void read(int&x){
x=0; bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
if(f) x=-x; return;
}
list<_>li;
int a[maxn];
bool vis[maxn];
int n,ans,f,l,r;
std::priority_queue<__>q;
int main(){
read(n); a[0]=inf;
for(int i=1;i<=n;++i){
read(a[i]);
if(a[i]!=a[i-1])
li.AddatTail(_(0,a[i],i));
++li.GetValue(li.GetBack()).u;
}
for(int i=li.GetHead();i!=li.GetTail();i=li.GetNext(i))
q.push(__(i,li.GetValue(i).u,li.GetValue(i).i,
li.GetValue(i).d));
while(!q.empty()){
int f=q.top().u, t=q.top().i; q.pop();
if(vis[f]) continue; vis[f]=1; ++ans;
// printf("%lld: %lld, %lld\n",f,li.GetValue(f).d,t);
l=li.GetPrev(f); r=li.GetNext(f);
if(f==li.GetHead()||f==li.GetBack()){
li.Delete(f);
continue;
}
li.Delete(f);
if(li.GetValue(l).d==li.GetValue(r).d){
li.GetValue(l).u+=li.GetValue(r).u;
li.Delete(r); vis[r]=1;
q.push(__(l,li.GetValue(l).u,t,li.GetValue(l).d));
}
}
printf("%lld",ans);
return 0;
}
#undef int
} // namespace XSC062
int main(){ XSC062::main(); return 0; }