LOJ#6284. 数列分块入门 8-白红宇

LOJ#6284. 数列分块入门 8

阅读量：5157 次

发布时间：2019-06-13

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

分块的时候开一个数组标记这个区间是不是都是一样颜色的部分，如果是的话，我后面的查询，更新部分就可以直接整块操作，对于不是不全部都一样颜色的块在具体进到快里面去暴力。

在更新的时候对边上的两个不完整的块，先暴力把这个地方的标记下推下去，然后我在给它重新标记

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define first fi#define second se#define lowbit(x) (x & (-x))typedef unsigned long long int ull;typedef long long int ll;const double pi = 4.0*atan(1.0);const int inf = 0x3f3f3f3f;const int maxn = 100005;const int maxm = 100000;const int mod = 10007;using namespace std;int n, m, tol, T;int block;int a[maxn];int add[maxn];bool vis[maxn];int belong[maxn];void init() { memset(a, 0, sizeof a); memset(add, 0, sizeof add); memset(vis, false, sizeof vis); memset(belong, 0, sizeof belong);}int L(int x) { return (x-1)*block + 1;}int R(int x) { return min(n, x*block);}void update(int l, int r, int c) { if(vis[belong[l]]) { for(int i=L(belong[l]); i<=R(belong[l]); i++) a[i] = add[belong[i]]; vis[belong[l]] = false; } for(int i=l; i<=min(r, R(belong[l])); i++) a[i] = c; if(belong[l] == belong[r]) return ; if(belong[l] != belong[r]) { if(vis[belong[r]]) { for(int i=L(belong[r]); i<=R(belong[r]); i++) a[i] = add[belong[i]]; vis[belong[r]] = false; } for(int i=L(belong[r]); i<=r; i++) a[i] = c; } for(int i=belong[l]+1; i