Description：

$n$ 个人排成一列，要求将数列分段，其中第 $i$ 个人所在的段必须在 $[l_i,r_i]$ 之内，求分段的最多段数和最优解方案数。

$1\leqslant n\leqslant 10^6$

Solution：

设 $f[i]$ 表示把前 $i$ 个人分好的最优解， $g[i]$ 是方案数，暴力转移为： $$ \begin{align} f[i]&=\max_{j=0}^{i-1}\bigg(f[j]+1(\max_{k=j+1}^il_k\leqslant i-j\leqslant \min_{k=j+1}^i r_k)\bigg)\\ g[i]&=\sum_{j=0}^{i-1}g[j]\bigg(\max_{k=j+1}^il_k\leqslant i-j\leqslant \min_{k=j+1}^i r_k,f[j]+1=f[i])\bigg) \end{align} $$ 发现限制太多，这个时候我们可以考虑用分治优化 $DP$ ，首先如果只考虑 $r$ 的限制的话，会发现合法的是一个后缀，并且这个后缀是单调的，因为如果某个位置不合法了，它后面的都不合法了，于是可以预处理每个 $i$ 的合法开头 $lef[i]$ ，考虑加上 $l$ 的限制，我们可以求出 $[l+1,r]$ 中 $l$ 最大的位置设为 $k$ ，然后分治左边求出左边的所有 $f$ 值，然后考虑用 $[l,k-1]$ 的所有状态去更新 $[k,r]$ 的所有状态，这时候转移为： $$ f[i]=\max_{j=l}^{k-1}\bigg(f[j]+1(lef[i]\leqslant j\leqslant i-l_k)\bigg)(\max(k,l+l_k)\leqslant i\leqslant r) $$ 限制就变得比较容易处理。

首先初始化 $i=\max(l+l_k,k)$ ，然后用一对左右指针维护当前能转移到的范围，即： $l=\max(l,lef[i]),r=\min(k-1,i-l_k)$ ，然后显然 $i$ 每往右走一格， $r$ 扩大一格，答案支持增量，所以可以 $O(1)$ 更新，但是可能 $l$ 也要往右走，这个时候我们就暴力在线段树上查，当右端点顶到 $k-1$ 的时候，批量操作，具体来说：

$lef[i]\geqslant k$ ：无法转移。

$l\leqslant lef[i]<k$ ：暴力在线段树上查，因为转移到 $i$ 的每个区间 $[l,k-1]$ 互不相交，因此对于每个 $i$ 最多会操作一次。

$lef[i]<l,i<k+l_k$ ： $i$ 每往后移动一次转移区间扩大一，每次 $O(1)$ 更新答案。

$lef[i]<l,i\geqslant k+l_k$ ：显然合法的 $i$ 是一段区间，可以二分得到这个区间，然后批量修改。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

#define MOD 1000000007

int le[MAXN],ri[MAXN];

int lef[MAXN];

#define pii pair<int,int>

#define fi first

#define se second

#define mp make_pair

namespace T1

{

	struct node

	{

		int lc,rc;

		pii s;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	#define mid ((l + r) >> 1)

	pii mymax(pii a,pii b)

	{

		if(a.fi >= b.fi)return a;

		else return b;

	}

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r){t[rt].s = mp(le[l],l);return;}

		build(t[rt].lc,l,mid);build(t[rt].rc,mid + 1,r);

		t[rt].s = mymax(t[t[rt].lc].s,t[t[rt].rc].s);

		return;

	}

	pii query(int rt,int L,int R,int l,int r)

	{

		if(L <= l && r <= R)return t[rt].s;

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return mymax(query(t[rt].lc,L,R,l,mid),query(t[rt].rc,L,R,mid + 1,r));

	}

}

#define INF 0x3f3f3f3f

struct state

{

	int mx,cnt;

	state(int mx_ = -INF,int cnt_ = 0){mx = mx_;cnt = cnt_;}

	friend state operator + (state a,state b)

