CF 292E 解题报告
链接:http://www.codeforces.com/contest/292/problem/E
题意:
有两个数组a和b
每次进行两种操作
1,将a[x...x+k-1]赋值给b[y...y+k-1]
2,单点询问
算法:线段树
还是一样的线段树,只是维护的稍微麻烦一些而已...
和52C差不多吧..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<string>#include<math.h>#include<time.h>#include<vector>#include<bitset>#include<memory>#include<utility>#include<fstream>#include<stdio.h>#include<sstream>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;int a[200005];int val[1<<18];void push_down(int num,int l,int r){ if (val[num]==-1) { return; } int mid=(l+r)/2; val[num*2+1]=val[num]; val[num*2+2]=val[num]+mid-l; val[num]=-1;}void change(int num,int l,int r,int l0,int r0,int k){ if ((l0<=l)&&(r<=r0)) { val[num]=k+(l-l0); return; } push_down(num,l,r); int mid=(l+r)/2; if (l0<mid) { change(num*2+1,l,mid,l0,r0,k); if (mid<r0) { change(num*2+2,mid,r,l0,r0,k); } } else if (mid<r0) { change(num*2+2,mid,r,l0,r0,k); }}int query(int num,int l,int r,int t){ if (l==r-1) { return val[num]; } push_down(num,l,r); int mid=(l+r)/2; if (t<mid) { return query(num*2+1,l,mid,t); } else { return query(num*2+2,mid,r,t); }}int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,m; scanf("%d%d",&n,&m); int i; for (i=0;i<n+n;i++) { scanf("%d",&a[i]); } memset(val,-1,sizeof(val)); change(0,0,n,0,n,n); for (i=0;i<m;i++) { int oper; scanf("%d",&oper); if (oper==1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); x--; y--; change(0,0,n,y,y+z,x); } else { int x; scanf("%d",&x); x--; printf("%d\n",a[query(0,0,n,x)]); } } return 0;} |
评论 (0)