题目
题目链接：https://www.ybtoj.com.cn/contest/118/problem/2
(nleq 10^6)。
思路
首先我们忽略 (c) 的限制，如果只考虑 (d) 的话，不难发现以第 (i) 个人结尾分组，左端点是一段连续的区间 ([lft_i,i))。 可以用 ST 表预处理区间最小值然后双指针扫一遍求出 (lft)。
加入了 (c) 的限制之后，此时和每一个点能转移过来的位置就不是连续的区间了。考虑对于当前区间内 (c) 的最大值分治，也就是建出笛卡尔树然后按照深度优先遍历进行转移。
设区间 ([l,r])，最大值所在位置为 (mid)，先递归处理 ([l,mid))，然后求 ([l,mid)) 对 ([mid,r]) 的贡献。考虑三种情况：
- (lft_ileq l) 且 (i<mid+c_{mid})
这一段区间能被贡献的区间一定是左端点为 (l)，右端点依次加一的区间。我们求出这一段区间的左端点 (=max(mid,l+c_{mid}))，直接在线段树上求出能贡献到它的区间的贡献之和；然后从左端点开始往右枚举，每次增加一个位置的贡献，所以一次右移的复杂度是 (O(1)) 的。
线段树上查询的次数为 (O(n))，所以每次第一个位置的总复杂度是 (O(nlog n))。而右移的长度最多是 ([l,mid)) 和 ([mid,r]) 的较小值，所以类似每次类似一个启发式合并的过程，总复杂度依然是 (O(nlog n))。 - (lft_ileq l) 且 (igeq mid+c_{mid})
这一段显然可以被 ([l,mid)) 全部贡献到，直接线段树区间查询，再区间赋值即可。 - (l<lft_i<mid)
因为每一个点指挥在这样的情况一次，所以直接暴力线段树区间询问即可。
到叶子节点之后在 (f) 和线段树上取一下最优即可。
时间复杂度 (O(nlog n))。
代码
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1000010,LG=20,MOD=1e9+7;
int n,c[N],d[N],lft[N],lg[N],st[N][LG+1];
int read()
{
int d=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) d=(d<<3)+(d<<1)+ch-48,ch=getchar();
return d;
}
void buildst()
{
for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for (int i=1;i<=n;i++) st[i][0]=i;
for (int i=n;i>=1;i--)
for (int j=1;i+(1<<j)-1<=n;j++)
if (d[st[i][j-1]]<d[st[i+(1<<(j-1))][j-1]])
st[i][j]=st[i][j-1];
else
st[i][j]=st[i+(1<<(j-1))][j-1];
}
int getmin(int l,int r)
{
int k=lg[r-l+1];
if (d[st[l][k]]<d[st[r-(1<<k)+1][k]])
return st[l][k];
else
return st[r-(1<<k)+1][k];
}
struct node
{
int v,c;
friend node operator +(node x,node y)
{
if (!y.c) return x;
if (!x.c) return y;
if (x.v<y.v) return y;
if (x.v>y.v) return x;
return (node){x.v,(x.c+y.c)%MOD};
}
}f[N];
struct SegTree
{
node val[N*4],lazy[N*4];
void pushup(int x)
{
val[x]=val[x*2]+val[x*2+1];
}
void pushdown(int x)
{
if (lazy[x].c)
{
val[x*2]=val[x*2]+lazy[x];
val[x*2+1]=val[x*2+1]+lazy[x];
lazy[x*2]=lazy[x*2]+lazy[x];
lazy[x*2+1]=lazy[x*2+1]+lazy[x];
lazy[x]=(node){0,0};
}
}
void update(int x,int l,int r,int ql,int qr,node v)
{
if (ql>qr) return;
if (ql<=l && qr>=r)
{
val[x]=val[x]+v; lazy[x]=lazy[x]+v;
return;
}
pushdown(x);
int mid=(l+r)>>1;
if (ql<=mid) update(x*2,l,mid,ql,qr,v);
if (qr>mid) update(x*2+1,mid+1,r,ql,qr,v);
pushup(x);
}
node query(int x,int l,int r,int ql,int qr)
{
if (ql>qr) return (node){0,0};
if (ql<=l && qr>=r) return val[x];
pushdown(x);
int mid=(l+r)>>1; node res=(node){0,0};
if (ql<=mid) res=res+query(x*2,l,mid,ql,qr);
if (qr>mid) res=res+query(x*2+1,mid+1,r,ql,qr);
return res;
}
}seg;
void solve(int l,int r)
{
if (l==r)
{
f[l]=f[l]+seg.query(1,0,n,l,l);
f[l].v++;
seg.update(1,0,n,l,l,f[l]);
return;
}
int mid=getmin(l+1,r);
solve(l,mid-1);
int ll=mid,rr=r,mm,pos;
while (ll<=rr)
{
mm=(ll+rr)>>1;
if (lft[mm]<=l) ll=mm+1;
else rr=mm-1;
}
pos=ll-1;
// part 1
node res=seg.query(1,0,n,l,max(mid-c[mid],l));
for (int i=max(mid,l+c[mid]);i<=pos;i++)
{
if (mid+c[mid]<=i) break;
f[i]=f[i]+res;
res=res+f[i-c[mid]+1];
}
// part 2
res=seg.query(1,0,n,l,mid-1);
seg.update(1,0,n,mid+c[mid],pos,res);
// part 3
for (int i=pos+1;i<=r;i++)
{
if (lft[i]>=mid) break;
f[i]=f[i]+seg.query(1,0,n,lft[i],min(mid-1,i-c[mid]));
}
solve(mid,r);
}
int main()
{
freopen("schooldays.in","r",stdin);
freopen("schooldays.out","w",stdout);
n=read();
for (int i=1;i<=n;i++)
c[i]=read(),d[i]=read();
buildst();
for (int i=1,j=1;i<=n;i++)
{
while (i-j+1>d[getmin(j,i)]) j++;
lft[i]=j-1;
}
for (int i=1;i<=n;i++) d[i]=n-c[i]+1;
buildst();
f[0]=(node){0,1};
solve(0,n);
if (f[n].c) printf("%d %d",f[n].v-1,f[n].c);
else printf("-1");
return 0;
}