分块

分块

关注
发信
关注(28)粉丝(399)

【二维莫队】【二维分块】bzoj2639 矩形计算

<法一>二维莫队，对n和m分别分块后，对块从上到下从左到右依次编号，询问以左上角所在块编号为第一关键字，以右下角标号为第二关键字排序，转移时非常厉害。

O(q*n*sqrt(n))。

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define N 201

#define M 100001

struct LiSan{int p,v;}t[N*N];

bool operator < (const LiSan &a,const LiSan &b){return a.v<b.v;}

int n,m,nm,zy,a[N][N],b[N*N],num[N][N],id[N][N];

struct ASK{int x1,y1,x2,y2,p;}Q[M];

bool operator < (const ASK &a,const ASK &b)

{return num[a.x1][a.y1]!=num[b.x1][b.y1] ?

num[a.x1][a.y1]<num[b.x1][b.y1] :

id[a.x2][a.y2]<id[b.x2][b.y2];}

void lisan()

{

    scanf("%d%d",&n,&m); nm=n*m;

    for(int i=1;i<=nm;++i)

      {

        scanf("%d",&t[i].v);

        t[i].p=i;

      }

    sort(t+1,t+nm+1);

    b[t[1].p]=++zy;

    for(int i=2;i<=nm;++i)

      {

        if(t[i].v!=t[i-1].v) ++zy;

        b[t[i].p]=zy;

      }

    int pen=0;

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

      for(int j=1;j<=m;++j)

        a[i][j]=b[++pen];

}

void makeblock()

{

    int sun=sqrt(n),sum=sqrt(m);

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

      for(int j=1;j<=m;++j)

        num[i][j]=(i-1)/sun*sum+(j-1)/sum+1;

}

int ans,T[N*N];

bool vis[N][N];

inline void Insert(const int &x,const int &y)

{

    if(!vis[x][y])

      {

        vis[x][y]=1;

        ans+=((T[a[x][y]]++)<<1|1);

      }

}

inline void Delete(const int &x,const int &y)

{

    if(vis[x][y])

      {

        vis[x][y]=0;

        ans-=((--T[a[x][y]])<<1|1);

      }

}

inline void trans(const ASK &a,const ASK &b)

{

    int t=min(a.x1-1,b.x2);

    for(int i=b.x1;i<=t;++i)

      for(int j=b.y1;j<=b.y2;++j)

        Insert(i,j);

    for(int i=max(b.x1,a.x2+1);i<=b.x2;++i)

      for(int j=b.y1;j<=b.y2;++j)

        Insert(i,j);

    t=min(a.y1-1,b.y2);

    for(int j=b.y1;j<=t;++j)

      for(int i=b.x1;i<=b.x2;++i)

        Insert(i,j);

    for(int j=max(b.y1,a.y2+1);j<=b.y2;++j)

      for(int i=b.x1;i<=b.x2;++i)

        Insert(i,j);

    t=min(b.x1-1,a.x2);

    for(int i=a.x1;i<=t;++i)

      for(int j=a.y1;j<=a.y2;++j)

        Delete(i,j);

    for(int i=max(a.x1,b.x2+1);i<=a.x2;++i)

      for(int j=a.y1;j<=a.y2;++j)

        Delete(i,j);

    t=min(b.y1-1,a.y2);

    for(int j=a.y1;j<=t;++j)

      for(int i=a.x1;i<=a.x2;++i)

        Delete(i,j);

    for(int j=max(a.y1,b.y2+1);j<=a.y2;++j)

      for(int i=a.x1;i<=a.x2;++i)

        Delete(i,j);

}

int q,anss[M];

int main()

{

//  freopen("bzoj2639.in","r",stdin);

//  freopen("bzoj2639.out","w",stdout);

    lisan();

    makeblock();

    int pen=0;

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

      for(int j=1;j<=m;++j)

        id[i][j]=++pen;

    scanf("%d", &q);

    for(int i=1;i<=q;++i)

      {

        scanf("%d%d%d%d",&Q[i].x1,&Q[i].y1,&Q[i].x2,&Q[i].y2);

        if(Q[i].x1>Q[i].x2) swap(Q[i].x1,Q[i].x2);

        if(Q[i].y1>Q[i].y2) swap(Q[i].y1,Q[i].y2);

        Q[i].p=i;

      }

    sort(Q+1,Q+1+q);

    for(int i=Q[1].x1;i<=Q[1].x2;++i)

      for(int j=Q[1].y1;j<=Q[1].y2;++j)

        Insert(i,j);

    anss[Q[1].p]=ans;

    for(int i=2;i<=q;++i)

      {

        trans(Q[i-1],Q[i]);

        anss[Q[i].p]=ans;

      }

    for(int i=1;i<=q;++i)

      printf("%d\n",anss[i]);

    return 0;

}

