解题：由乃OI 2018 五彩斑斓的世界

写在前面的扯淡：

分块的总体学习告一段落，这算是分块集中学习的最后一题么；以后当然也可能会写，就是零零散散的题了=。=

在洛谷上搜ynoi发现好像只有这道题和由乃OI 2018 未来日记是分块，久闻由乃OI之大名，就想试着写一写这道题(那道太毒了，写不了)；结果一开始差点被吓跑了，不过最后还是硬着头皮写完了QAQ

“分块最重要的就是常数” — —shadowice1984

好像挺有道理的，分块从诞生之日起就是一个依靠你的决策而决定复杂度的算法(或思想)，它不像什么高级的数据结构每块的写法都是基本固定的，复杂度有着严格的证明— —分块是个相对灵活的算法(所以也说它是一种思想)。举个例子：最简单的那种序列分块基本上复杂度都是$O(\frac{n^2}{size})$，$size$就是你自己决定的块大小，大家可能都知道块大小开$sqrt(n)$(当然这是均值不等式算出来的)，但是有时候可能某个操作的常数非常大，把块大小适当地调整可能会跑的更快......但是当卡常超过一定的地步，算法就又失去了本身的意义和美感......算了我语言表达能力太差了，还是赶快写题解吧=。=

考虑到区间一个个查询修改非常慢，先用并查集把每块里相同的数字连到第一次出现的位置上，然后考虑修改操作$(l,r,v)$：

对于一个最大值$maxx$不超过$2*v$的块，我们直接修改，即把大于$v$而小于最大值的部分的每个数$x$用并查集连到$x-v$

对于一个最大值$maxx$大于$2*v$的块，我们反过来修改，把小于$v$的部分的每个数$x$连到$x+v$，同时在区间上打标记

为什么要这样做？

首先我们发现这两种修改方法本质是一样的

然后我们发现对于第一种修改我们每次动的数是$v$级别的，同时我们把最大值缩小了$v$

而对于第二种修改我们每次动的数是$maxx-v$级别的，在那个限制下其实还是$v$级别的，和上面的效率是一样的(注意我们是根据$maxx$分出两种情况的，这也是用到了分块的思想)

然后均摊复杂度就有保证了，当然你还需要卡常(其实卡常不是很厉害，我就用了烂大街的快读+快输+register跑过去问题不大，还有这题当年在CF上好像因为CF太快+优化+3s实现把暴力放过去了=。=)

 #include<cmath>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,Sq=,M=;

 int a[N],ori[N],blo[N],ll[N],rr[N],aset[N];

 int siz[N],maxx[Sq],laz[Sq],firs[Sq][N];

 int n,m,t1,t2,t3,t4,sqr,cnt;

 inline int read()

 {

     int ret=;

     char ch=getchar();

     while(!isdigit(ch))

         ch=getchar();

     while(isdigit(ch))

         ret=(ret<<)+(ret<<)+(ch^),ch=getchar();

     return ret;

 }

 void write(int x)

 {

     if(x>) write(x/);

     putchar(x%+);

 }

 int finda(int x)

 {

     return (x==aset[x])?x:aset[x]=finda(aset[x]);

 }

 inline void rebuild(int b)//块重构

 {

     register int i;

     for(i=ll[b];i<=rr[b];i++)

     {

         maxx[b]=max(maxx[b],a[i]);

         firs[b][a[i]]=,aset[i]=i,siz[i]=;

     }

     for(i=ll[b];i<=rr[b];i++)//把每个数都并到第一次出现的位置

     {

         int &fir=firs[b][a[i]];

         if(fir) siz[fir]+=siz[i],aset[i]=fir;

         else fir=i,ori[i]=a[i];

     }

 }

 inline void force(int b,int l,int r,int v)//大力重构

 {

     register int i;

     for(i=ll[b];i<=rr[b];i++)

         firs[b][a[i]=ori[finda(i)]]=;

     for(i=l;i<=r;i++)

         if(a[i]-laz[b]>v) a[i]-=v;

     rebuild(b);

 }

 void change(int l,int r,int v)

 {

     register int i,j;

     int b1=blo[l],b2=blo[r];

     if(b1!=b2)

     {

         force(b1,l,rr[b1],v);

         force(b2,ll[b2],r,v);

         for(i=b1+;i<=b2-;i++)

             if(maxx[i]-laz[i]<*v)//当最大值不超过2*v时，正常地修改

             {

                 for(j=laz[i]+v+;j<=maxx[i];j++)

                 {

                     int &pos1=firs[i][j];

                     int &pos2=firs[i][j-v];

                     if(pos1)

                     {

                         if(pos2) siz[pos2]+=siz[pos1],aset[pos1]=pos2;

                         else pos2=pos1,ori[pos2]=j-v; pos1=;

                     }

                 }

                 maxx[i]=min(maxx[i],laz[i]+v);

             }

             else//否则反过来，把其余的数加上这个值并打标记

             {

                 for(j=laz[i]+;j<=laz[i]+v;j++)

                 {

                     int &pos1=firs[i][j];

                     int &pos2=firs[i][j+v];

                     if(pos1)

                     {

                         if(pos2) siz[pos2]+=siz[pos1],aset[pos1]=pos2;

                         else pos2=pos1,ori[pos2]=j+v; pos1=;

                     }

                 }

                 laz[i]+=v;

             }

     }

     else force(b1,l,r,v);

     //修改的理论依据：对于第一种情况最大值在O(v)时间内减小了v，对于第二种情况最大值在O(max-v)减少了max-v，所以最终的均摊复杂度是O(1)的

     //(虽然CF的官方题解这里写的是极差，但我觉得不太对，例如对233,235两个数来说，将大于234的数减去234后极差反而在增大)

 }

 int query(int l,int r,int v)//普通的查询

 {

     register int i;

     int b1=blo[l],b2=blo[r],ret=;

     if(b1!=b2)

     {

         for(i=l;i<=rr[b1];i++)

             ret+=(ori[finda(i)]-laz[b1]==v);

         for(i=ll[b2];i<=r;i++)

             ret+=(ori[finda(i)]-laz[b2]==v);

         for(i=b1+;i<=b2-;i++)

             if(laz[i]+v<=M) ret+=siz[firs[i][laz[i]+v]];

     }

     else

         for(i=l;i<=r;i++)

             ret+=(ori[finda(i)]-laz[b1]==v);

     return ret;

 }

 int main ()

 {

     register int i;

     n=read(),m=read();

     sqr=sqrt(n)+,ll[cnt=]=;

     for(i=;i<=n;i++)

     {

         a[i]=read(),ori[i]=a[i];

         aset[i]=i,blo[i]=(i-)/sqr+;

         maxx[blo[i]]=max(maxx[blo[i]],a[i]);

         if(i%sqr==) rr[cnt++]=i,ll[cnt]=i+;

     }

     rr[cnt]=n;

     for(i=;i<=cnt;i++) rebuild(i);

     for(i=;i<=m;i++)

     {

         t1=read(),t2=read(),t3=read(),t4=read();

         if(t1==) change(t2,t3,t4); else printf("%d\n",query(t2,t3,t4));

     }

     return ;

 }

巴特西

解题：由乃OI 2018 五彩斑斓的世界

最新文章

热门文章