【学习笔记】各类基于决策单调性的dp优化

贴个模板

//该模板适用于最小化问题，若求最大化，自行将对应不等号取反即可
//cal(j,i):g_j(i)
    ll que[N];//单调队列
    hd=1,tl=0;
    que[++tl]=0;ls[0]=1,rs[0]=n;
	for(int i=1;i<=n;++i)
    {
        while(hd<tl&&rs[que[hd]]<i) hd++;//弹出无用点
        dp[i]=cal(que[hd],i);
        pre[i]=que[hd];
        while(hd<tl&&cal(i,ls[que[tl]])<=cal(que[tl],ls[que[tl]])) tl--;//弹出无用点
        ll l=ls[que[tl]],r=n+1;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(cal(i,mid)<=cal(que[tl],mid)) r=mid-1;
            //二分查找i与que[tl]的转移分界点，也就是最小的满足i优于que[tl]的点
            else l=mid+1;
        }
        p_ans=r+1;
        if(p_ans>n) continue;
        //i并没有用
        rs[que[tl]]=p_ans-1;
        que[++tl]=i;//插入队列
        ls[i]=p_ans,rs[i]=n;
    }
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

Tips:二分决策区间边界的时候，右界设置为n+1,因为i有可能完全不如P优，要防一手

如果$w(j,i)$我们能够以$O(1)$的复杂度求出的话，该方法的时间复杂度式$O(nlog)$的

例题：

NOI 2009 诗人小G

dp式并不难列出，关于其决策单调性我们已经在上一块里证明过了，所以这里直接用二分队列即可

数据范围有点大，记得开long double

code

