题解 P4729 【[HNOI2009]积木游戏】

bzy · 2020-06-06 22:39:23 · 题解

这大概是全网唯一靠谱的题解了。

写在纸上，字很丑，先凑合一下。

附 C++ 源代码

#include<bits/stdc++.h>
using namespace std;

int n, flag; 

int max( int a, int b, int c )
  { return max( a, max( b, c ) ); }

int max( int a, int b, int c, int d )
  { return max( a, max( b, c, d ) ); }

bool cross( int a, int b, int x, int y )
  { return max( a, x ) <= min(b, y); } 

namespace SGT{
    #define ls ( x << 1 )
    #define rs ( ls | 1 )
    #define mid ( ( l[x] + r[x] ) >> 1 )
    #define Lrange ls, L, min( mid, R )
    #define Rrange rs, max( mid + 1, L ), R
    int l [100005 << 2];
    int r [100005 << 2];
    int mx[100005 << 2];
    int mk[100005 << 2];

    void push_up( int x ) { mx[x] = max( mx[ls], mx[rs] ); }

    void push_down( int x )
      { mk[ls] = max( mk[ls], mk[x]);
        mk[rs] = max( mk[rs], mk[x]);
        if( mx[ls] < mk[ls] ) mx[ls] = mk[ls];
        if( mx[rs] < mk[rs] ) mx[rs] = mk[rs]; }

    void build( int x, int L, int R ) 
      { l[x] = L, r[x] = R;
        if( L == R ) return ;
        build( Lrange ); build( Rrange ); }

    void modify( int x, int L, int R, int V ) 
      { if( l[x] == L and r[x] == R ) return mk[x] = max( mk[x], V ), mx[x] = max( V, mx[x] ), void(); push_down(x);
        if( L <= mid ) modify( Lrange, V );
        if( R >  mid ) modify( Rrange, V );
        push_up(x); }

    int query( int x, int L, int R ) 
      { if( l[x] == L and r[x] == R ) return mx[x];
        push_down(x);
        if( R <= mid ) return query( Lrange );
        if( L >  mid ) return query( Rrange );
        return max( query( Lrange ), query( Rrange ) ); }
}

int cnt[100005];

namespace GRP{
    vector<int> to1[100005]; 
    vector<int> to2[100005];
    int deg[100005];
    int tag[100005];
    map< pair<int, int>, bool > MP;

    void addEdge( int u, int v )
      { if( MP[ make_pair( u, v ) ] or MP[ make_pair( v, u ) ] ) return ;
        MP[ make_pair( u, v ) ] = 1;
        to1[u].push_back(v); deg[u] ++;
        to1[v].push_back(u); deg[v] ++; }

    void countTriangle() 
      { for( int i = 0; i <= n; i ++ ) for( int j : to1[i] )
          { if( deg[i] > deg[j] or ( deg[i] == deg[j] and i > j ) ) 
              { to2[i].push_back(j); }
          }

        for( int i = 0; i <= n; i ++ )
          { for( int j : to2[i] ) tag[j] = i + 1;
            for( int j : to2[i] ) for( int k : to2[j] ) if( tag[k] == i + 1 ) 
              { cnt[ max( i, j, k ) ] --; } 
          }
      }

    void flush( int x )
      { for( int i : to1[x] ) if( i < x ) cnt[x] ++; cnt[x] --; }
}

struct Rect
  { int l, r, b, t, h, id;
    void get( int _id )
      { id = _id; cin >> l >> r >> h; }
  } R[100005], T[100005];

bool cmp1( Rect& A, Rect& B ) { return A.l == B.l ? A.b < B.b : A.l < B.l; }
bool cmp2( Rect& A, Rect& B ) { return A.r == B.r ? A.b < B.b : A.r < B.r; }
bool cmp3( Rect& A, Rect& B ) { return A.b == B.b ? A.l < B.l : A.b < B.b; }
bool cmp4( Rect& A, Rect& B ) { return A.t == B.t ? A.l < B.l : A.t < B.t; }

struct Point
  { int x, y, id;
    Point( int _x, int _y, int _id )
      : x(_x), y(_y), id(_id) { }
    bool operator <( const Point& F )
      { return x == F.x ? y < F.y : x < F.x; } 
    bool operator ==( const Point& F )
      { return x == F.x and y == F.y; }
  } ;

vector<Point> VP; 

int main(){
    cin >> n;

    SGT::build( 1, 1, 100000 ); 

    for( int i = 1; i <= n; i ++ ) R[i].get(i);
    for( int i = 1; i <= n; i ++ ) 
      { int Q = SGT::query( 1, R[i].l + 1, R[i].r );
        R[i].b = Q; R[i].t = R[i].h + Q;
        SGT::modify( 1, R[i].l + 1, R[i].r, R[i].t ); } 

    for( int i = 1; i <= n; i ++ ) if( R[i].b == 0 )
      { GRP::addEdge( 0, i ); }

    for( int i = 1; i <= n; i ++ ) T[i] = R[i];

    for( int i = 1; i <= n; i ++ ) T[i] = R[i];

    sort( R + 1, R + n + 1, cmp1 );
    sort( T + 1, T + n + 1, cmp2 );

    for( int l = 1, r = 1, p; l <= n; l ++ )
      { while( T[r].r < R[l].l or ( T[r].r == R[l].l and T[r].t < R[l].b ) ) r ++; p = r;
        while( T[p].r == R[l].l and T[p].b <= R[l].t ) GRP::addEdge( R[l].id, T[p].id ), p ++;  }

    sort( R + 1, R + n + 1, cmp3 );
    sort( T + 1, T + n + 1, cmp4 );

    for( int l = 1, r = 1, p; l <= n; l ++ )
      { while( T[r].t < R[l].b or ( T[r].t == R[l].b and T[r].r < R[l].l ) ) r ++; p = r;
        while( T[p].t == R[l].b and T[p].l <= R[l].r ) GRP::addEdge( R[l].id, T[p].id ), p ++;  }

    GRP::countTriangle();

    for( int i = 1; i <= n; i ++ )
      { VP.push_back( Point( R[i].l, R[i].b, R[i].id ) );
        VP.push_back( Point( R[i].l, R[i].t, R[i].id ) ); 
        VP.push_back( Point( R[i].r, R[i].b, R[i].id ) );
        VP.push_back( Point( R[i].r, R[i].t, R[i].id ) ); }

    sort( VP.begin(), VP.end() );

    for( int i = 0; i < (n - 1) * 4; i ++ )
      { if( VP[i] == VP[i + 1] ) if( VP[i] == VP[i + 2] ) if( VP[i] == VP[i + 3] )
          { cnt[ max( VP[i].id, VP[i + 1].id, VP[i + 2].id, VP[i + 3].id ) ] ++; } } 

    for( int i = 1; i <= n ; i ++ ) GRP::flush( i );
    for( int i = 1; i <= n ; i ++ ) cout << cnt[i] << "\n";

    return 0;
}

一些题外话：

一次偶然的机会蒟蒻 bzy 看到了这到风格古老的题，然后无聊的时候花 10min 想了出来，但应为退役太久实力退化太严重所以花了几天才实现完全。

但却实在想不明白这一道难度正常的题为何 11 年来无人问津，果然还是 HNOI 出题人太懒从不放官方题解的缘故吗?

抛开这些因素，个人认为本题很符合 HNOI 历年来的风格，是一道不错的图论题。

但在互联网时代的大浪淘沙之下，又有多少曾经璀璨的事物被人淡忘而暗自蒙尘呢?