BZOJ3642 : [CEOI 2014] Cake-白红宇的个人博客

BZOJ3642 : [CEOI 2014] Cake

发布日期：2021-09-08 01:45:24 浏览次数：34 分类：技术文章

本文共 1998 字，大约阅读时间需要 6 分钟。

rank[i]表示第i美味的是哪块

left[i]表示在k左边美味度为i的是哪块

right[i]表示在k右边美味度为i的是哪块

用3棵线段树分别维护d序列的区间最大值、left序列的区间最大值、right序列的区间最小值

修改：

把第x块改成第y美味

把第y+1到第9美味的全部后移一位

然后把第x块美味度改成最大值+1

然后把第y-1到第1美味的美味度依次改成最大

查询：

设x到k这一段中美味度的最大值为y

求出k另一侧最靠近k的且美味度大于y的位置z

答案为|z-x|-1

时间复杂度为每次操作$O(\log n)$

一开始写了普通线段树被卡常数了TAT（最近怎么都被卡常数）

然后去学了zkw线段树后改成zkw线段树就过了，效果拔群，又快又短。

zkw线段树真是个好东西。

#include
     
      const int N=250010,inf=~0U>>1;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 min(int a,int b){return a
      
       b?a:b;}inline void Max(int&a,int b){if(a
       
        b)a=b;}int n,m,t,q,k,i,x,y,rank[N],d[N],left[5250010],right[5250010],M1,M2,ta_v[530000],tl_v[16777220],tr_v[16777220],que[500010][3];char ch;inline void ta_change(int x,int y){for(ta_v[x+=M1]=y,x>>=1;x;x>>=1)ta_v[x]=max(ta_v[x<<1],ta_v[x<<1|1]);}inline int ta_ask(int x,int y){  int t=-inf;  for(x+=M1-1,y+=M1+1;x^y^1;x>>=1,y>>=1){    if(~x&1)Max(t,ta_v[x^1]);    if(y&1)Max(t,ta_v[y^1]);  }  return t;}inline void tl_change(int x,int y){for(tl_v[x+=M2]=y,x>>=1;x;x>>=1)tl_v[x]=max(tl_v[x<<1],tl_v[x<<1|1]);}inline int tl_ask(int x,int y){  int t=-inf;  for(x+=M2-1,y+=M2+1;x^y^1;x>>=1,y>>=1){    if(~x&1)Max(t,tl_v[x^1]);    if(y&1)Max(t,tl_v[y^1]);  }  return t;}inline void tr_change(int x,int y){for(tr_v[x+=M2]=y,x>>=1;x;x>>=1)tr_v[x]=min(tr_v[x<<1],tr_v[x<<1|1]);}inline int tr_ask(int x,int y){  int t=inf;  for(x+=M2-1,y+=M2+1;x^y^1;x>>=1,y>>=1){    if(~x&1)Min(t,tr_v[x^1]);    if(y&1)Min(t,tr_v[y^1]);  }  return t;}inline void modify(int x,int y){//d[x]改成y  if(x
        
         k)tr_change(d[x],n+1);  ta_change(x,d[x]=y);  if(x
         
          k)tr_change(y,x);}inline void change(int x,int y){//把第x块蛋糕设置成第y美味  int i,j=0;  for(i=1;i<=10;i++)if(rank[i]==x)j=i;  for(i=j?j:10;i>y;i--)rank[i]=rank[i-1];  for(modify(rank[y]=x,++t),i=y-1;i;i--)modify(rank[i],++t);}inline int ask(int x){  if(x==k)return 0;  return x

转载地址：https://blog.csdn.net/weixin_34310369/article/details/85641324 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：9、NFC技术：NDEF文本格式解析

下一篇：Ubuntu下用命令行快速打开各类型文件

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章