题解 P1901 【发射站】

G_A_TS · 2019-04-13 15:38:30 · 题解

发射栈
然而我是分块做的（这种膜你题竟然没有暴力题解???）
分 块 大 法 好
如上，分块是莫队的标配优化之一
题中注意边界，分为左辐射和右辐射跑两遍
如图：
维护每块最大值Fmax[i]
若Fmax[i]>所求，暴力那个块，程序O(2n根号n)
简单的分块可以sqrt(n)每块

#include<bits/stdc++.h>
using namespace std;
int n,sum[2000010],h[1000010],v[1000010],q[1000010],FK,fk[1000010],Fmax[1000010],fs[1000010],fe[1000010],maxn;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&h[i],&v[i]);
    }
    FK=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        fk[i]=(i-1)/FK+1;
    }
    for(int i=1;i<=n;i++)
    {
        int nowFK=fk[i];
        if(h[i]>Fmax[nowFK])
        {
            Fmax[nowFK]=h[i];
        }
        for(int j=nowFK;j>=1;j--)
        {
            if(Fmax[j]>h[i])
            {
                for(int k=min(i,FK*j);k>=FK*(j-1)+1;k--)
                {
                    if(h[k]>h[i])
                    {
                        sum[k]+=v[i];
                        break;
                    }
                }
                break;
            }
        } 
    }
    int nFK=(n-1)/FK+1;
    for(int i=1;i<=n;i++)
    {
        Fmax[i]=0;
    }
    for(int i=n;i>=1;i--)
    {
        int nowFK=fk[i];
        if(i==220)
        {
            nowFK=fk[i];
        }
        if(h[i]>Fmax[nowFK])
        {
            Fmax[nowFK]=h[i];
        }
        for(int j=nowFK;j<=nFK;j++)
        {
            if(Fmax[j]>h[i])
            {
                for(int k=max(i,FK*(j-1)+1);k<=min(n,FK*j);k++)
                {
                    if(h[k]>h[i])
                    {
                        if(sum[k]==249990)
                        {
                            cout<<i<<endl;
                        }
                        sum[k]+=v[i];
                        break;
                    }
                }
                break;
            }
        } 
    }
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,sum[i]);
    }
    cout<<maxn;
}