BZOJ4631 : 踩气球
气球
2023-09-11 14:15:04 时间
将所有盒子插入链表,每当一个盒子变空时,从链表里删去它。
查一下它的前驱后继$pre,nxt$,那么$[pre+1,nxt-1]$都是空的。
每次对于$[A,B]$这段都为空,对小朋友按$R$维护线段树,维护区间内$L$的最大值,不断询问$[1,B]$内$L$的最大值,如果$\geq A$则拿出来。
时间复杂度$O(m\log m)$。
#include<cstdio> #include<algorithm> #define N 100010 int n,m,q,i,j,a[N],pre[N],nxt[N],c[N],v[262150],ans; struct P{int l,r;}b[N]; inline bool cmp(const P&a,const P&b){return a.r<b.r;} inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline int merge(int x,int y){return b[x].l>b[y].l?x:y;} void build(int x,int a,int b){ if(a==b){v[x]=a;return;} int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b); v[x]=merge(v[x<<1],v[x<<1|1]); } void change(int x,int a,int b,int c){ if(a==b){v[x]=0;return;} int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c);else change(x<<1|1,mid+1,b,c); v[x]=merge(v[x<<1],v[x<<1|1]); } int ask(int x,int a,int b,int d){ if(b<=d)return v[x]; int mid=(a+b)>>1,t=ask(x<<1,a,mid,d); if(d>mid)t=merge(t,ask(x<<1|1,mid+1,b,d)); return t; } inline void del(int x){ a[x]--; if(a[x])return; int l=pre[x],r=nxt[x]; nxt[l]=r,pre[r]=l; r=c[r-1]; if(!r)return; while(1){ int t=ask(1,1,m,r); if(b[t].l<=l)return; ans++; change(1,1,m,t); } } int main(){ read(n),read(m); for(i=1;i<=n;i++)read(a[i]),pre[i]=i-1,nxt[i]=i+1; for(i=1;i<=m;i++)read(b[i].l),read(b[i].r); std::sort(b+1,b+m+1,cmp); for(i=1;i<=m;i++)if(b[i].r!=b[i-1].r)for(j=b[i-1].r;j<b[i].r;j++)c[j]=i-1; for(i=b[m].r;i<=n;i++)c[i]=m; build(1,1,m); read(q); while(q--)read(i),del((i+ans-1)%n+1),printf("%d\n",ans); return 0; }
相关文章
- CSS动画实例:升空的气球
- 纯CSS实现各类气球泡泡对话框效果
- 【BZOJ4631】踩气球 链表+线段树+堆
- 打爆一排气球arr,你能获得的最大分数是多少?
- 谷歌Facebook为何需要气球、无人机和火箭?
- [计蒜客][结构体]抢气球升级版
- [计蒜客][结构体]抢气球
- 力扣解法汇总1189-“气球” 的最大数量
- 近距离观察谷歌气球:体积硕大将在万米高空提供4G信号
- 气球项目CEO辞职 Alphabet还有啥项目根本不赚钱
- 189、【动态规划】leetcode ——312. 戳气球(C++版本)
- 138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
- 免费素材:气球样式的图标集(PSD, SVG, PNG)
- [LeetCode] 1189. Maximum Number of Balloons 气球的最大数量
- [LeetCode] Minimum Number of Arrows to Burst Balloons 最少数量的箭引爆气球
- [LeetCode] 312. Burst Balloons 打气球游戏
- Java //PP2.17 编写一个applet,画出一些用绳子拴住的各种颜色的气球
- 【bzoj4631】踩气球 线段树
- leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球(中等)
- leetcode 312. Burst Balloons 戳气球(困难)