跳到主要内容

祭坛

· 阅读需 7 分钟

0.随便唠唠​

没有想到这个题会成为我接触树套树的契机，但是这也是真的"思维不够码量来凑"了

别人的写法怎么想到二分的啊QAQ，我只能堆一个史山了

1.思维转化​

下文我会把"答案"默认为是指"祭坛最多可以位于多少个结界的中心"，"次数"指"结界数最多的方案"

首先我们可以想到对于一个没有水晶柱点它的贡献就是四个方向上水晶柱数量的最小值

那么如果这是个一维问题我们就可以随便乱cao过去了对吧，我们不如先考虑尽量线性完成一维的问题

我就把每一列(竖起来的)的贡献来考虑线性的做，现在需要处理的就是行的信息了

我们可以通过看一下图来思考我们需要维护什么

如果我们看图上红色的这两个点之间构成的段之间能得到的最大答案，那么我们首先是可以处理出上下水晶柱数量的最小值的

那么我们就要在蓝色框住的区间内处理每一行的左右水晶柱数量的最小值，这个其实也是可以线性去修改的，每次我们处理完一列后是可以一并更新这个信息的

那么我们线段树查询这个区间内能构成最大答案的行的数量就可以了

2.为什么是树套树​

这个东西我最开始想的是主席树去做的

但是有一个问题，我们每一次处理单点改之后后面的版本的树不能及时更新到新状态，但是要暴力更新就是O(n)O(n)的了

这就是为什么要在外层套一个树状数组，其实就是相当于完成O(logn)O(logn)计算前缀和的功能了

所以我们的时间复杂度是O(nlog2n)O(nlog^2n)

3.代码​

因为懒得算空间就直接写vectorvector了

代码里有一些注释应该可以帮助理解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define QAQ return 

const int N=1e5+10;

//值域线段树来记录每行左右水晶柱的最小值
struct segment_tree
{
    struct NODE
    {
        int ls, rs, val;

        NODE() : ls( 0 ), rs( 0 ), val( 0 ){}
    };

    //纯粹懒得算空间了
    vector< NODE > tree;

    segment_tree(){ tree.emplace_back(); }

    inline int newNODE() 
    { tree.emplace_back();
      QAQ tree.size()-1;}

    //单点修改
    inline int change( int p,int l,int r,int pos,int x )
    {
        if( !p ) p=newNODE();
        tree[p].val+=x;
        if( l == r ) QAQ p;
        int mid =l+r>>1;
        // if( mid >= pos ) tree[p].ls=change( tree[p].ls,l,mid,pos,x );
        // if( mid <  pos ) tree[p].rs=change( tree[p].rs,mid+1,r,pos,x );
        //什么tmd叫做vector动态扩容导致上面这个写法爆炸了
        int son;
        if( mid >= pos ) son=change( tree[p].ls,l,mid,pos,x ),   tree[p].ls=son;
        if( mid <  pos ) son=change( tree[p].rs,mid+1,r,pos,x ), tree[p].rs=son;
        QAQ p;
    }

    //查询区间[ql,qr]的和
    inline int query1( int p,int l,int r,int ql,int qr )
    {
        if( !p ||  ql > r || qr < l ) QAQ 0;
        if( ql <= l && r <= qr ) QAQ tree[p].val;
        int mid=l+r>>1;
        int ans=0;
        if( mid >= ql ) ans+=query1( tree[p].ls,l,mid,ql,qr );
        if( mid <  qr ) ans+=query1( tree[p].rs,mid+1,r,ql,qr );
        QAQ ans;
    }

    //二分权值线段树找最大值
    inline int query2( const vector< int > &pr,const vector< int > &pl,int l,int r )
    {
        if( l == r ) QAQ l;
        int mid=l+r>>1;
        int right=0;
        for( auto &p:pr ) if( p ) right+=tree[tree[p].rs].val;
        for( auto &p:pl ) if( p ) right-=tree[tree[p].rs].val;
        vector< int > nr; nr.reserve( pr.size() );
        vector< int > nl; nl.reserve( pl.size() ); 
        if( right > 0 )
        {
            for( auto &p:pr ) nr.push_back( p ? tree[p].rs : 0 );
            for( auto &p:pl ) nl.push_back( p ? tree[p].rs : 0 );
            QAQ query2( nr,nl,mid+1,r );
        }
        else
        {
            for( auto &p:pr ) nr.push_back( p ? tree[p].ls : 0 );
            for( auto &p:pl ) nl.push_back( p ? tree[p].ls : 0 );
            QAQ query2( nr,nl,l,mid );
        }
    }

};

