FZU 2225 小茗的魔法阵 扫描线+树状数组

这个题和一个CF上的找"Z"的题差不多，都是扫描线+树状数组

从右上角的主对角线开始扫描，一直扫到左下角，每次更新，右延伸等于该扫描线的点，注意在其所在的树状数组更新就好了

时间复杂度O（n^2logn)

#include <stdio.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <string.h>

#include <string>

using namespace std;

typedef long long LL;

const LL mod=1e8+;

const int N=1e3+;

int c[][N],n,m;

char s[N][N];

int r[N][N],xl[N][N],xr[N][N];

struct Point

{

    int x,y;

};

vector<Point>g[];

void add(int pos,int x)

{

    for(int i=x; i<=m; i+=i&(-i))

        ++c[pos][i];

}

int sum(int pos,int x)

{

    int ans=;

    if(x==)return ;

    for(int i=x; i>; i-=i&(-i))

        ans+=c[pos][i];

    return ans;

}

int main()

{

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=; i<=n+m; ++i)g[i].clear();

        for(int i=; i<=n; ++i)scanf("%s",s[i]+);

        memset(xl,,sizeof(xl));

        memset(xr,,sizeof(xr));

        memset(r,,sizeof(r));

        memset(c,,sizeof(c));

        for(int j=m; j>; --j)

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

                if(s[i][j]=='x')r[i][j]=r[i][j+]+;

        for(int i=n; i>; --i)

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

                if(s[i][j]=='x')xl[i][j]=xl[i+][j-]+,xr[i][j]=xr[i+][j+]+;

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

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

                if(s[i][j]=='x')

                {

                    int x=i,y=j+r[i][j]-;

                    if(x<y)y-=(x-),x=;

                    else x-=(y-),y=;

                    Point tmp;

                    tmp.x=i,tmp.y=j;

                    int id;

                    if(x==)id=y;

                    else id=m+x;

                    g[id].push_back(tmp);

                }

        int res=;

        for(int i=m; i>=; --i)

        {

            for(int j=; j<g[i].size(); ++j)

            {

                int pos=g[i][j].x+g[i][j].y;

                add(pos,g[i][j].y);

            }

            for(int x=,y=i; x<=n&&y<=m; ++x,++y)

            {

                if(s[x][y]!='x')continue;

                int l=min(xl[x][y],xr[x][y]);

                res+=sum(x+y,y)-sum(x+y,y-l);

            }

        }

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

        {

            for(int j=; j<g[m+i].size(); ++j)

            {

                int pos=g[i+m][j].x+g[i+m][j].y;

                add(pos,g[i+m][j].y);

            }

            for(int x=i,y=; x<=n&&y<=m; ++x,++y)

            {

                if(s[x][y]!='x')continue;

                int l=min(xl[x][y],xr[x][y]);

                res+=sum(x+y,y)-sum(x+y,y-l);

            }

        }

        printf("Case #%d: %d\n",++cas,res);

    }

    return ;

}

FZU 2225 小茗的魔法阵 扫描线+树状数组的相关教程结束。