原题地址：
让期末考试整的好久没有写题， 放假之后由于生病也没怎么做，新年的第一场CF也不是那么在状态，只过了div2的前两道题，第三题想到算法但是太困了没写对，刚刚把第三题A了很兴奋，赶快过来把解题报告写了。不得不说这道题还算有点水平
题目大意：
维护一个初始为空的序列，支持两种操作，共 m 个(1 <= m <= 10 ^ 5)：
1 将一个数插入到数列的尾端（插入的数不大于10 ^ 5）
2 将数列的前 l 位复制 c 次，贴到数列的尾端（1 <= l <= 10 ^ 5, 1 <= c <= 10 ^ 4）
然后进行 n (1 <= n <= 10 ^ 5)次查询，每次给出一个数 x ，输出最终数列的第x位（所有查询数满足严格递增）
题目满足数据合法
题目分析：
这道题给人的第一反应是数据规模很大，直接模拟生成数列不仅会超时，而且会爆系统内存(最多大概可以有 10 ^ 9个数)，所以我们着手去想其他的解题思路。
首先想到的是处理出每一个操作所生成的数列的位置（包括起始位置和终止位置）然后按照查询给出的位置 x 在操作序列中二分查找出生成包含 x 这一段的操作的位置，根据这个操作去计算位置x上的值。但是这样要考虑到一件事，如果生成 x 的操作是操作 2 ， 那么由于操作 2 是复制当前数列的前l个数，而当前数列仍旧是未知的，也就是说我们还是需要再在前面的操作中二分，知道查到一个由操作一生成的点。这种做法直接导致复杂度无法估计，而且递归的编程难度加大，想法有点难实现。
接下来我们从范围入手，注意到操作二只会用到当前数列的前10 ^ 5个点，而数列中的点是不会修改的，所以我们萌生了这种想法：模拟出数列的前10 ^ 5个点，然后再查找生成 x 的对应操作。这样问题就简化很多了。
模拟之后的查找有两种方案，第一种还是二分，复杂度O(n log n)没问题，但是写起来稍微麻烦。后一种方法用到了题目中查询序列的递增顺序，直接线性地从先往后扫就行，复杂度是O(n + m)
细节处理：
1. 注意边界条件和循环退出条件
2.如果当前查到的点的位置小于10 ^ 5 直接输出模拟出来的数列中的对应位置值就可以了。
3.如果查到的位置对应操作为操作1，直接输出操作一的操作数值，如果为操作二需要计算一下取模（详见代码），特别注意取模得零的情况
1 //date 20140114 2 #include3 #include 4 #include 5 6 using namespace std; 7 8 const int maxm = 100005; 9 10 inline int getint()11 {12 int ans(0); char w = getchar();13 while('0' > w || w > '9')w = getchar();14 while('0' <= w && w <= '9')15 {16 ans = ans * 10 + w - '0';17 w = getchar();18 }19 return ans;20 }21 22 int n, m;23 struct build24 {25 int ord, x, l, c;26 long long a, b;27 }hell[maxm];28 int sq[maxm];29 30 int main()31 {32 m = getint();33 for(int i = 1; i <= m; ++i)34 {35 hell[i].ord = getint();36 if(hell[i].ord == 1){37 hell[i].x = getint(); 38 hell[i].a = hell[i].b = hell[i - 1].b + 1LL;39 if(hell[i].a < maxm)sq[hell[i].a] = hell[i].x;40 }41 else{42 hell[i].l = getint(); hell[i].c = getint();43 hell[i].a = hell[i - 1].b + 1LL;44 hell[i].b = hell[i - 1].b + (long long)hell[i].l * (long long)hell[i].c;45 if(hell[i].a < maxm)46 {47 int now = hell[i].a;48 for(int j = 1; j <= hell[i].c && now < maxm; ++j)49 for(int k = 1; k <= hell[i].l && now < maxm; ++k)50 sq[now++] = sq[k];51 }52 }53 }54 55 n = getint();56 int h = 1; long long x;57 for(int i = 1; i <= n; ++i)58 {59 cin >> x;60 while(!(hell[h].a <= x && hell[h].b >= x))++h;61 if(x <= 100000)printf("%d ", sq[x]);62 else{63 if((x - hell[h - 1].b) % (long long)hell[h].l != 0)64 cout << sq[(x - hell[h - 1].b) % (long long)hell[h].l] << ' ';65 else cout << sq[hell[h].l] << ' ';66 }67 }68 return 0;69 }
总结：
这题就是想法和细节以及编程能力。