【日常小测】三明治

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

假如我们钦定某个格子先取走靠左的三角形,那么其余格子是先取走靠左还是靠右就全部定下来了
于是我们暴力枚举一下,复杂度是$O(n^4)$

更进一步,我们发现:

假如我们钦定先取走$(x, y)$这个格子的靠左三角形
那么我们一定得先将$(x – 1, y)$这个格子的左三角形取走,然后再取走一些其他的三角形

于是同一行的信息是可以共用的,然后就可以记忆化搜索了
时间复杂度是$O(n^3)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500;
const int INF = 1e7;

char mp[N][N];
int n, m, ans[N];
bool up[N][N], dw[N][N], InStack[N][N], vis[N][N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int F(int x, int y, int t) {
	InStack[y][x] = 1;
	int nx = x + (t == 1? 1: -1), ny = y, nt = t, ret = 1;
	ret += vis[ny][nx]? 0: (InStack[ny][nx]? INF: F(nx, y, t));
	nx = x; ny = up[y][x] == t? y - 1: y + 1; nt = up[y][x] == t? up[ny][nx]: dw[ny][nx];
	ret += vis[ny][nx] || ret >= INF? 0: (InStack[ny][nx]? INF: F(nx, ny, nt));	
	vis[y][x] = 1;
	InStack[y][x] = 0;
	return ret > INF? INF: ret;
}

inline void init() {
	memset(vis, 0, sizeof(vis));
	for (int j = 1; j <= m; j++) {
		vis[j][0] = 1;
		vis[j][n + 1] = 1;
	}
	for (int i = 1; i <= n; i++) {
		vis[0][i] = 1;
		vis[m + 1][i] = 1;
	}
}

int main() {
	m = read(); n = read();
	for (int j = 1; j <= m; j++) {
		scanf("%s", mp[j] + 1);
		for (int i = 1; i <= n; i++) {
			up[j][i] = 1;
			dw[j][i] = 0;
			if (mp[j][i] == 'Z') {
				swap(up[j][i], dw[j][i]);
			}
		}
	}
	for (int j = 1; j <= m; j++) {
		init();
		for (int i = n; i; i--) {
			ans[i] = ans[i + 1] < INF? F(i, j, 1) + ans[i + 1]: INF;
		}
		init();
		for (int i = 1; i <= n; i++) {
			ans[i] = min(ans[i], ans[i - 1] < INF? F(i, j, 0) + ans[i - 1]: INF);
			printf("%d ", ans[i] >= INF? -1: ans[i] << 1);
		}
		putchar('\n');
	}
	return 0;
}

【BZOJ 2471】Count

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解:http://www.cnblogs.com/clrs97/p/5993606.html

解题报告

我们考虑从高位开始,逐位枚举。那么每枚举一位相当于将序列划分为10分,并且取其中一份。
对于一段连续的序列来讲,我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的,于是我们可以记忆化搜索。

另外这题很容易扩展到:“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里,不知道有没有人能切掉

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;
 
int n, m, nxt[M];
char s[M];
struct Transfer{
    LL pos, cnt;
    inline Transfer() {
    }
    inline Transfer(LL a, LL b):pos(a), cnt(b) {
    }
    inline Transfer operator + (const Transfer &T) {
        return Transfer(T.pos, cnt + T.cnt);
    }
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
    int HashVal;
    Transfer t[M];
    inline void GetHashVal() {
        const static int MOD = 1000000007;
        const static int SEED1 = 13, SEED2 = 131;
        HashVal = 0;
        for (int i = 0; i < m; i++) {
            HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
        }
    }
    inline bool operator < (const MatchStatus &MS) const {
        return HashVal < MS.HashVal;
    }
};
 
inline Transfer DFS(int w, int p, const MatchStatus &cur) {
    if (w <= 0) {
        return cur.t[p];
    } else if (f[w][p].count(cur.HashVal)) {
        return f[w][p][cur.HashVal];
    } else {
        Transfer ret(p, 0);
        for (int i = 0; i < SGZ; i++) {
            MatchStatus nw = cur;
            for (int j = 0; j < m; j++) {
                nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
            }
            nw.GetHashVal();
            ret = ret + DFS(w - 1, ret.pos, nw);
        }
        return f[w][p][cur.HashVal] = ret;
    }
}
 
int main() {
    while (~scanf("%d %s", &n, s + 1) && n) {
        m = strlen(s + 1);
        for (int i = 1; i <= m; i++) {
            s[i] -= '0';
        }
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
            for (; j && s[j + 1] != s[i]; j = nxt[j]);
            j += s[j + 1] == s[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < SGZ; j++) {
                int k = i;
                for (; k && s[k + 1] != j; k = nxt[k]);
                k += s[k + 1] == j;
                t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                f[i][j].clear();
            }
        }
        Transfer ans(0, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < SGZ; j++) {
                MatchStatus cur;
                for (int k = 0; k < m; k++) {
                    cur.t[k] = t[k][j];
                }
                cur.GetHashVal();
                ans = ans + DFS(i - 1, ans.pos, cur);
            }
        }
        printf("%lld\n", ans.cnt);
    }
    return 0;
}