#include
using namespace std;
#define ll long long
#define ld long double
#define IL inline
#define endl '\n'
const ll N=100010;
const ll mod=998244353;
const ll inf=1e18;
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
int n,L,P;
char s[N][50];
ld mas[N];
int ls[N],rs[N],pre[N];//记录最优决策点
int que[N];
int hd,tl,p_ans;
ld dp[N];
ld ksm(ld x,ll y)
{
    ld ans=1;
    while(y)
    {
        if(y&1) ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
ld cal(ll k,ll x)
{
    return dp[k]+ksm(abs(mas[x]-mas[k]-1-L),P);
}
void solve()
{
    n=read();L=read();P=read();
    for(int i=1;i<=n;++i) scanf("%s",s[i]);
    // for(int i=1;i<=n;++i) cin>>s[i];
    for(int i=1;i<=n;++i)
    {
        mas[i]=mas[i-1]+strlen(s[i])+1;
    }
    hd=1,tl=0;
    que[++tl]=0;ls[0]=1,rs[0]=n;
    for(int i=1;i<=n;++i)
    {
        while(hd<tl&&rs[que[hd]]<i) hd++;
        dp[i]=cal(que[hd],i);
        pre[i]=que[hd];
        while(hd<tl&&cal(i,ls[que[tl]])<=cal(que[tl],ls[que[tl]])) tl--;
        ll l=ls[que[tl]],r=n+1;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(cal(i,mid)<=cal(que[tl],mid)) r=mid-1;
            //二分查找i与que[tl]的转移分界点，也就是最小的满足i优于que[tl]的点
            else l=mid+1;
        }
        p_ans=r+1;
        if(p_ans>n) continue;
        //i并没有用
        rs[que[tl]]=p_ans-1;
        que[++tl]=i;//插入队列
        ls[i]=p_ans,rs[i]=n;
    }
    ///

    if(dp[n]>inf)
    {
        puts("Too hard to arrange");
    }
    else
    {
        printf("%lld\n",(ll)dp[n]);
        vector<string> ans;
        ll pos=n;
        while(1)
        {
            ll x=pre[pos]+1;
            string ss="";
            for(int i=x;i<pos;++i) ss+=s[i],ss+=" ";
            ss+=s[pos];
            ans.push_back(ss);
            pos=pre[pos];
            if(pos==0) break;
        }
        reverse(ans.begin(),ans.end());
        for(auto i:ans) cout<<i<<endl;
    }
    puts("--------------------");
}
int main()
{
    // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;t=read();while(t--)
    solve();
    return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

二分栈

一般用于最优决策点是不增的情况。在原本的二分队列的做法中，我们从队列的首部取出最优决策点，从队列的尾部放入决策点。那么如果决策点是不增的，意味着我们需要从队列的尾部取最优决策点。这样取和放的操作都是在队列的尾部，我们只要用一个栈来实现就好了。同样的，相邻的两个决策点更新的区间会有一个边界，我们不妨记为$k_{l,r}$,当尝试加入$i$的时候，记队列倒数第一个元素为$p_1$,倒数第二个元素为$p_2$,那么如果$k_{p_1,p_2}\le k_{p_2,i}$,那么$p_2$就可以踢掉了，因为它不管在什么时候都不会是$i,p_1,p_2$中的最优解。然后将$i$加入队列之后再按照$k_{p_1,p_2}$是否$\le i$来踢即可

JSOI2001 柠檬

思路：

首先不难发现最优选择下每一段的首尾的颜色就是这段的$s_0$，否则我们就可以将首尾的没用的点分出去自称一段，贡献一定更优

所以我们可以按照不同的颜色来分开处理

d p i = m a x c o l j = c o l i , j ≤ i { d p j − 1 + w ( j , i ) } dp_i=max_{col_j=col_i,j\leq i}\{dp_{j-1}+w(j,i)\} dpi​=maxcolj​=coli​,j≤i​{dpj−1​+w(j,i)},其中$w(j,i)=(su{m}_i-su{m}_j+1{)}^2$

这里我们画图就能发现决策点是单调不增的（按照上文与图形结合的方法），所以可以使用二分栈。但是这题的决策单调性是在相同颜色的点之间才存在的，所以我们要分开来做二分栈

然后每一个点不会从0转移，所以一开始也不用把0放进去

code

#include 
#define pii pair<int,int>
#define il inline
#define ll long long
using namespace std;
#define bc(idx) vt[idx].size()-1
#define bd(idx) vt[idx].size()-2
#define g(a,b) vt[a][b]
const int N=200000;
const ll inf=1e18;
ll n;
ll mas[N];
vector<ll> vt[N];
ll dp[N];
ll ls[N],rs[N];
map<ll,ll> mp;
ll sum[N];
ll gt(ll k,ll num)
{
    return dp[k-1]+mas[k]*num*num;
}
ll gtf(ll a,ll b)
{
    ll l=1,r=n;
    while(l<=r)
    {
        ll mid=l+r>>1;
        if(gt(a,mid-sum[a]+1)>=gt(b,mid-sum[b]+1)) r=mid-1;
        else l=mid+1;
    }
    return r+1;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>mas[i];
        mp[mas[i]]++;
        sum[i]=mp[mas[i]];
    }
    for(int i=1;i<=n;++i)
    {
        ll idx=mas[i];
        while(vt[idx].size()>=2&& gtf(g(idx,bd(idx)),g(idx,bc(idx)))<=gtf(g(idx,bc(idx)),i)) vt[idx].pop_back();
        vt[idx].push_back(i);
        while(vt[idx].size()>=2&& gtf(g(idx,bd(idx)),g(idx,bc(idx)))<=sum[i]) vt[idx].pop_back();
        dp[i]=gt(g(idx,bc(idx)),sum[i]-sum[g(idx,bc(idx))]+1);
    }
    cout<<dp[n]<<endl;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

分治

分治的方法主要用于同一层之间的点相互之间线性无关的情况。

比如$F_1$ : d p i , j = m i n { d p i − 1 , k + w ( k , i ) } :dp_{i,j}=min\{dp_{i-1,k}+w(k,i)\} :dpi,j​=min{dpi−1,k​+w(k,i)}.$F_2$ : d p i = m i n { a k + w ( k , i ) } :dp_i=min\{a_k+w(k,i)\} :dpi​=min{ak​+w(k,i)}

可以看到同一层之间的点不会相互转移

那么如果同一层的点满足决策单调性的话，也就是意味着决策点是单调的，我们就可以采用分治的策略来优化转移的过程

假设当前需要转移的区间是$[L,R]$,决策点的选择区间是$[p_l,p_r]$(显然一开始转移区间和决策点的选择区间都为$[1,n]$)，设$mid=\frac{L+R}{2}$,我们可以先暴力求出$mid$的最优决策点$pos$,那么$[L,mid-1]$的决策点选择区间就是$[p_l,pos]$,$[mid+1,R]$的决策点选择区间就是$[pos,p_r]$，那么这样分治下去就好了。

如果我们可以$O(1)$求代价的话，对$mid$求$pos$的时间复杂度就只有$O(n)$,再加上每次要处理的区间长度会变成原本的一半，所以处理区间为n的复杂度是$f(n)=O(n)+O(f(n/2))$,总复杂度是$O(nlogn)$

一个板子：

void Solve(ll l,ll r,ll pl,ll pr)
{
	//当前分治处理区间是[l,r],最佳决策区间是[pl,pr]
	ll mid=l+r>>1;
	ll pos;//mid的最佳决策点
	dp[mid]=gt(pos=pl,mid);
	for(int i=pl+1;i<=min(mid-1,pr);++i)
	{
		if(gt(i,mid)<dp[mid]) dp[mid]=gt(pos=i,mid);
	}
	if(l<mid) Solve(l,mid-1,pl,pos);
	if(r>mid) Solve(mid+1,r,pos,pr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

JSOI2016 灯塔

大意：

给定$h_i$，对于每一个$i$,要求$\forall j,p_i\ge h_j-h_i+\sqrt{|i-j|}$,求最小的$p_i$

思路：

不妨先将绝对值去掉，那么 p i = { m i n { h j + i − j − h i } j < i m i n { h j + j − i − h i } j > i p_i=\left\{min{hj+√i−j−hi}j<imin{hj+√j−i−hi}j>i

那么我们只要处理第一个式子就好了，第二个式子只要把整个数组反一下即可

可以发现 p i = m i n { h j + i − j − h i } p_i=min\{h_j+\sqrt{i-j}-h_i\} pi​=min{hj​+i−j ​−hi​}满足决策单调性，并且$p_i$之间相互无关，所以直接分治就解决了

code

#include
using namespace std;
#define ll long long
#define IL inline
#define endl '\n'
const ll N=5e5+10;
double ep=1e-9;
const ll mod=998244353;
const ll inf=1e18;
ll n;
ll mas[N];
double dp1[N],dp2[N];
double gt(ll p,ll x)
{
    return mas[p]+sqrt(x-p)-mas[x];
}
void Solve(ll l,ll r,ll pl,ll pr,double *dp)
{
    // if(l>r||pl>pr) return;
    ll mid=(l+r)>>1;
    ll pos=pl;
    for(int i=pl;i<=min(mid,pr);++i)
    {
        if(gt(i,mid)-dp[mid]>=-ep) dp[mid]=gt(pos=i,mid);//要取>=0
    }
    if(l<mid) Solve(l,mid-1,pl,pos,dp);
    if(r>mid) Solve(mid+1,r,pos,pr,dp);
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>mas[i];
    Solve(1,n,1,n,dp1);
    reverse(mas+1,mas+1+n);
    Solve(1,n,1,n,dp2);
    for(int i=1;i<=n;++i)
    {
        double x=fmax(dp1[i],dp2[n-i+1]);
        cout<<(ll)ceil(x)<<endl;
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // ll t;t=read();while(t--)
    solve();
    return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

SDOI2016 征途

CF321 E

类莫队做法

注意到分治要保证时间复杂度的前提是每次求$w$代价的复杂度是$O(1)$的

但是有一类$w$比较特殊：关于区间的信息的记录，比如区间数字种类数等。这种问题我们一般可以离线下来用莫队处理，那么仿照莫队用左右端点的连续移动就可以做到$O(1)$转移了，因为我们的决策点的选择范围也刚好是一个连续的区间，所以这样的话复杂度是正确的

CF868 F

CmdOI2019 任务分配问题

#include
#include 
using namespace std;
#define ll int
#define IL inline
#define endl '\n'
const ll N=3e4+10;
double ep=1e-9;
const ll mod=998244353;
const ll inf=1e9;
struct Tree
{
    ll tr[N];
    #define low(x) x&(-x)
    void add(ll x,ll y)
    {
        while(x<N)
        {
            tr[x]+=y;
            x+=low(x);
        }
    }
    ll sum(ll x)
    {
        ll ans=0;
        while(x)
        {
            ans+=tr[x];
            x-=low(x);
        }
        return ans;
    }
}T;
ll n,k;
ll mas[N];
ll dp[N],pp[N];
namespace Mo
{
    int L=1,R=0;
    ll ans=0;
    int col[N];
    ll cnt[N];
    void add1(ll pos,ll op)//区间左边
    {
        if(op==1)
        {
            ans+=T.sum(n+1)-T.sum(col[pos]);
            T.add(col[pos],1);
        }
        else
        {
            ans-=T.sum(n+1)-T.sum(col[pos]);
            T.add(col[pos],-1);
        }
    }
    void add2(ll pos,ll op)//区间右边
    {
        if(op==1)
        {
            ans+=T.sum(col[pos]-1);
            T.add(col[pos],1);
        }
        else
        {
            ans-=T.sum(col[pos]-1);
            T.add(col[pos],-1);
        }
    }
    ll gt(ll l,ll r)
    {
        l++;
        while(L<l) add1(L++,0);
        while(L>l) add1(--L,1);
        while(R>r) add2(R--,0);
        while(R<r) add2(++R,1);
        return pp[l-1]+ans;
    }
}
void Solve(ll l,ll r,ll pl,ll pr)
{
    ll mid=(l+r)>>1;
    ll pos;
    dp[mid]=Mo::gt(pos=pl,mid);
    for(int i=pl+1;i<=min(mid-1,pr);++i)
    {
        if(dp[mid]>Mo::gt(i,mid)) dp[mid]=Mo::gt(pos=i,mid);
    }

    if(l<mid) Solve(l,mid-1,pl,pos);
    if(r>mid) Solve(mid+1,r,pos,pr);
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>Mo::col[i];
    }
    for(int i=1;i<=n;++i) pp[i]=Mo::gt(0,i);
    for(int i=1;i<k;++i)
    {
        Solve(1,n,0,n);
        for(int j=1;j<=n;++j) pp[j]=dp[j];
    }
    cout<<pp[n]<<endl;

}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // ll t;t=read();while(t--)
    solve();
    return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

SMAWK

SMAWK的用途跟分治一样，用于处理同一层之间没有转移关系的情况，但是复杂度会更优，可以达到$O(n)$

我们考虑从另一个角度来理解决策单调性

定义1 若矩阵A满足∀i,j∈[0,k],pos(i)

重新定义四边形不等式

定义2 对于n*m的矩阵A，若$\forall 1<i_1<i_2\le n,1\le j_1,\le j_2\le m$,均有$A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}$,则称A满足四边形不等式

快速判断矩阵是否满足四边形不等式：

定理1 对于n*m的矩阵A，若$\forall 1<i<n,1\le j<m$,均有$A_{i,j}+A_{i+1,j+1}\le A_{i,j+1}+A_{i+1,j}$,则称A满足四边形不等式

定理2 若矩阵A满足四边形不等式，则A以及$A^T$是完全单调矩阵

证明就不给了，感兴趣可以去看看原论文

接下来考虑 d p i = m i n j < i { a j + w ( j , i ) } dp_i=min_{jdpi​=minj<i​{aj​+w(j,i)},放到矩阵上，当$j<i$时，$A_{i,j}=d{p}_j+w(j,i),j\ge i$时，令$A_{i,j}=inf$，那么求$d{p}_i$其实就是在第i行找最小值对应的列j.如果矩阵是一个单调矩阵，也就是dp满足决策单调性，我们就可以采用SMAWK

struct Node
{
    ll val,opt;
    Node *lst,*nxt;
    Node(){val=opt=0;lst=nxt=NULL;}
};
struct List
{
    ll len;//列表长度
    Node *s,*e;
    List()
    {
        len=0;
        s=new Node();s->opt=1;
        e=new Node();e->opt=-1;
        s->nxt=e;e->lst=s;
    }
    void append(ll x)
    {
        //将x加入尾部
        Node *n=new Node();
        n->val=x;
        Node *a=e->lst;//尾部元素
        a->nxt=n;n->lst=a;
        n->nxt=e;e->lst=n;
        len++;//长度
    }
    List(const List &a)
    {
        //Copy
        len=0;
        s=new Node();s->opt=1;
        e=new Node();e->opt=-1;
        s->nxt=e;e->lst=s;
        Node *n=a.s->nxt;
        while(n->opt!=-1)
        {
            append(n->val);
            n=n->nxt;
        }
    }
    Node* del(Node *n)
    {
        --len;
        Node *a=n->lst,*b=n->nxt;
        a->nxt=b,b->lst=a;
        delete(n);
        return a;//前一个节点
    }
};
struct submat
{
    List r,c;
    //row,column
}A;
submat Reduce(const submat &A)
{
    submat B;
    B.r=(List)A.r;B.c=(List)A.c;
    int n=A.r.len;//行数
    int m=A.c.len;//列数
    Node *nr=B.r.s->nxt;//第一个节点
    Node *nc=B.c.s->nxt;
    ll k=1;
    while(n<m)
    {
        if(get(nr->val,nc->val)>get(nr->val,nc->nxt->val))
        {
            nc=B.c.del(nc);
            m--;
            if(k>1)
            {
                --k;
                nr=nr->lst;
            }
            else
            {
                //k=1
                nr=B.r.s->nxt;nc=B.c.s->nxt;
            }
        }
        else if(k==n)
        {
            B.c.del(nc->nxt);m--;
        }
        else
        {
            k++;
            nr=nr->nxt;nc=nc->nxt;
        }
    }
    return B;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

void SMAWK(submat A)
{
    int n=A.r.len;//行数
    int m=A.c.len;//列数
    if(n==1)
    {
        ll x=A.r.s->nxt->val;//只有一行
        Node *nc=A.c.s->nxt;
        ll maxn=0;
        ll maxp=0;//最值位置
        while(nc->opt!=-1)
        {
            if(get(x,nc->val)>=maxn)
            {
                maxp=nc->val,maxn=get(x,nc->val);
            }
            nc=nc->nxt;
        }
        ans[x]=maxp;//存储最大值所在位置
        ///
        return;
    }
    if(m==1)
    {
        ll y=A.c.s->nxt->val;
        Node *nr=A.r.s->nxt;//第一行
        while(nr->opt!=-1)
        {
            ans[nr->val]=y;
            nr=nr->nxt;
        }
        return;
    }
    submat B=Reduce(A);
    submat C;C.c=List(B.c);//首先保存每一列的信息
    Node *nr=B.r.s->nxt;//行第一个元素
    bool fl=0;
    while(nr->opt!=-1)
    {
        if(fl) C.r.append(nr->val);//C保存偶数行
        nr=nr->nxt;
        fl^=1;
    }
    //得到一个只有偶数行，列不变的矩阵
    SMAWK(C);//递归
    nr=B.r.s->nxt;fl=0;
    Node *nc=B.c.s->nxt;//列指针
    while(nr->opt!=-1)
    {
        if(!fl)
        {
            ll z=ans[nr->nxt->val];//已经处理过了，这里是有值的
            ll x=nr->val;
            ll maxn=0,maxp=0;
            if(z==0) z=inf;
            while(nc->opt!=-1 && nc->val<=z)
            {
                //枚举列
                //返回的是最右边的最小值
                if(get(x,nc->val)>=maxn)
                {
                    maxn=get(x,nc->val);
                    maxp=nc->val;
                }
                nc=nc->nxt;
            }
            if(nc->lst->val==z) nc=nc->lst;
            ans[x]=maxp;
        }
        nr=nr->nxt;
        fl^=1;
    }
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

//求每行最左边最小值
int pre[N],suf[N],M[N],n,m,ans=1e18,P=0;
vector<int>L,H;
map<int,int>Mp[N];
ll get(ll a,ll b)
{
    //返回第a行第b列的元素
} 
int pre[N],suf[N],M[N],P=0;
void del(int x)
{
    if (pre[x]!=-1)
        suf[pre[x]]=suf[x]; else P=suf[x];
    pre[suf[x]]=pre[x];
}
vector<int> reduce(vector<int>X,vector<int>Y)
{
    for (int i=0;i<Y.size();i++) pre[i]=i-1,suf[i]=i+1;
    int x=0,y=0;
    P=0;
    for (int nmsl=Y.size()-X.size();nmsl>0;nmsl--)
    {
        if (get(X[x],Y[y])<get(X[x],Y[suf[y]]))
        {
            y=suf[y];
            del(pre[y]);
            if (x) y=pre[y],x--;
        } else
        {
            if (x==X.size()-1) del(suf[y]);
            else
            {
                y=suf[y];
                x++;
            }
        }
    }
    vector<int>ret;
    for (int i=P;i!=Y.size();i=suf[i])  ret.push_back(Y[i]);
    return ret;
}
void Solve(vector<int>X,vector<int>Y)
{
    Y=reduce(X,Y);
    if (X.size()==1)
    {
        M[X[0]]=Y[0];
        return;
    }
    vector<int>Z;
    for (int i=0;i<X.size();i++)
        if (!(i%2)) Z.push_back(X[i]);
    Solve(Z,Y);
    for (int i=0;i<X.size();i++)
    {
        if (!(i%2)) continue;
        int l=lower_bound(Y.begin(),Y.end(),M[X[i-1]])-Y.begin();
        int r=0;
        if (i==X.size()-1) r=Y.size()-1;
        else
        {
            r=lower_bound(Y.begin(),Y.end(),M[X[i+1]])-Y.begin();
        }
        M[X[i]]=Y[l];
        while (l<r)
        {
            l++;
            if (get(X[i],Y[l])>get(X[i],M[X[i]])) M[X[i]]=Y[l];
        }
    }
}
signed main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		H.push_back(i);
	}
	for (int i=1;i<=m;i++) L.push_back(i);
	Solve(H,L);
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81