loj#6284. 数列分块入门 8

#6284. 数列分块入门 8

题目：传送门

简要题意：

　　给出一个长为

题解：

　　超级超级超级恶心！！！

　　码农就算了...lazy的运用搞得我几乎要吐：

　　 lazy就看看该块是不是同一数字嘛...不是的话就为-1，是的话就更新成该块的数字

　　然后又到暴力表演了，不停分情况（其实也就三种左右），头尾+中间　　

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define mod 10007
  7 #define qread(x) x=read()
  8 using namespace std;
  9 typedef long long LL;
 10 inline LL read()
 11 {
 12     LL x=0,f=1;char ch;
 13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return f*x;
 16 }
 17 LL n,a[110000],ba[110000];
 18 LL block,pos[110000];
 19 void sol(LL l,LL r,LL c)
 20 {
 21     LL ans=0;
 22     if(pos[l]==pos[r])
 23     {
 24         if(ba[pos[l]]==c)printf("%lld
",r-l+1);
 25         else
 26         {
 27             if(ba[pos[l]]!=-1)
 28                 for(int i=(pos[l]-1)*block+1;i<=pos[l]*block;i++)
 29                     a[i]=ba[pos[l]];
 30             for(int i=l;i<=r;i++){if(a[i]==c)ans++;a[i]=c;}
 31             bool bk=false;
 32             for(int i=(pos[l]-1)*block+1;i<=pos[l]*block;i++)
 33                 if(a[i]!=c){bk=true;break;}
 34             if(bk==false)ba[pos[l]]=c;
 35             else ba[pos[l]]=-1;
 36             printf("%lld
",ans);
 37         }
 38     }
 39     else
 40     {
 41         for(int i=pos[l]+1;i<=pos[r]-1;i++)
 42         {
 43             if(ba[i]==c)ans+=(i*block-((i-1)*block+1)+1);
 44             else if(ba[i]!=-1)ba[i]=c;
 45             else
 46             {
 47                 for(int j=(i-1)*block+1;j<=i*block;j++)
 48                 {
 49                     if(a[j]==c)ans++;
 50                     a[j]=c;
 51                 }
 52                 ba[i]=c;
 53             }
 54             continue;
 55         }
 56         if(ba[pos[l]]==c)ans+=(pos[l]*block-l+1);
 57         else 
 58         {
 59             if(ba[pos[l]]!=-1)
 60                 for(int i=(pos[l]-1)*block+1;i<=pos[l]*block;i++)
 61                     a[i]=ba[pos[l]];
 62             for(int i=l;i<=pos[l]*block;i++)
 63             {
 64                 if(a[i]==c)ans++;
 65                 a[i]=c;
 66             }
 67             bool bk=false;
 68             for(int i=(pos[l]-1)*block+1;i<=pos[l]*block;i++)
 69                 if(a[i]!=c){bk=true;break;}
 70             if(bk==false)ba[pos[l]]=c;
 71             else ba[pos[l]]=-1;
 72         }
 73         if(ba[pos[r]]==c)ans+=(r-((pos[r]-1)*block+1)+1);
 74         else 
 75         {
 76             if(ba[pos[r]]!=-1)
 77                 for(int i=(pos[r]-1)*block+1;i<=pos[r]*block;i++)
 78                     a[i]=ba[pos[r]];
 79             for(int i=(pos[r]-1)*block+1;i<=r;i++)
 80             {
 81                 if(a[i]==c)ans++;
 82                 a[i]=c;
 83             }
 84             bool bk=false;
 85             for(int i=(pos[r]-1)*block+1;i<=pos[r]*block;i++)
 86                 if(a[i]!=c){bk=true;break;}
 87             if(bk==false)ba[pos[r]]=c;
 88             else ba[pos[r]]=-1;
 89         }
 90         printf("%lld
",ans);
 91     }
 92 }
 93 int main()
 94 {
 95     qread(n);for(int i=1;i<=n;i++)qread(a[i]);
 96     block=sqrt(n);
 97     for(int i=1;i<=n;i++)
 98     {    
 99         pos[i]=(i-1)/block+1;
100     }
101     memset(ba,-1,sizeof(ba));
102     for(int i=1;i<=n;i++)
103     {
104         LL l,r,c;qread(l);qread(r);qread(c);
105         sol(l,r,c);
106     }
107     return 0;
108 }