【TopCoder SRM713】PowerEquation

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

【BZOJ 3990】[SDOI2015] 排序

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3990
神犇题解:http://blog.csdn.net/regina8023/article/details/45503151

解题报告

最开始一眼看成神题,还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块,并且$2$的不同次幂之间不会相互影响
话一句话来说,考虑交换长度为$2^k$的块时,所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块,只能有至多两块位置不对
于是我们搞一发$DFS$就好了,时间复杂度:$O(n \log n)$

【BZOJ 3811】玛里苟斯

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html

解题报告

这题这么神,我们来分情况讨论:

1. $k = 1$

这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:

如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$

证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D

于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$

2. $k = 2$

这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$

因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:

如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$

于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$

3. $k \ge 3$

我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:

不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D

所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$

【日常小测】tree

题目大意

给定一棵大小为$n(n \le 3000)$的树,带边权
请你给出一个长度为$k(k \le n)$的序列$\{a_i\}$
要求序列中两两元素不同,请你最小化$\sum\limits_{i=1}^{k-1}{dis(a_i,a_{i+1})}$

解题报告

我们看一看这个式子可以发现实际上是要我们给出一个大小为$k$的连通块
问你这个连通块内的边权乘上$2$再减掉直径的最小值是多少

于是我们定义$h_{i,j}$为$i$的子树中选$j$个点,还没有考虑直径的最小花费
$f_{i,j}$表示在$i$的子树里,选$j$个点,直径包含$i$的最小花费
$g_{i,j}$表示在$i$的子树里,选$j$个点,已经考虑过直径且直径不包含$i$的最小花费
然后我们暴力$DP$就可以了

我们的时间复杂度是$T(n)=\sum\limits_{i}{\sum\limits_{fa_i=fa_j}{size_i \cdot size_j}}$
仔细想一想的话,每一堆点只会在$LCA$处被计算,时间复杂度是$O(n^2)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N << 1;
const LL INF = 1e18;

int n,k,head[N],nxt[M],to[M],cost[M],sz[N];
LL vout=INF,f[N][N],g[N][N],h[N][N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void update(int w, int fa) { 
	fill(f[w], f[w]+1+N, INF);
    fill(g[w], g[w]+1+N, INF);
	fill(h[w], h[w]+1+N, INF);
	f[w][1] = g[w][1] = h[w][1] = 0; sz[w] = 1;
	for (int i=head[w],t;i;i=nxt[i]) {
		if ((t=to[i]) != fa) {
			update(to[i], w); 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					g[w][x+j] = min(g[w][x+j], g[w][x] + h[t][j] + tmp);
					g[w][x+j] = min(g[w][x+j], f[w][x] + f[t][j] + cost[i]);
					g[w][x+j] = min(g[w][x+j], h[w][x] + g[t][j] + tmp);
				}
			}
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) {
					f[w][x+j] = min(f[w][x+j], h[w][x] + f[t][j] + cost[i]);
					f[w][x+j] = min(f[w][x+j], f[w][x] + h[t][j] + tmp);
				}
			} 
			for (int x=sz[w],tmp=cost[i]<<1;x;x--) {
				for (int j=1;j<=sz[t];j++) 
					h[w][x+j] = min(h[w][x+j], h[w][x] + h[t][j] + tmp);
			} 
			sz[w] += sz[t];
		}	
	}
	vout = min(vout, f[w][k]);
	vout = min(vout, g[w][k]); 
}

