codeforces 292 E. Copying Data (染色问题，线段树lazy标记模板题)
x题目链接
题意：给出两个数组，每个数组n个数，分别为a和b,给出m个操作，操作有两种类型，第一种是给出x,y,k,表示从a数组的x坐标开始复制k个数到b数组的y到y+k-1。
第二种操作是给出x，询问当前b[x]是多少。
对于每个第二种操作，输出结果。
思路：第一次写lazy标记的线段树。
今天突然就顿悟了。。。其实lazy标记的思想大概就是。。
对于某段区间的更新，如果没有查询到这段区间中任何一个数的时候。。。那么这个更新其实是无所谓的。。。
（让我想到了那个脑洞，就是整个世界都是一段程序，为了让你不察觉异常并且耗费尽量少的资源，所有场景只有在有人观测的时候才会被加载，不观测就用很少的资源随便处理一下233）
所以lazy标记，也叫延迟标记，就是只有当查询到某个节点的时候，才去把之前的修改更新，不然不更新（就好像有人观测的时候，上帝才把某个场景的代码写出来）
这道题除了延迟标记这个点外，还用到了染色问题的经典做法。
所谓染色问题，这里说的是一种区间覆盖问题，每次用一个颜色覆盖某段区间，最后询问某一点是什么颜色（大概是这样...?
回到这道题，具体做法是，记录每次覆盖操作的位移差，然后用线段树维护某个点最后被覆盖的时间（也可以形象得说被染成了什么颜色，染的颜色种类和时间对应）
这样，每次询问b[x]的时候，我们可以查询x位置最后是被染成了什么颜色，然后根据之前记录的位移差信息，就可以得到相应的答案。
这是一种经典做法，这类问题具有一定普遍性，注意体会。
以及，之前对lazy标记有一个错误得认识，以为lazy是基于线段树本身数组的一个辅助数组。。。但是做完这道题后感觉。。。
之前写的单点更新的线段树数组tree和现在的lazy标记的数组应该是同等地位。。。。PushDown和PushUp大概也是同等地位。。。就是说。。。可以只出现PushDown和lazy数组不出现PushUp和tree.
还有一些写法上的注意，见代码注释。
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 06 Sep 2016 08:41:03 PM CST
4File Name :code/cf/problem/292E.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int lazy[N<<2];//lazy[i]记录的信息是以i节点为根节点的子树所表示的区间被覆盖的时间。
33int n,m;
34int q[N]; //记录覆盖信息，q[i]表示第i个覆盖的位移差。
35int a[N],b[N];
36void PushDown( int rt)
37{
38 if (lazy[rt])
39 lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
40 lazy[rt] = 0;
41}
42void update(int L,int R,int sc,int l,int r,int rt)
43{
44 if (L<=l && r<=R)
45 {
46 lazy[rt] = sc;
47 return;
48 }
49 PushDown(rt);
50 int m = (l+r)>>1;
51 if (L<=m) update(L,R,sc,lson);
52 if (R>=m+1) update(L,R,sc,rson); //如果是区间查询或者修改，那么就需要分别两个if来判断。
53}
54int query(int p,int l,int r,int rt)
55{
56 if (l==r) return lazy[rt];
57 PushDown(rt);
58 int m = (l+r)>>1;
59 if (p<=m) query(p,lson); //如果是单点查询或者修改，那么不在这个就一定在另一个，所以可以用else.
60 else query(p,rson);
61}
62int main()
63{
64 #ifndef ONLINE_JUDGE
65 freopen("code/in.txt","r",stdin);
66 #endif
67 ios::sync_with_stdio(false);//谁说cf不会卡cin了orz......
68 cin>>n>>m;
69 for ( int i = 1 ; i <= n ; i++) cin>>a[i];
70 for ( int i = 1 ; i <= n ; i++) cin>>b[i];
71 ms(lazy,0);
72 for ( int i = 1 ; i <= m; i++)
73 {
74 int opt;
75 cin>>opt;
76 if (opt==1)
77 {
78 int x,y,k;
79 cin>>x>>y>>k;
80 q[i]=x-y;//记录覆盖的位移，查询的时候用。
81 update(y,y+k-1,i,1,n,1);
82 }
83 else
84 {
85 int x;
86 cin>>x;
87 int markid = query(x,1,n,1); //查询返回当前节点x最后是在哪个时间被覆盖，如果返回0，说明没有被覆盖。
88 if (markid) cout<<a[x+q[markid]]<<endl; else cout<<b[x]<<endl;
89 }
90 }
91 #ifndef ONLINE_JUDGE
92 fclose(stdin);
93 #endif
94 return 0;
95}