【题目】E. Segments Removal
【题意】给定n个数字&＃xff0c;每次操作删除最长的连续相同数字&＃xff08;等长删最左&＃xff09;&＃xff0c;求全部删完的最少次数。n<&＃61;2*10^6&＃xff0c;1<&＃61;ai<&＃61;10^9。
【算法】并查集&＃43;堆
【题解】将序列的相同数字段压缩&＃xff0c;全部插入堆。那么每次操作删除堆顶&＃xff0c;并尝试合并堆顶的前驱和后继&＃xff0c;能合并就重新插入堆中。
在支持删除的序列中找前驱和后继&＃xff0c;是经典的并查集实现。
具体而言&＃xff0c;fa[i]表示 i 点左边&＃xff08;含自身&＃xff09;最近的未被删除的点&＃xff0c;即把删除了的点全部并入左侧第一个未被删除的点&＃xff0c;那么删除点x后fa[x]&＃61;find(fa[x]-1)。
前驱是find(fa[x]-1)&＃xff0c;后继只需要记录r[x]表示x点代表区间的最右端点&＃xff0c;每次合并是&＃xff1a;fa[y]&＃61;x,r[x]&＃61;r[y]。
如果能合并就重新插入堆中&＃xff0c;容易发现堆中废弃的元素一定比新插入的更晚访问&＃xff0c;所以废弃元素访问到就会是被删除的现象&＃xff0c;一个元素被删除表现为find(x) ≠ x。
注意&＃xff1a;删除的时候记得更新r[]。
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#define ll long long
#define lowbit(x) x&-x
using namespace std;
int read(){char c;int s&＃61;0,t&＃61;1;while(!isdigit(c&＃61;getchar()))if(c&＃61;&＃61;&＃39;-&＃39;)t&＃61;-1;do{s&＃61;s*10&＃43;c-&＃39;0&＃39;;}while(isdigit(c&＃61;getchar()));return s*t;
}
int min(int a,int b){return a
int max(int a,int b){return a
int ab(int x){return x>0?x:-x;}
//int MO(int x){return x>&＃61;MOD?x-MOD:x;}
//void insert(int u,int v){tot&＃43;&＃43;;e[tot].v&＃61;v;e[tot].from&＃61;first[u];first[u]&＃61;tot;}
/*------------------------------------------------------------*/
const int inf&＃61;0x3f3f3f3f,maxn&＃61;200010;int n,fa[maxn],a[maxn],tot,r[maxn];
struct cyc{int id,ans,number,l;bool operator <(const cyc &a)const{return ans
}b[maxn];
priority_queue
int find(int x){return fa[x]&＃61;&＃61;x?x:fa[x]&＃61;find(fa[x]);}
int main(){n&＃61;read();int x&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;read();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){x&＃43;&＃43;;if(a[i]!&＃61;a[i&＃43;1]){b[&＃43;&＃43;tot]&＃61;(cyc){tot,x,a[i],i};x&＃61;0;}}n&＃61;tot;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)fa[i]&＃61;i,r[i]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)q.push(b[i]);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cyc x&＃61;q.top();q.pop();while(find(x.id)!&＃61;x.id&&!q.empty())x&＃61;q.top(),q.pop();if(q.empty()){if(find(x.id)!&＃61;x.id)printf("%d",i-1);else printf("%d",i);return 0;}//printf("%d %d %d %d\n",x.id,x.ans,x.number,x.l);int f&＃61;find(x.id);fa[f]&＃61;find(f-1);r[fa[f]]&＃61;r[f];int pre&＃61;find(f-1),suc&＃61;find(r[f]&＃43;1);if(pre&＃61;&＃61;0||suc&＃61;&＃61;0||b[pre].number!&＃61;b[suc].number)continue;fa[suc]&＃61;pre;b[pre].ans&＃43;&＃61;b[suc].ans;r[pre]&＃61;r[suc];q.push(b[pre]);}return 0;
}
京公网安备 11010802041100号