Try to find out the wrong in the test
题目背景：
1.14 WC模拟T3
分析：线段树优化DP + 复杂度分析
终于不用打公式了，心累······
首先我们只考虑d的限制，在满足d限制的情况下，对于一个i，可行的上一个区间的端点，一定是一段连续的区间，并且，区间右端点是i，那么我们只需要预处理出left[i]表示最小的可以用于更新i的位置，显然left[i]是单增的，我们直接用一个单调队列就可以维护了。
对于c限制并不是很好处理，于是我们考虑分治，对于一段区间[l, r]，我们找出其中c值最大的位置p，递归处理[l, p - 1], [p, r],单独处理最后一个区间包含p的情况。
首先比较显然的是，如果我们要求最后一个转移区间包含p，那么可以从[l, p - 1]转移的i，一定是属于[max(p, l + c[p]), r]的，然后我们来分类讨论一下。
1、left[i] < l且i <= p - 1 + c
显然满足条件的i是[l, i - c], 并且i和i + 1的可行区间只相差一个i - c + 1这个位置的贡献，那么我们可以对于第一个位置在线段树中查询，然后后面的所有直接O(1)加上贡献即可
2、left[i] < l且i > p - 1 + c
显然，满足这个条件的i的可行转移范围全部都是[l, p - 1]，那么我们只需要二分出满足这个条件的区间，然后查询[l, p - 1]的答案，之后直接给可行区间打标记即可。
3、l <= left[i] < p
这一段的left[i]都不能确定，所以只能直接在线段树里面查询
4、left[i] >= p
显然无法转移。
乍一看这不是n2logn的吗，真的可能过？
现在我们来分析一下复杂度
首先，对于情况1，一定首先有一个log，接下来考虑会扫过多少数，显然，满足情况1的区间是[max(l + c, p), min(r, p + c - 1)]，显然区间长度是小于min(p - l + 1, r - p)，相当于取被p分割的区间当中长度较小的一个。显然前面的log，一共有n层，是nlogn，后面的区间长度可以通过类似于启发式合并的思想分析，也是nlogn的。
对于情况2，显然每层只有一个，所以是nlogn
对于情况3，我们可以发现，这种情况当且仅当，改点属于区间的右边部分，但是left[i]，是在左边部分，那么显然这种情况对于每一个点，有且仅会出现一次，所以是nlogn的
所以，总的复杂度就是O(nlogn)的，当分治到l == r时，直接更新答案，然后更新到上层区间即可。
Source:
/*created by scarlyw
*/
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <set>
#include <queue>inline char read() {static const int IN_LEN = 1024 * 1024;static char buf[IN_LEN], *s, *t;if (s == t) {t = (s = buf) + fread(buf, 1, IN_LEN, stdin);if (s == t) return -1;}return *s++;
}///*
template<class T>
inline void R(T &x) {static char c;static bool iosig;for (c = read(), iosig = false; !isdigit(c); c = read()) {if (c == -1) return ;if (c == '-') iosig = true; }for (x = 0; isdigit(c); c = read()) x = ((x << 2) + x << 1) + (c ^ '0');if (iosig) x = -x;
}
//*/const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}template<class T>
inline void W(T x) {static int buf[30], cnt;if (x == 0) write_char('0');else {if (x < 0) write_char('-'), x = -x;for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;while (cnt) write_char(buf[cnt--]);}
}inline void flush() {fwrite(obuf, 1, oh - obuf, stdout);
}/*
template<class T>
inline void R(T &x) {static char c;static bool iosig;for (c = getchar(), iosig = false; !isdigit(c); c = getchar())if (c == '-') iosig = true; for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');if (iosig) x = -x;
}
//*/const int MAXN = 1000000 + 10;
const int mod = 1000000000 + 7;int n;
int c[MAXN], d[MAXN], left[MAXN], f[MAXN], g[MAXN];inline void add(int &x, int t) {x += t, (x >= mod) ? (x -= mod) : (0);
}struct node {int c_id, f, g, tag_f, tag_g;
} tree[MAXN << 2 | 1];inline void update(int &f, int &g, int cur_f, int cur_g) {if (cur_f > f) f = cur_f, g = cur_g;else if (f == cur_f) add(g, cur_g);
}inline void update(int k) {node lc = tree[k << 1], rc = tree[k << 1 | 1];tree[k].c_id = ((c[lc.c_id] > c[rc.c_id]) ? lc.c_id : rc.c_id);if (lc.f > rc.f) tree[k].f = lc.f, tree[k].g = lc.g;else if (lc.f == rc.f) tree[k].f = lc.f, tree[k].g = (lc.g + rc.g) % mod;else tree[k].f = rc.f, tree[k].g = rc.g;
}inline void modify(int k, int f, int g) {update(tree[k].f, tree[k].g, f, g);update(tree[k].tag_f, tree[k].tag_g, f, g);
}inline void push_down(int k) {if (tree[k].tag_f > -1) {modify(k << 1, tree[k].tag_f, tree[k].tag_g);modify(k << 1 | 1, tree[k].tag_f, tree[k].tag_g);tree[k].tag_f = -1, tree[k].tag_g = 0;}
}inline void build(int k, int l, int r) {tree[k].tag_f = -1, tree[k].tag_g = 0;if (l == r) {tree[k].c_id = l, tree[k].f = -1, tree[k].g = 0;return ;}int mid = l + r >> 1;build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);update(k);
}inline void modify(int k, int l, int r, int ql, int qr, int f, int g) {if (ql <= l && r <= qr) return modify(k, f, g);int mid = l + r >> 1;if (ql <= mid) modify(k << 1, l, mid, ql, qr, f, g);if (qr > mid) modify(k << 1 | 1, mid + 1, r, ql, qr, f, g);
}inline void modify(int k, int l, int r, int pos, int f, int g) {if (l == r) return modify(k, f, g);int mid = l + r >> 1;push_down(k);if (pos <= mid) modify(k << 1, l, mid, pos, f, g);else modify(k << 1 | 1, mid + 1, r, pos, f, g);
}inline void query(int k, int l, int r, int ql, int qr, int &f, int &g) {if (qr < ql) return; if (ql <= l && r <= qr) return update(f, g, tree[k].f, tree[k].g);int mid = l + r >> 1;if (ql <= mid) query(k << 1, l, mid, ql, qr, f, g);if (qr > mid) query(k << 1 | 1, mid + 1, r, ql, qr, f, g);
}inline void query(int k, int l, int r, int pos, int &f, int &g) {if (l == r) return update(f, g, tree[k].f, tree[k].g);int mid = l + r >> 1;if (pos <= mid) query(k << 1, l, mid, pos, f, g);else query(k << 1 | 1, mid + 1, r, pos, f, g);update(k);
}inline int find(int k, int l, int r, int ql, int qr) {if (ql <= l && r <= qr) return tree[k].c_id;int mid = l + r >> 1;if (qr <= mid) return find(k << 1, l, mid, ql, qr);else if (ql > mid) return find(k << 1 | 1, mid + 1, r, ql, qr);else {int pos1 = find(k << 1, l, mid, ql, qr);int pos2 = find(k << 1 | 1, mid + 1, r, ql, qr);return (c[pos1] > c[pos2]) ? pos1 : pos2; }
}inline void read_in() {R(n);for (int i = 1; i <= n; ++i) R(c[i]), R(d[i]);
}inline void pre_work() {int cur_pos = 0, head = 1, tail = 0;static int q[MAXN];for (int i = 1; i <= n; ++i) {while (head <= tail && d[q[tail]] >= d[i]) tail--;q[++tail] = i;int pos;while (head <= tail && q[head] <= cur_pos) head++;pos = d[q[head]];while (i - pos > cur_pos) {++cur_pos;while (head <= tail && q[head] <= cur_pos) head++;pos = d[q[head]];}left[i] = cur_pos;}// for (int i = 1; i <= n; ++i) std::cout << left[i] << " ";// std::cout << '\n';
}inline int binary(int x, int y, int val) {int l = x, r = y + 1;while (l + 1 < r) {int mid = l + r >> 1;(left[mid] < val) ? l = mid : r = mid;}// std::cout << "??" << l << '\n';return l;
}inline void solve(int l, int r, int k) {int start = std::max(k, l + c[k]), end1 = std::min(r, k + c[k] - 1);int cur_f = -1, cur_g = 0, st = start;while (st <= end1) {if (left[st] >= l) break ;if (left[st] >= k) return ;if (st == start) query(1, 0, n, l, st - c[k], cur_f, cur_g);else update(cur_f, cur_g, f[st - c[k]], g[st - c[k]]);if (cur_f != -1) update(f[st], g[st], cur_f + 1, cur_g);++st;}if (st > r) return ;if (left[st] < l) {int pos = binary(st, r, l);cur_f = -1, cur_g = 0;query(1, 0, n, l, k - 1, cur_f, cur_g);if (cur_f > -1) modify(1, 0, n, st, pos, cur_f + 1, cur_g);st = pos + 1;}while (st <= r) {if (left[st] >= k) return ;cur_f = -1, cur_g = 0;query(1, 0, n, left[st], std::min(k - 1, st - c[k]), cur_f, cur_g);if (cur_f > -1) update(f[st], g[st], cur_f + 1, cur_g);st++;}
}inline void solve(int l, int r) {if (r < l) return ;if (l == r) {modify(1, 0, n, l, f[l], g[l]);f[l] = -1, g[l] = 0, query(1, 0, n, l, f[l], g[l]);return ;}int pos = find(1, 0, n, l + 1, r);solve(l, pos - 1), solve(l, r, pos), solve(pos, r);
}int main() {freopen("schooldays.in", "r", stdin);freopen("schooldays.out", "w", stdout);read_in();pre_work();build(1, 0, n);for (int i = 1; i <= n; ++i) f[i] = -1;g[0] = 1, solve(0, n);// for (int i = 1; i <= n; ++i) std::cout << f[i] << " " << g[i] << '\n';if (f[n] > -1) std::cout << f[n] << " " << g[n];else std::cout << "-1";return 0;
}