<法二>二维分块，分块在矩阵中的扩展，预处理前缀矩阵每个数出现的次数，以及所有“子矩块”的答案。询问的时候整块的部分直接获取，零散的部分暴力转移。TLE。

复杂度O(n^2+q)*n*sqrt(n)，常数较大。

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int f,C;

inline void R(int &x){

    C=0;f=1;

    for(;C<'0'||C>'9';C=getchar())if(C=='-')f=-1;

    for(x=0;C>='0'&&C<='9';C=getchar())(x*=10)+=(C-'0');

    x*=f;

}

inline void P(int x){

    if(x<10)putchar(x+'0');

    else{P(x/10);putchar(x%10+'0');}

}

#define N 202

#define BN 17

int n,m,nm;

struct Point{int x,y;}num[N][N];

inline bool operator == (const Point &a,const Point &b){return a.x==b.x && a.y==b.y;}

struct LiSan{int p,v;}t[N*N];

inline bool operator < (const LiSan &a,const LiSan &b){return a.v<b.v;}

int b[N*N],a[N][N],zy,szn,szm,ln[BN],rn[BN],lm[BN],rm[BN],sun=1,sum=1;

void makeblock()

{

    szn=sqrt(n);

    for(;sun*szn<n;++sun)

      {

        ln[sun]=rn[sun-1]+1;

        rn[sun]=sun*szn;

      }

    ln[sun]=rn[sun-1]+1;

    rn[sun]=n;

    //

    szm=sqrt(m);

    for(;sum*szm<m;++sum)

      {

        lm[sum]=rm[sum-1]+1;

        rm[sum]=sum*szm;

      }

    lm[sum]=rm[sum-1]+1;

    rm[sum]=m;

    //

    for(int i=1;i<=sun;++i)

      for(int j=1;j<=sum;++j)

        for(int k=ln[i];k<=rn[i];++k)

          for(int l=lm[j];l<=rm[j];++l)

            num[k][l]=(Point){i,j};

}

int anss[BN][BN][BN][BN];

int T[N*N];

int sumv[BN][BN][N*N];

int haha[BN],hehe[BN];

void Init_Sumv()

{

    for(int i=1;i<=sun;++i)

      for(int j=1;j<=sum;++j)

        {

          memcpy(sumv[i][j]+1,sumv[i][j-1]+1,sizeof(int)*zy);

          for(int k=ln[i];k<=rn[i];++k)

            for(int l=lm[j];l<=rm[j];++l)

              ++sumv[i][j][a[k][l]];

        }

    for(int j=1;j<=sum;++j)

      for(int i=1;i<=sun;++i)

        for(int k=1;k<=zy;++k)

          sumv[i][j][k]+=sumv[i-1][j][k];

}

inline int Calc(int X1,int Y1,int X2,int Y2,int v)

{

    if(!(X2>=X1 && Y2>=Y1)) return 0;

//  int a[20][20];

    static int* b=&sumv[0][0][0];

    int *x=b+haha[X2]+hehe[Y2]+v;

    int *y=b+haha[X1-1]+hehe[Y2]+v;

    int *z=b+haha[X2]+hehe[Y1-1]+v;

    int *l=b+haha[X1-1]+hehe[Y1-1]+v;

//  if(*z!=sumv[X2][Y1-1][v])puts("jhsdhe");

//  if(*(sumv+x))!=sumv[X2][Y2][v])puts("BaoJingLa");

    return *x-*y-*z+*l;

}

void Init_Ans()

