思维妙妙题。
首先发现 \(d\) 的限制满足单调性，所以可以转化为 \(l\ge p_r\) 的限制。
注意：\(p\) 是单调不降的
然后就是 \(p_r\le l\le r,\max\limits_{i=l}^r\{c_i\}\le r-l+1\)。
这个 \(\max\) 想到转化到笛卡尔树上操作。
然而这题要需要一个 dp，所以考虑类似 cdq 分治一样分治转移。
注意：在笛卡尔树上的分治优化 dp 转移值得注意
在 \(u\) 节点时，设 \(L_u,R_u\) 表示 \(u\) 对应原序列的区间。
那么在 \(u\) 节点时，会对所有满足 \(L_u\le l \le u\le r\le R_u\) 的区间 \([l,r]\) 进行转移。
现在对于 \(l\) 的限制变成了 \(\max\{L_u,p_r\}\le l< \min\{r-c_u,u\}\)下面开始分类讨论
设 \(lim\) 为最小的满足 \(i\in[u,R_u],p_i\ge L_u\) 的 \(i\)，若不存在 \(lim=R_u+1\)。
- 由于 \(p\) 的单调性，\(lim\) 可用二分求出
\(1.p_r<L_u \and r-c_u<u \iff r< \min\{lim,c_u+u\}\)
此时的转移点 \(l\) 的限制即为 \(L_u\le l<r-c_u<u\)。
发现 \(r\) 向右移动一步时，\(r-c_u\) 也会向右移动一步。
可以维护一对双指针从左向右扫过去，每次单点查询，初始位置 \(u\) 可以用线段树区间查询出来。
这样的总复杂度为 \(O(n\log n)\)，类似启发式合并。
因为 \(l,r\) 都只能在两边扫，距离一定，每次的运算次数为 【左右区间大小的较小值】
\(2.p_r<L_u \and r-c_u\ge u\iff c_u+u\le r<lim\)
此时的 \(l\) 取遍 \([L_u,u]\) 中的所有数，可以线段树区间查询，区间修改。
\(3.L_u\le p_r\le u\iff lim\le r \le Lim\)
\(Lim\) 为最大的满足 \(i\in [u,R_u],p_i\le u\) 的 \(i\)。
这样的转移似乎很难转移，但是这样的总转移次数是 \(O(n)\) 的。
因为 \(L_u\le p_r\le u\le r\le R_u\)，一个转移 \((p_r,r)\) 只会在区间 \([p_r,r]\) 的最大值处转移一次，所以可以枚举 \(r\)，线段树区间查询转移。
细节不少，由于要计算方案数，所以要注意贡献不能算两次。
单点修改和区间修改的贡献不能混杂在一起。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+10,INF=1e9,mod=1e9+7;
int n,a[N],b[N];
struct zj{
int mx,cnt;
zj operator + (const zj &x)const{
if(mx^x.mx)return mx>x.mx?*this:x;
return {mx,(cnt+x.cnt)%mod};
}
zj add()const{
if(mx==-INF)return *this;
return {mx+1,cnt};
}
}t[N<<2],laz[N<<2],f[N];
void pushup(int rt){
t[rt]=t[rt<<1]+t[rt<<1|1];
}
void pushadd(int rt,zj x){
t[rt]=t[rt]+x,laz[rt]=laz[rt]+x;
}
void pushdown(int rt){
if(laz[rt].mx>-INF){
pushadd(rt<<1,laz[rt]);
pushadd(rt<<1|1,laz[rt]);
laz[rt]={-INF,0};
}
}
void build(int l=0,int r=n,int rt=1){
laz[rt]={-INF,0};
if(l==r){
if(l)t[rt]={-INF,0};
else t[rt]={0,1};
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int R,zj x,int l=0,int r=n,int rt=1){
if(L<=l&&r<=R)return pushadd(rt,x);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)update(L,R,x,l,mid,rt<<1);
if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void cover(int x,zj y,int l=0,int r=n,int rt=1){
if(l==r){
t[rt]=y;return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)cover(x,y,l,mid,rt<<1);
else cover(x,y,mid+1,r,rt<<1|1);
pushup(rt);
}
zj query(int L,int R,int l=0,int r=n,int rt=1){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
pushdown(rt);
zj s={-INF,0};
if(L<=mid)s=s+query(L,R,l,mid,rt<<1);
if(mid<R)s=s+query(L,R,mid+1,r,rt<<1|1);
return s;
}
int p[N];
namespace ST{
const int K=__lg(N)+2;
int f[K][N];
void init(){
for(int i=1;i<=n;i++)f[0][i]=b[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);
}
int query(int l,int r){
int k=__lg(r-l+1);
return min(f[k][l],f[k][r-(1<<k)+1]);
}
}
int top,stk[N],ls[N],rs[N],L[N],R[N];
void init(int u){
if(ls[u])init(ls[u]),L[u]=L[ls[u]];else L[u]=u;
if(rs[u])init(rs[u]),R[u]=R[rs[u]];else R[u]=u;
}
void dfs(int u){
if(ls[u])dfs(ls[u]);
auto find=[&](){
int l=u-1,r=R[u]+1,mid;
for(;l+1<r;){
mid=(l+r)>>1;
if(p[mid]<L[u])l=mid;
else r=mid;
}
return r;
};
int lim=find();
auto trs1=[&](){
if(p[u]>=L[u])return;
int st=max(u,L[u]+a[u]-1);
int ed=min(lim-1,a[u]+u-1);
if(st>ed)return;
zj now={-INF,0};
now=now+query(L[u]-1,st-a[u]);
for(int i=st;i<=ed;i++){
if(i>st)now=now+f[i-a[u]];
if(i-a[u]+1>=u){
update(i,ed,now.add());
break;
}
f[i]=f[i]+now.add();
}
};
trs1();
auto trs2=[&](){
int st=a[u]+u,ed=lim-1;
if(st>ed)return;
update(st,ed,query(L[u]-1,u-1).add());
};
trs2();
auto calc=[&](){
int l=u,r=R[u]+1,mid;
for(;l+1<r;){
mid=(l+r)>>1;
if(p[mid]<=u)l=mid;
else r=mid;
}
return l;
};
auto trs3=[&](){
int Lim=calc();
if(lim>Lim)return;
for(int i=lim;i<=Lim;i++){
int st=p[i],ed=min(u,i+1-a[u]);
if(st<=ed)f[i]=f[i]+query(st-1,ed-1).add();
}
};
trs3();
f[u]=f[u]+query(u,u);
cover(u,f[u]);
if(rs[u])dfs(rs[u]);
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
ST::init();
for(int i=1;i<=n;i++){
int l=0,r=i,mid;
for(;l+1<r;){
mid=(l+r)>>1;
if(i-mid+1<=ST::query(mid,i))r=mid;
else l=mid;
}
p[i]=r;
}
for(int i=1;i<=n;i++){
for(;top&&a[stk[top]]<a[i];top--)ls[i]=stk[top];
rs[stk[top]]=i,stk[++top]=i;
}
f[0]={0,1};
for(int i=1;i<=n;i++)f[i]={-INF,0};
build();
init(rs[0]);
dfs(rs[0]);
// for(int i=1;i<=n;i++){
// fprintf(stderr,"%d %d\n",f[i].mx,f[i].cnt);
// }
if(f[n].cnt==0)puts("NIE");
else printf("%d %d\n",f[n].mx,f[n].cnt);
return 0;
}