題目大意：兩個數組，a和b，兩種操作：
1：將數組a的區間[x,x+k-1]復制給數組b的區間[y,y+k-1]。
2：問當前b[x]的值。
思路：這道題可以用線段樹做，在線段樹中維護以下值：sta，stb，這兩個值只有在線段樹的葉子節點才有意義，對於一個位置po，（也就是線段[po,po]，它是線段樹的葉子節點），sta為0表示這個位置還沒有被a覆蓋，保持原來的值，否則，sta表示位置po已被覆蓋，且是被a[sta]~a[sta+k-1]覆蓋。stb為0和sta類似，不為0表示該位置是從stb開始被覆蓋的。下面舉個例子。
比如我們進行操作1，將a[x]~a[x+k-1]的值復制給數組b的區間[y,y+k-1],那麼我們將線段樹中區間[y,y+k-1]中的sta賦值為x,將stb賦值為y。
那麼對於操作1,：1,x,y,k，我們就將區間[y,y+k-1]中的sta，stb分別賦值為x,y.
對於操作2:2,po 我們得到位置po的值為sta和stb，若sta為0，則輸出b[po]即可，否則輸出a[po-stb+sta]即可。
代碼如下：
[cpp]
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct tree
{
int l,r;
int sta,stb;
}t[maxn<<2];
int a[maxn],b[maxn];
void pushdown(int p)
{
if(t[p].sta)
{
t[ls].sta=t[p].sta;
t[ls].stb=t[p].stb;
t[rs].sta=t[p].sta;
t[rs].stb=t[p].stb;
t[p].sta=0;
}
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].sta=t[p].stb=0;
if(l==r)
return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int p,int l,int r,int sta,int stb)
{
if(t[p].l==l&&t[p].r==r)
{
t[p].sta=sta;
t[p].stb=stb;
return;
}
pushdown(p);
if(r<=mid)
change(ls,l,r,sta,stb);
else if(l>mid)
change(rs,l,r,sta,stb);
else
{
change(ls,l,mid,sta,stb);
change(rs,mid+1,r,sta,stb);
}
}
struct node
{
int sta,stb;
};
node query(int p,int x)
{
node tmp;
if(t[p].l==t[p].r)
{
tmp.sta=t[p].sta,tmp.stb=t[p].stb;
return tmp;
}
pushdown(p);
if(x>mid)
return query(rs,x);
return query(ls,x);
}
int main()
{
freopen("dd.txt","r",stdin);
int n,q,i;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
build(1,1,n);
while(q--)
{
int t,x,y,z;
scanf("%d",&t);
if(t==1)
{
scanf("%d%d%d",&x,&y,&z);
change(1,y,y+z-1,x,y);
}
else
{
scanf("%d",&x);
node tmp=query(1,x);
if(tmp.stb==0)
printf("%d\n",b[x]);
else
printf("%d\n",a[x-tmp.stb+tmp.sta]);
}
}
return 0;
}
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct tree
{
int l,r;
int sta,stb;
}t[maxn<<2];
int a[maxn],b[maxn];
void pushdown(int p)
{
if(t[p].sta)
{
t[ls].sta=t[p].sta;
t[ls].stb=t[p].stb;
t[rs].sta=t[p].sta;
t[rs].stb=t[p].stb;
t[p].sta=0;
}
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].sta=t[p].stb=0;
if(l==r)
return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int p,int l,int r,int sta,int stb)
{
if(t[p].l==l&&t[p].r==r)
{
t[p].sta=sta;
t[p].stb=stb;
return;
}
pushdown(p);
if(r<=mid)
change(ls,l,r,sta,stb);
else if(l>mid)
change(rs,l,r,sta,stb);
else
{
change(ls,l,mid,sta,stb);
change(rs,mid+1,r,sta,stb);
}
}
struct node
{
int sta,stb;
};
node query(int p,int x)
{
node tmp;
if(t[p].l==t[p].r)
{
tmp.sta=t[p].sta,tmp.stb=t[p].stb;
return tmp;
}
pushdown(p);
if(x>mid)
return query(rs,x);
return query(ls,x);
}
int main()
{
freopen("dd.txt","r",stdin);
int n,q,i;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
build(1,1,n);
while(q--)
{
int t,x,y,z;
scanf("%d",&t);
if(t==1)
{
scanf("%d%d%d",&x,&y,&z);
change(1,y,y+z-1,x,y);
}
else
{
scanf("%d",&x);
node tmp=query(1,x);
if(tmp.stb==0)
printf("%d\n",b[x]);
else
printf("%d\n",a[x-tmp.stb+tmp.sta]);
}
}
return 0;
}