{

    for(int i=1;i<=sun;++i)

      for(int j=1;j<=sum;++j)

        for(int k=i;k<=sun;++k)

          for(int l=j;l<=sum;++l)

            {

              anss[i][j][k][l]=anss[i][j][k-1][l];

              for(int o=j;o<=l;++o)

                for(int p=ln[k];p<=rn[k];++p)

                  for(int q=lm[o];q<=rm[o];++q)

                    {

                      anss[i][j][k][l]+=((Calc(i,j,k-1,l,a[p][q])+T[a[p][q]])<<1|1);

                      ++T[a[p][q]];

                    }

              for(int o=j;o<=l;++o)

                for(int p=ln[k];p<=rn[k];++p)

                  for(int q=lm[o];q<=rm[o];++q)

                    --T[a[p][q]];

            }

}

int q;

int main()

{

//  freopen("bzoj2639.in","r",stdin);

//  freopen("bzoj2639.out","w",stdout);

    R(n); R(m); nm=n*m;

    for(int i(1);i<BN;i++) haha[i]=haha[i-1]+BN*N*N;

    for(int i(1);i<BN;i++) hehe[i]=hehe[i-1]+N*N;

    for(int i=1;i<=nm;++i)

      {

        R(t[i].v);

        t[i].p=i;

      }

    sort(t+1,t+nm+1);

    b[t[1].p]=++zy;

    for(int i=2;i<=nm;++i)

      {

        if(t[i].v!=t[i-1].v) ++zy;

        b[t[i].p]=zy;

      }

    int pen=0;

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

      for(int j=1;j<=m;++j)

        a[i][j]=b[++pen];

    makeblock();

    Init_Sumv();

    Init_Ans();

    int X1,Y1,X2,Y2;

    R(q);

    for(;q;--q)

      {

        R(X1); R(Y1); R(X2); R(Y2);

        if(X1>X2)

          swap(X1,X2);

        if(Y1>Y2)

          swap(Y1,Y2);

        Point zs=(Point){num[X1][Y1].x+(num[X1][Y1]==num[X1-1][Y1]),

                         num[X1][Y1].y+(num[X1][Y1]==num[X1][Y1-1])};

        Point yx=(Point){num[X2][Y2].x-(num[X2][Y2]==num[X2+1][Y2]),

                         num[X2][Y2].y-(num[X2][Y2]==num[X2][Y2+1])};

        int ans=0;

        if(!(yx.x>=zs.x && yx.y>=zs.y))

          {

            for(int i=X1;i<=X2;++i)

              for(int j=Y1;j<=Y2;++j)

                {

                  ans+=((T[a[i][j]])<<1|1);

                  ++T[a[i][j]];

                }

            for(int i=X1;i<=X2;++i)

              for(int j=Y1;j<=Y2;++j)

                --T[a[i][j]];

          }

        else

          {

            ans=anss[zs.x][zs.y][yx.x][yx.y];

            int TX=ln[zs.x]-1;

            int TY=rm[yx.y];

            for(int i=X1;i<=TX;++i)

              for(int j=Y1;j<=TY;++j)

                {

                  ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1);

                  ++T[a[i][j]];

                }

            int TX2=rn[yx.x];

            int TY2=rm[yx.y]+1;

            for(int i=X1;i<=TX2;++i)

              for(int j=TY2;j<=Y2;++j)

                {

                  ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1);

                  ++T[a[i][j]];

                }

            int TX3=rn[yx.x]+1;

            int TY3=lm[zs.y];

            for(int i=TX3;i<=X2;++i)

              for(int j=TY3;j<=Y2;++j)

                {

                  ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1);

                  ++T[a[i][j]];

                }

            int TX4=ln[zs.x];

            int TY4=lm[zs.y]-1;

            for(int i=TX4;i<=X2;++i)

              for(int j=Y1;j<=TY4;++j)

                {

                  ans+=((T[a[i][j]]+Calc(zs.x,zs.y,yx.x,yx.y,a[i][j]))<<1|1);

                  ++T[a[i][j]];

                }

            for(int i=X1;i<=TX;++i)

              for(int j=Y1;j<=TY;++j)

                --T[a[i][j]];

            for(int i=X1;i<=TX2;++i)

              for(int j=TY2;j<=Y2;++j)

                --T[a[i][j]];

            for(int i=TX3;i<=X2;++i)

              for(int j=TY3;j<=Y2;++j)

                --T[a[i][j]];

            for(int i=TX4;i<=X2;++i)

              for(int j=Y1;j<=TY4;++j)

                --T[a[i][j]];

          }

        P(ans),puts("");

      }

    return 0;

}
05-23 23:32
Powered by LMLPHP ©2025 分块 0.046087