51nod 1422 沙拉酱前缀

http://www.51nod.com/onlineJudge/questionCode.html#problemId=1422&noticeId=399940

题意：

思路：

先把所有步骤存起来，对于每次查询，二分结果。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 1e5+5;
 6 
 7 int op[maxn][3];
 8 long long d[maxn];
 9 
10 template <class T>
11 inline void scan_d(T &ret)
12 {
13     char c;
14     ret = 0;
15     while ((c = getchar()) < '0' || c > '9');
16     while (c >= '0' && c <= '9')
17     {
18         ret = ret * 10 + (c - '0'), c = getchar();
19     }
20 }
21 
22 int main()
23 {
24     //freopen("in.txt","r",stdin);
25     int m;
26     scan_d(m);
27     d[0] = 0;
28     for(int i=1;i<=m;i++)
29     {
30         scan_d(op[i][0]);
31         if(op[i][0]==1)
32         {
33             scan_d(op[i][1]);
34             d[i] = d[i-1]+1;
35         }
36         else
37         {
38             scan_d(op[i][1]);
39             scan_d(op[i][2]);
40             d[i] = d[i-1]+(long long)op[i][1]*op[i][2];
41         }
42     }
43     int n;
44     long long x;
45     scan_d(n);
46     while(n--)
47     {
48         scanf("%lld",&x);
49         while(true)
50         {
51             int pos = lower_bound(d+1,d+m+1,x)-d;
52             if(op[pos][0]==1)
53             {
54                 printf("%d ",op[pos][1]);
55                 break;
56             }
57             else x = (x-d[pos-1]-1)%op[pos][1]+1;
58         }
59     }
60     printf("
");
61     return 0;
62 }