	{

		if(a.mx == b.mx)return (state){a.mx,(a.cnt + b.cnt) % MOD};

		else return (a.mx > b.mx ? a : b);

	}

	state operator += (const state& b){*this = *this + b;return *this;}

	friend state operator + (state a,int b){return (state){a.mx + b,a.cnt};}

}f[MAXN];

namespace T2

{

	struct node

	{

		int lc,rc;

		state val,tag;

	}t[MAXN << 1];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root;

	void build(int &rt,int l,int r)

	{

		rt = newnode();

		if(l == r){if(l == 0)t[rt].val = (state){0,1};return;}

		build(t[rt].lc,l,mid);build(t[rt].rc,mid + 1,r);

		t[rt].val = t[t[rt].lc].val + t[t[rt].rc].val;

		return;

	}

	void pushdown(int rt)

	{

		t[t[rt].lc].val += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].val += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = (state){-INF,0};

		return;

	}

	void add(int rt,int L,int R,state k,int l,int r)

	{

		if(L > R)return;

		if(L <= l && r <= R){t[rt].val += k;t[rt].tag += k;return;}

		if(t[rt].tag.cnt != 0)pushdown(rt);

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

		t[rt].val = t[t[rt].lc].val + t[t[rt].rc].val;

		return;

	}

	state query(int rt,int L,int R,int l,int r)

	{

		if(L > R)return (state){-INF,0};

		if(L <= l && r <= R)return t[rt].val;

		if(t[rt].tag.cnt != 0)pushdown(rt);

		if(R <= mid)return query(t[rt].lc,L,R,l,mid);

		if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

		return query(t[rt].lc,L,R,l,mid) + query(t[rt].rc,L,R,mid + 1,r);

	} 

}

int findpos(int l,int r,int k)

{

	int mi;

	while(l < r)

	{

		mi = ((l + r + 1) >> 1);

		if(lef[mi] <= k)l = mi;

		else r = mi - 1;

	}

	return l;

}

void work(int l,int k,int r)

{

	int i = max(l + le[k],k);

	int nowl = max(l,lef[k]),nowr = min(k - 1,i - le[k]);

	state ans = T2::query(T2::root,nowl,nowr,0,n);

	if(ans.cnt)ans = ans + 1;

	if(i > r || lef[i] >= k)return;

	for(;i <= r && lef[i] <= l && i < k + le[k];++i)

	{

		f[i] += ans;

		++nowr;

		ans = ans + (f[nowr] + 1);

	}

	if(i <= r && lef[i] <= l && i >= k + le[k])

	{

		int p = findpos(i,r,l);

		state tr = T2::query(T2::root,l,k - 1,0,n) + 1;

		T2::add(T2::root,i,p,tr,0,n);

		i = p + 1;

	}

	for(;i <= r && lef[i] < k;++i)

	{

		f[i] += T2::query(T2::root,lef[i],min(k - 1,i - le[k]),0,n) + 1;

	}

	return;

}

void solve(int l,int r)

{

	if(l > r)return;

	if(l == r)

	{

		T2::add(T2::root,l,l,f[l],0,n);

		f[l] = T2::query(T2::root,l,l,0,n);

		return;

	}

	int k = T1::query(T1::root,l + 1,r,0,n).se;

	solve(l,k - 1);work(l,k,r);solve(k,r);

	return;

}

void prework()

{

	int q[MAXN],head = 1,tail = 0;

	int pos = 0;

	for(int i = 1;i <= n;++i)

	{

		while(head <= tail && ri[q[tail]] >= ri[i])--tail;

		q[++tail] = i;

		while(head <= tail && i - pos > ri[q[head]])

		{

			++pos;

			if(q[head] <= pos)++head;

		}

		lef[i] = pos;

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&le[i],&ri[i]);

	prework();lef[n + 1] = INF;

	T1::build(T1::root,0,n);T2::build(T2::root,0,n);

	solve(0,n);

	state ans = T2::query(T2::root,n,n,0,n);

	if(ans.cnt == 0)puts("NIE");

	else printf("%d %d\n",ans.mx,ans.cnt);

	return 0;

}