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.

还有一些写法上的注意，见代码注释。

/* ***********************************************
Author :111qqz
Created Time :Tue 06 Sep 2016 08:41:03 PM CST
File Name :code/cf/problem/292E.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int lazy[N<<2];//lazy[i]记录的信息是以i节点为根节点的子树所表示的区间被覆盖的时间。
int n,m;
int q[N]; //记录覆盖信息，q[i]表示第i个覆盖的位移差。
int a[N],b[N];
void PushDown( int rt)
{
    if (lazy[rt])
    lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
    lazy[rt] =  0;
}
void update(int L,int R,int sc,int l,int r,int rt)
{
    if (L<=l && r<=R)
    {
	lazy[rt] = sc;
	return;
    }
    PushDown(rt);
    int m = (l+r)>>1;
    if (L<=m) update(L,R,sc,lson);
    if (R>=m+1) update(L,R,sc,rson); //如果是区间查询或者修改，那么就需要分别两个if来判断。
}
int query(int p,int l,int r,int rt)
{
    if (l==r) return lazy[rt];
    PushDown(rt);
    int m = (l+r)>>1;
    if (p<=m) query(p,lson);  //如果是单点查询或者修改，那么不在这个就一定在另一个，所以可以用else.
    else query(p,rson);
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	ios::sync_with_stdio(false);//谁说cf不会卡cin了orz......
	cin>>n>>m;
	for ( int i = 1 ; i <= n ; i++) cin>>a[i];
	for ( int i = 1 ; i <= n ; i++) cin>>b[i];
	ms(lazy,0);
	for ( int i = 1 ; i <=  m; i++)
	{
	    int opt;
	    cin>>opt;
	    if (opt==1)
	    {
		int x,y,k;
		cin>>x>>y>>k;
		q[i]=x-y;//记录覆盖的位移，查询的时候用。
		update(y,y+k-1,i,1,n,1);
	    }
	    else
	    {
		int x;
		cin>>x;
		int markid = query(x,1,n,1); //查询返回当前节点x最后是在哪个时间被覆盖，如果返回0，说明没有被覆盖。
		if (markid) cout<<a[x+q[markid]]<<endl; else cout<<b[x]<<endl;
	    }
	}
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}