struct binary
{
    int n;
    vector< int > root, val;
    segment_tree st;

    binary( int n ):n( n ), root( n+1 ), val( n+1 ){}

    inline int lowbit( int x ){ QAQ x&-x; }

    //把位置 x 变成 y  
    inline void add( int x,int y )
    {
        int pre=val[x], nxt=y;
        if( pre == nxt ) QAQ;
        val[x]=nxt;
        for( ;x<=n;x+=lowbit( x ) )
        {
            if( pre ) root[x]=st.change( root[x],1,n,pre,-1 );
            if( nxt ) root[x]=st.change( root[x],1,n,nxt, 1 );
        }
    }

    //查询位置 [1,x] 中值在 [l,r] 的数的个数
    inline int query1( int x,int l,int r )
    {
        if( x <= 0 || l > r ) QAQ 0;
        int ans=0;
        for( x=min( x,n );x;x-=lowbit( x ) ) ans+=st.query1( root[x],1,n,l,r );
        QAQ ans;
    }

    inline int query2( int l,int r,int vl,int vr )
    {
        l=max( l,1 ); r=min( r,n );
        if( l > r || vl > vr ) QAQ 0;
        QAQ query1( r,vl,vr )-query1( l-1,vl,vr );
    }

    //查询区间最大值
    inline int query3( int l,int r )
    {
        l=max( l,1 ); r=min( r,n );
        if( l > r ) QAQ 0;
        vector< int > pr, pl;
        for(      ;r;r-=lowbit( r ) ) pr.push_back( root[r] );
        for( l=l-1;l;l-=lowbit( l ) ) pl.push_back( root[l] );
        int sum=0;
        for( auto &p:pr ) if( p ) sum+=st.tree[p].val;
        for( auto &p:pl ) if( p ) sum-=st.tree[p].val;
        if( !sum ) QAQ 0;
        QAQ st.query2( pr,pl,1,n );
    }
    
};

//记录每一行左右分别有多少点
int rp[N], lp[N];
//记录每一列所以点的坐标
vector< int > col[N];

int main()
{
    // freopen( "txt.in","r",stdin );
    // freopen( "txt.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ); cout.tie( nullptr );
    int n;
    cin>>n; n++;
    binary bit( n );
    for( int i=1, x, y;i<n;i++ )
        //由于树状数组的缘故，我们尽量不要出现 0 下标
        cin>>x>>y, x++, y++,
        col[x].push_back( y ), rp[y]++;
    
    int ans=0;
    ll tim=0;
    //枚举每一列
    for( int x=1;x<=n;x++ )
    {
        //添加哨兵便于处理最低点下面和最高点上面两个部分
        col[x].push_back( -1 );
        col[x].push_back( n+1 );
        sort( col[x].begin(),col[x].end() );
        //正在非哨兵点的数量
        int all=col[x].size()-2;
        //枚举每一个中间段
        for( int i=0;i+1<col[x].size();i++ )
        {
            int down=col[x][i], up=col[x][i+1];
            if( down+1 > up-1 ) continue;//即两点相邻
            //寻找区间最大值，主要是为了比较计算最大能得到的答案
            int maxRow=bit.query3( down+1,up-1 );
            //竖列上产生的贡献
            int maxCol=min( i,all-i );
            //计算区间能得到的最大答案
            int newans=min( maxRow,maxCol );
            //计算能得到这个最大答案的点的个数
            //这个区间的行里面所有贡献比 newans 大的都可以选
            int newtim=bit.query2( down+1,up-1,newans,n );
            //更新答案
            if( newans > ans )       ans=newans, tim=newtim;
            else if( newans == ans ) tim+=newtim;
        }
        //维护我们这个列上的权值线段树的状态
        for( int i=1, y;i<=all;i++ )
            y=col[x][i], lp[y]++, rp[y]--,
            bit.add( y,min( lp[y],rp[y] ) );
    }
    if( ans ) cout<<ans<<"\n"<<tim;
    //虽然但是，我还是觉得这种情况所有数都是可以选的
    else      cout<<"0\n0"; 
    QWQ
}