int main() {
	n = read(); k = read();
	for (int i=2,u,v;i<=n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read());
	}
	update(1, 1);
	printf("%lld\n",vout);
	return 0;
}

【日常小测】资源采集

题目大意

给定一棵$n(n \le 52501)$个点的树,初始状态下,每一结点存储的能量为$0$
树上每一个点有两个属性$v_i,l_i$分别表示这个点每单位时间产生的能量,和这个点的存储能量的上限
再给定$q(q\le52501)$个操作,每个操作有三个属性$w_i,d_i,t_i$,表示
在$t_i$的时刻,遍历在$w_i$的子树中且与$w_i$距离不超过$d_i$的点,并收集这些点的能量
一个点的能量被收集后就会清空,询问每次操作能够收集到多少能量

解题报告

先来说一说链上的情况,我们定义$last_i$为$i$号点上一次被收集的时间
我们可以把相邻的且$last_i$相同的点合并在一起,然后询问的时候用函数式线段树来回答
如果还有什么问题的话,我们可以戳这个题:市场

现在考虑树上的情况,我们先搞出DFS序,将其作为一个点的横坐标
然后我们把深度作为这个点的纵坐标,然后把这个点扔到平面上
这样单次操作就是对于一个平面上的矩形进行操作
这个是经典的$Kd-Tree$的应用,可以做到单次操作只影响到$\sqrt{n}$个结点
于是将$Kd-Tree$子树中$last_i$相同的点合在一起,打一个标记
单次操作最多增加$\sqrt n$个标记,而每一次在$Kd-Tree$上走一次就会回收一个标记
于是总的操作次数为$q\sqrt n$的
当然我们也需要用平衡树的启发式合并,或者函数式线段树来支持询问
于是总的时间复杂度为:$O(q \sqrt n \log n)$

不过众所周知,这题的暴力是$O(nq)$的
所以非递归的暴力跑得飞快,两秒的题目暴力可以卡到一秒以内
所以考完改题的时候,所有改了的人都是用的暴力……

【日常小测】市场

相关链接

题目传送门:https://ly.men.ci/problem/196

题目大意

搞一个数据结构来维护一个长度为$n(n \le 10^5)$的序列。
并进行$m(m \le 10^5)$个操作,操作分为以下四种:

  1. 区间加$c(-10^4 \le c \le 10^4)$
  2. 区间除$d$。即对于单个元素$a_i$,除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
  3. 询问区间和
  4. 询问区间最值

解题报告

考虑将所有的相邻的并且值相同的位置合成一个块
考虑一次修改操作最多增加两个块,于是总的块数不会超过$n+m$
那么对于操作二,我们暴力应用到区间的每一个块上
因为每一个块最多进行$\log val$次的操作二就会消失
所以总的操作次数不会超过$O ((n+m) \log (10^4))$

现在考虑具体实现
不嫌麻烦的话,我们可以使用$Splay$。脑袋里想想还是很好写的
要好写一点的话,我们就用线段树,记录一下一个点的子树中所有的值是否相等

相关拓展

这种将相同值合并到一起来保证复杂度的题目还在雅礼集训的时候见过一次啊
当时是要求将编号$l \to r$的结点的父亲全部设为$x$,然后单点修改权值,查询某个点的子树和
也是将$fa$相同的点搞在一起,然后用$Splay$维护一下

【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4725
神犇题解:http://blog.csdn.net/lych_cys/article/details/53455978

解题报告

这题看上去一脸不可做QwQ
前前后后想了差不多三个小时吧?
突然反应过来:从第63项开始$a(x)$就大于$10^9$了
换一句话来说:之后的每一项,只可能减去前一项才可能小于$10^9$

于是我们把前$63$项之内的拿出来暴力搞一搞
$63$项之后的,我们可以推公式推出来答案是多少

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void insert(int w) {
	for (int i=w-1;i;i--) {
		if (abs(f[w]-f[i]) >= N) break;
		vis[abs(f[w]-f[i])] = 1;
	}
} 

