注意：这是一篇十分劣质的博客，只有题目和简单的几句话，慎用。。。。。。。。。。OVO

分块

入门推荐：

bzoj2957

        这个题有线段树和分块两种做法；

       线段树维护了区间的答案合并的时候维护高度最大值，右区的左子区间进一步讨论对分类讨论；

       分块就对每个块维护一个可看到的上升序列，lower_bound即可；

1 #include
      
        2 #define ll long long 3 #define il inline  4 #define rg register   5 using namespace std; 6 const int N=100010,M=610; 7 int n,m,bl[N],u,t[M],len; 8 double a[N],g[M][M];  9 il int find(int i,double x){10     int l=1,r=t[i]+1;11     while(l
       
        >1;13         if(x
        
         '9')c=gc();39     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();40     return x;41 }42 int main(){43 //    freopen("bzoj2957.in","r",stdin);44 //    freopen("bzoj2957.out","w",stdout);45     n=rd(); m=rd();46     u=550;47     for(rg int i=1;i<=n;i++)bl[i]=(i-1)/u+1;48     len=bl[n];49     for(rg int i=1;i<=n;i++)a[i]=-1;50     for(rg int i=1,x,y;i<=m;i++){51         x=rd(),y=rd();52         a[x]=1.0*y/x;53         update(x);54     }55     return 0;56 }
        
       
      

 

bzoj2141

        交换两个位置，维护逆序对；

        考虑两个位置的影响，对每个块维护一个树状数组；

1 #include
      
        2 #define rg register  3 #define il inline  4 #define ll long long  5 using namespace std; 6 const int N=20010,M=810; 7 int n,m,c[M][N],a[N],sub[N],tot,sz[N],bl[N],u,len; 8 ll ans; 9 il char gc(){10     static char*p1,*p2,s[1000000];11     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);12     return(p1==p2)?EOF:*p1++;13 }14 il int rd(){15     int x=0; char C=gc();16     while(C<'0'||C>'9')C=gc();17     while(C>='0'&&C<='9')x=(x<<1)+(x<<3)+C-'0',C=gc();18     return x;19 }20 il void add(int id,int x,int y){
    for(rg int i=x;i<=tot;i+=i&-i)c[id][i]+=y;}21 il int query(int id,int x){
    int re=0;for(rg int i=x;i;i-=i&-i)re+=c[id][i];return re;}22 void update(int x,int y){23     int tx=a[x],ty=a[y];24     add(bl[x],a[x],-1);25     add(bl[y],a[y],-1);26     swap(a[x],a[y]);27     add(bl[x],a[x],1);28     add(bl[y],a[y],1);29     if(tx>ty)ans--;else if(tx
       
        (--y))return ;31     if(bl[x]==bl[y]){32         for(rg int i=x;i<=y;i++){33             if(tx
        
         a[i])ans--;34             if(ty>a[i])ans++;else if(ty
         
          a[i])ans--;39             if(ty>a[i])ans++;else if(ty
          
           a[i])ans--;43             if(ty>a[i])ans++;else if(ty
           
            y)swap(x,y);74 update(x,y);75 printf("%lld\n",ans); 76 }77 return 0;78 }
           
          
         
        
       
      

 

bzoj3744

       其实也一样，只不过多个套路维护每个块的前缀和就可以快速查询整块了(我没码。。。。。)

 

bzoj2821

      也是套路，维护d[i][j]表示块i到块j的答案，然后再记录出现次数的前缀和，用讨论散块对答案的影响；

1 #include
      
        2 #define rg register  3 #define il inline  4 using namespace std; 5 const int N=100010,M=320; 6 int n,m,q,c[M][N],d[M][M],tmp[N],bl[N],a[N],u,len,st[M],ed[M]; 7 il char gc(){ 8     static char*p1,*p2,s[1000000]; 9     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);10     return(p1==p2)?EOF:*p1++;11 }12 il int rd(){13     int x=0; char ch=gc();14     while(ch<'0'||ch>'9')ch=gc();15     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=gc();16     return x;17 }18 il int query(int x,int y){19     int re=0,num;20     if(bl[x]==bl[y]){21         for(rg int i=x;i<=y;i++){22             if(++tmp[a[i]]==1)continue;23             if(tmp[a[i]]&1)re--;else re++;24         }25         for(rg int i=x;i<=y;i++)tmp[a[i]]=0;26     }else{27         if(bl[x]+1
       
        r)swap(l,r);70         ans=query(l,r);71         printf("%d\n",ans);72     }73     return 0;74 }
       
      

 

bzoj2724

      区间众数，强制在线；     

     不带修和上一个一样；预处理整块出现次数的前缀和，枚举散块

     带修的话修改一下分块大小暴力改，分块大小为$n^{\frac{2}{3}}$，复杂度为$O( n^{ \frac{5}{3} } )$ ;

1 #include
      
        2 #define il inline  3 #define rg register  4 using namespace std; 5 const int N=40010,M=210; 6 int n,m,c[M][N],d[M][M],tmp[N],sub[N],tot,a[N],bl[N]; 7 il char gc(){ 8     static char*p1,*p2,s[1000000]; 9     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);10     return(p1==p2)?EOF:*p1++;11 }12 il int rd(){13     int x=0,f=1; char C=gc();14     while(C<'0'||C>'9'){C=gc();if(C=='-')f=-1;}15     while(C>='0'&&C<='9'){x=x*10+C-'0',C=gc();}16     return x*f;17 }18 int main(){19     freopen("bzoj2724.in","r",stdin);20     freopen("bzoj2724.out","w",stdout);21     n=rd(); m=rd();22     int u = sqrt(n) , len = (n-1)/u+1;23     for(rg int i=1;i<=n;i++)a[i]=sub[i]=rd(),bl[i]=(i-1)/u+1;24     sort(sub+1,sub+n+1);25     tot=unique(sub+1,sub+n+1)-sub-1;26     for(rg int i=1;i<=n;i++)a[i]=lower_bound(sub+1,sub+tot+1,a[i])-sub;27     for(rg int i=1;i<=len;i++){28         int li=u*(i-1)+1,ri=u*i;29         for(rg int j=li;j<=ri;j++)tmp[a[j]]++;30         for(rg int j=1;j<=tot;j++)c[i][j]=tmp[j];31     }32     for(rg int i=1;i<=len;i++){33         int mxv=0,mxd=0;34         for(rg int j=1;j<=tot;j++)tmp[j]=0; 35         for(rg int j=i;j<=len;j++){36             int lj=u*(j-1)+1,rj=u*j;    37             for(rg int k=lj;k<=rj;k++){38                 tmp[a[k]]++;39                 if(tmp[a[k]]>mxv||(tmp[a[k]]==mxv&&a[k]
       
        r)swap(l,r); 51         if(bl[l]==bl[r]){52             ans=0;mx=0;53             for(rg int j=l;j<=r;j++){54                 tmp[a[j]]++;55                 if(tmp[a[j]]>mx||(tmp[a[j]]==mx&&a[j]
        
         mx||(now==mx&&a[j]
         
          mx||(now==mx&&a[j]