[BOJ] 15977 조화로운 행렬

2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.

다시는 2d segment tree를 짤 일이 없었으면 한다.

#include <bits/stdc++.h>
 
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
int m;
 
typedef struct node
{
    int val;
    int left, right;
    node() : val(0),left(-1),right(-1) {}
}Node;
Node N[55000000];
 
int ncnt=0;
int alloc() {return ncnt++;}
 
typedef struct SegmentTree
{
    int n,left,right;
    SegmentTree() : n(0), left(-1), right(-1) {}
    void initN(int _n) {n=_n+1;}
    int root=alloc();
 
    void update(int nidx, int st, int en, int idx, int diff)
    {
        Node& nd=N[nidx];
        if(idx<st || en<idx) return;
        if(st==en && st==idx)
        {
            nd.val=diff;
            return;
        }
        int mid=(st+en)>>1;
        int ma=0;
        if(idx<=mid)
        {
            if(nd.left==-1) nd.left=alloc();
            update(nd.left,st,mid,idx,diff);
            ma=max(ma,N[nd.left].val);
            if(nd.right!=-1) ma=max(ma,N[nd.right].val);
        }
        else
        {
            if(nd.right==-1) nd.right=alloc();
            update(nd.right,mid+1,en,idx,diff);
            ma=max(ma,N[nd.right].val);
            if(nd.left!=-1) ma=max(ma,N[nd.left].val);
        }
        nd.val=ma;
    }
    void update(int idx, int diff) {update(root,0,n-1,idx,diff);}
 
    int query(int nidx, int st, int en, int le, int ri)
    {
        Node& nd=N[nidx];
        if(en<le || ri<st) return 0;
        if(le<=st && en<=ri) return nd.val;
        int mid=(st+en)>>1;
        int ma=0;
        if(nd.left!=-1) ma=max(ma,query(nd.left,st,mid,le,ri));
        if(nd.right!=-1) ma=max(ma,query(nd.right,mid+1,en,le,ri));
        return ma;
    }
    int query(int le, int ri) {return query(root,0,n-1,le,ri);}
}ST;
ST STN[4000000];
 
int stn=0;
int allocST() {STN[stn].initN(m); return stn++;}
 
typedef struct Seg2D
{
    int n,root=allocST();
    Seg2D(int _n) : n(_n+1) {}
 
    void update(int nidx, int st, int en, int x, int y, int diff)
    {
        ST& nd=STN[nidx];
        if(x<st || en<x) return;
        if(st==en && st==x)
        {
            nd.update(y,diff);
            return;
        }
        int mid=(st+en)>>1;
        int ma=0;
        if(x<=mid)
        {
            if(nd.left==-1) nd.left=allocST();
            update(nd.left,st,mid,x,y,diff);
            ma=max(ma,STN[nd.left].query(y,y));
            if(nd.right!=-1) ma=max(ma,STN[nd.right].query(y,y));
        }
        else
        {
            if(nd.right==-1) nd.right=allocST();
            update(nd.right,mid+1,en,x,y,diff);
            ma=max(ma,STN[nd.right].query(y,y));
            if(nd.left!=-1) ma=max(ma,STN[nd.left].query(y,y));
        }
        nd.update(y,ma);
    }
    void update(int x, int y, int diff){update(root,0,n-1,x,y,diff);}
 
    int query(int nidx, int st, int en, int x1, int x2, int y1, int y2)
    {
        ST& nd=STN[nidx];
        if(x2<st || en<x1) return 0;
        else if(x1<=st && en<=x2) return nd.query(y1,y2);
        int mid=(st+en)>>1;
        int ma=0;
        if(nd.left!=-1) ma=max(ma,query(nd.left,st,mid,x1,x2,y1,y2));
        if(nd.right!=-1) ma=max(ma,query(nd.right,mid+1,en,x1,x2,y1,y2));
        return ma;
    }
    int query(int x1, int x2, int y1, int y2) {return query(root,0,n-1,x1,x2,y1,y2);}
}ST2;
 
typedef struct vecarr
{
   int x,y,z;
   //vecarr(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
}va;
 
bool comp_x(va a, va b) {return a.x<b.x;}
bool comp_y(va a, va b) {return a.y<b.y;}
bool comp_z(va a, va b) {return a.z<b.z;}
 
int main()
{
    int n;
    scanf("%d %d",&n,&m);
 
    if(n==2)
    {
        vector<pii> pv(m); vi dp;
        for(int i=0;i<m;i++) scanf("%d",&pv[i].first);
        for(int i=0;i<m;i++) scanf("%d",&pv[i].second);
        sort(pv.begin(),pv.end());
        for(int i=0;i<m;i++)
        {
            auto it=lower_bound(dp.begin(),dp.end(),pv[i].second);
            if(it==dp.end()) dp.push_back(pv[i].second);
            else *it=pv[i].second;
        }
        printf("%d",dp.size());
        return 0;
    }
 
    vector<va> V(m);
    for(int i=0;i<m;i++) scanf("%d",&V[i].x);
    for(int i=0;i<m;i++) scanf("%d",&V[i].y);
    for(int i=0;i<m;i++) scanf("%d",&V[i].z);
    sort(V.begin(),V.end(),comp_y);
    for(int i=1;i<=V.size();i++) V[i-1].y=i;
    sort(V.begin(),V.end(),comp_z);
    for(int i=1;i<=V.size();i++) V[i-1].z=i;
    sort(V.begin(),V.end(),comp_x);
 
    int ma=0; ST2 S(m);
    for(int i=0;i<V.size();i++)
    {
        va& h=V[i];
        int val=S.query(0,h.y-1,0,h.z-1)+1;
        ma=max(ma,val);
        S.update(h.y,h.z,val);
    }
    printf("%d",ma);
    return 0;
}