[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形

比赛时候万人题，呵呵，没想到转换成histogram来做。貌似转化之后暴力都可以，n*m^2，气哭aaaaaaaaaaaaaaaaaaa

然后自己写了单调栈n*m做法，需要注意的是要同时保存一段height的左端点和右端点，因为要求数量的话，用单调栈只保存一个的话会忽略掉中间的“高点”，只保存一个端点就无法正确计算了。。。emm，代码写得时候脑子也很乱，还是需要多写写单调数据结构的题目。

#include
#include
#include
#include
#include
#include
#include
#include

#include

using namespace std;
const int maxn=1e5+5;
typedef long long LL;

int st[200][2],top;
int height[2][105],prel;
vector vp[100005];
LL getit(LL m,LL n){return m*n;}//((m*(m+1))>>1)*((n*(n+1))>>1);}

int main()
{
    int T,n,m,k,x,y,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        cas++;
        memset(height,0,sizeof(height));
        scanf("%d%d%d",&n,&m,&k);
        for (int i=1;i<=n;i++)
            vp[i].clear();
        for (int i=1;i<=k;i++)
        {
            scanf("%d%d",&x,&y);
            vp[x].push_back(y);
        }
        LL ans=0;
        int t=0;
        for (int i=1;i<=n;i++)
        {
            prel=0;
            int flag=0;
            top=-1;
            if(!vp[i].empty())
            {
                sort(vp[i].begin(),vp[i].end());
                flag=1;
            }
            int tp=0,len=vp[i].size();
            for (int j=1;j<=m;j++)
            {

                if(flag&&j==vp[i][tp])
                {
                    prel=j;
                    if(tp<len-1)//error1 tp++; top=-1; height[t^1][j]=0; continue; } height[t^1][j]=height[t][j]+1; while(top>-1&&height[t^1][st[top][0]]>height[t^1][j])
                {
                    top--;
                }
                if(~top)
                    ans+=getit(j-prel,height[t^1][st[0][0]]);
                for (int w=1;w<=top;w++)
                {
                    ans+=getit(j-st[w-1][1],height[t^1][st[w][1]]-height[t^1][st[w-1][1]]);
                }
                if(top==-1||height[t^1][st[top][0]]<=height[t^1][j])
                {
                    if(top==-1)
                    {
                        ans+=getit(height[t^1][j],j-prel);
                        top++;
                        st[top][0]=st[top][1]=j;
                    }
                    else if(height[t^1][st[top][0]]<height[t^1][j])
                    {
                        ans+=getit(j-st[top][1],height[t^1][j]-height[t^1][st[top][1]]);
                        top++;
                        st[top][0]=st[top][1]=j;
                    }
                    else
                    {
                        ans+=height[t^1][j]-height[t^1][st[top][1]];
                        st[top][1]=j;
                    }
                }
            }
            t^=1;
        }
        printf("Case #%d: %lld\n",cas,ans);
    }
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

发表回复 取消回复

发表回复取消回复