Codeforces 238D: Tape Programming
1. 题目大意
有一种编程语言，在这个语言下一个程序是由数字和“<”，“>”构成的非空串。程序运行时有一个指针。初始时指针指向最左字符，移动方向为向右。
我们重复以下操作：
1. 如果指针指向的位置是一个数字，输出这个数字，然后将指针沿原来的移动方向移动，同时将原来的数字减1，如果数字为0则删除；
2. 如果指针指向的位置是“<”或“>”，那么指针的移动方向对应修改，接着沿着新的移动方向移动。如果新的位置也是“<”或“>”，则删除原来位置上的字符；
3. 如果指针指向串外就停止运行。
现在我们有一个长度为\(n\)且由数字和“<”，“>”构成的串\(s\)，你需要回答\(q\)个询问，每个询问给出一段区间\([l, r]\)，你要求出如果把区间\([l, r]\)内的\(s\)看成一个单独的程序，每个数字会被输出多少次。
2. 数据范围
\( 1 \le n, q \le 10^5 \)
3. 题解
容易发现这个语言下指针的移动是连续的，也就是说，如果在程序的左侧添加足够多的“>”，那么将某个区间作为单独的程序执行的过程一定是执行整个程序的过程的一部分。
记录\(f[i][j]\)表示第\(i\)个位置第一次被访问到之前数字\(j\)被输出了多少次，\(g[i][j]\)表示第\(i\)个字符在指针准备向左移走时数字\(j\)被输出了多少次。考虑到查询一段区间时程序一定是从左端点开始执行，但有可能从左边或右边出去，我们可以比较一下左端点的\(g\)值和右端点的\(f\)值，然后做一个前缀和得到结果。
易知程序的运行次数是\(O(nd)\)的（其中\(d\)是数字的大小），那么我们可以直接用双向链表模拟程序的执行过程得到\(f\)和\(g\)。
4. 时空复杂度
时间复杂度：\( O((n + q)d) \)
空间复杂度：\( O(nd) \)
5. 代码
代码在这里。