inline int query() {
	for (int i=1;i;i++)
		if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				L[id] = i; R[id] = j;
				return;
			}
		}
	}
}

inline void query(int w) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				cout<<j<<' '<<i<<endl;
				return;
			}
		}
	}
}

int main() {
	f[1] = 1; f[2] = 2; vis[1] = 1;
	for (int i=3;i<=120;i++) { 
		if (i&1) f[i] = f[i-1] << 1;
		else f[i] = f[i-1] + query();
		insert(i);
	} 
	for (int j=2;j<=63;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] > 1e9) continue;
			que[++tot] = f[j] - f[i];
		}
	} 
	que[++tot] = (1e9) + 10;
	sort(que+1, que+1+tot);
	for (int i=1;i<tot;i++) Get_Ans(que[i], i); 
	for (int q=read(),x,p;q;q--) {
		x = read();
		p = lower_bound(que+1, que+1+tot, x) - que;
		if (que[p] == x) printf("%d %d\n",R[p], L[p]);
		else if (x <= 90) query(x);
		else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
	}
	return 0;
}

【Codeforces 781E】Andryusha and Nervous Barriers

相关链接

题目传送门:http://codeforces.com/contest/781/problem/E
代码参考:http://codeforces.com/contest/781/submission/25269119

解题报告

这题我们先考虑没有墙会害怕的版本
这样的话,我们想象一下是墙冲向一排点
于是搞一个线段树支持区间赋值,区间查询就可以了!

现在考虑加上害怕的限制
那我们可以用二维线段树!
但好难写QwQ ←这货写到一半就弃坑了

于是就去看别人的代码
然后看到了毛爷爷的代码 (毛爷爷这场暴跌 默哀 _(:з」∠)_
然后发现这题又可以暴力………

我们考虑将每一次分开的点打成一包
算上最开始的,不难发现总共只有$O(w+2n)$个包
那每一个包我们插到线段树中,此时总包数是$O((w+2n) \log (w+2n))$的
那么每一次查询我们就暴力每一个节点,于是均摊的复杂度仍然是$O(\log n)$的
代码好写还跑得飞快!

这种有一点暴力思想的数据结构题,我还真的是一点想不出来啊!
比如BZOJ 4712,真的是一点都没往那边想啊!
我一定要在科技树上点亮这个技能!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000;
const int M = 200009;
const int MOD = 1000000007;

int hit,wid,n,cnt;
struct Pack{int h,sum,del;}p[N];
struct Wall{int h,l,r,s;}wall[M];

class Segment_Tree{
	int ans_tmp,tot,root,ch[M][2];
	stack<int> s[M];
	public:
		inline void insert(int p, int id) {
			insert(root, 1, wid, p, id);
		}
		inline int query(int h, int l, int r) {
			ans_tmp = 0; 
			query(root, 1, wid, l, r, h);
			return ans_tmp;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++tot; s[w].push(v);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}
		}
		void query(int w, int l, int r, int L, int R, int h) {
			if (L <= l && r <= R) {
				while (!s[w].empty() && p[s[w].top()].h <= h) {
					if (!p[s[w].top()].del) {
						p[s[w].top()].del = 1;
						(ans_tmp += p[s[w].top()].sum) %= MOD;	
					} s[w].pop();
				}
			} else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, h);
				if (mid <= R) query(ch[w][1], mid, r, L, R, h);
			}
		}
}SGT;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	hit = read(); wid = read(); n = read();
	for (int i=1;i<=n;i++) {
		wall[i].h = read();
		wall[i].l = read();
		wall[i].r = read();
		wall[i].s = read();
	}
	for (int i=1;i<=wid;i++) {
		p[++cnt].h = hit + 1;
		p[cnt].sum = 1;
		SGT.insert(i, cnt); 
	} 
	sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;});
	for (int i=1,h_mx,tmp;i<=n;i++) { 
		tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r);
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1);
		else SGT.insert(wall[i].l-1, cnt-1);
		if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt);
		else SGT.insert(wall[i].r+1, cnt);
	}
	int vout = 0;
	for (int i=1;i<=cnt;i++) 
		(vout += (p[i].del ^ 1) * p[i].sum) %= MOD;
	printf("%d\n",vout);
	return 0;
}