2
1 1
2 1 2
2
1 3
1
1
对于这道绊倒我2小时的题，有必要记录一下。
将所有操作的产生数存入g，g有三个值（val,loc,sum）
二分。对于1操作，直接在末端插入一个值val，并记录一下他的位置loc；然后2操作，先找到a位置的值val，假设2操作之前文档有tmp个数，2操作之后最后一个位置就是tmp+a*b，在这个位置的值就是val，然后记录一个sum表示这个点前面是前sum个值重复。对于每个位置的值的访问就用二分，比如找x位置的值，在存储的序列（struct存储）中找到第一个loc（在文档中的位置）不小于x的元素g[i]，如果这个元素的loc刚好就是x，那就返回这个元素的值val；如果loc不等于x，在(g[i-1].loc,g[i].loc]这个区间里就是重复的前g[i].sum个值，所以接下来找(x-g[i-1].loc)%g[i].sum这个位置的值，反复进行，直到找到的loc==x。
严重教训：开long long??
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int N = 110009; 5 typedef long long LL; 6 struct Node 7 { 8 LL val, loc, sum; 9 }g[N]; 10 LL cnt, tmp; 11 int n, m; 12 int find(LL x) 13 { 14 int p = 1, l = 1, r = cnt; 15 while(l <= r) 16 { 17 int mid = (l + r) >> 1; 18 if(g[mid].loc >= x) 19 p = mid, r = mid - 1; 20 else l = mid + 1; 21 } 22 return p; 23 } 24 int query(LL x) 25 { 26 int p = find(x); 27 if(g[p].loc == x) 28 return g[p].val; 29 int nex = x - g[p-1].loc; 30 if(nex % g[p].sum != 0) 31 return query(nex%g[p].sum); 32 else return query(g[p].sum); 33 } 34 void func1() 35 { 36 int x; 37 scanf("%d", &x); 38 ++tmp; 39 g[++cnt] = (Node){x, tmp, tmp}; 40 } 41 void func2() 42 { 43 LL a, b; 44 scanf("%lld%lld", &a, &b); 45 tmp += a * b; 46 int val = query(a); 47 g[++cnt] = (Node){val, tmp, a}; 48 } 49 int main() 50 { 51 //freopen("in.in", "r", stdin); 52 //freopen("my.out", "w", stdout); 53 scanf("%d", &n); 54 for(int i = 1; i <= n; i++) 55 { 56 int x; 57 scanf("%d", &x); 58 if(x == 1) func1(); 59 else func2(); 60 } 61 scanf("%d", &m); 62 for(int i = 1; i <= m; i++) 63 { 64 LL p; 65 scanf("%lld", &p); 66 printf("%d\n", query(p)); 67 } 68 return 0; 69 }
原文：https://www.cnblogs.com/Jony-English/p/12662793.html
