ACM: Copying Data 线段树-成段更新-解题报告

#include"iostream"
#include"algorithm"
#include"cstdio"
#include"cmath"
#include"cstring"
#define MX 110000
#define INF 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
/*题目没看懂百度了题意和思路：
给你两个数字序列a[]和lazy[]，有两种操作，
一种是把起点为xi,长度为k的a[]的一段复制给以yi为起点，长度为k的lazy[]
还有一种操作是询问当前lazy[x]的数字是什么。思路：
这道题可以用线段树成段更新做，属于染色一类线段树题目
可以这么想，对于任意一个数，记录它有没有被a[]的其中一段覆盖了
如果被覆盖了，可以记录它被覆盖的a[]的那段的起点st以及lazy[]被覆盖的起点ed
如果被覆盖，那么最后结果就是a[x1+ed-st]。st表示这一线段是否被a[]数组覆盖，如果没有覆盖，那么st=0
如果覆盖，那么被a[]覆盖的区间范围是a[st]~a[st+k-1],ed同理,只不过记录的是lazy[]的开始位置。对于操作1，输入x1,y1,k,只要使得区间[y1,y1+k-1]的st变成x1,ed变成y1.
对于操作2，输入x1,在线段树中寻找，如果这一点(即[x1,x1])的st是0，就输出c[x1]，否则输出a[x1+ed-st].*/int a[MX],b[MX];
int st1,st2;
int k;
struct tree {
int l,r,st,ed;
} lazy[MX<<2];void Build(int l,int r,int rt) {
lazy[rt].l=l;//标记每个的位置
lazy[rt].r=r;
lazy[rt].st=lazy[rt].ed=0; //清空左右标记
if(l==r)return;
int m=(l+r)>>1;
Build(lson);
Build(rson);
}void PushDown(int rt){
if(lazy[rt].st!=-1) { //如果节点发生的变化
lazy[rt<<1].st=lazy[rt<<1|1].st=lazy[rt].st;//标记下移
lazy[rt<<1].ed=lazy[rt<<1|1].ed=lazy[rt].ed;
lazy[rt].st=lazy[rt].ed=-1;
}
}void UpData(int x1,int y1,int l,int r,int rt) {
if(lazy[rt].st==x1 && lazy[rt].ed==y1)return; //如果节点的变化重复，直接返回
if(lazy[rt].l==l && lazy[rt].r==r) { //如果查询到了目标的lazy点
lazy[rt].st=x1; //将lazy点的左右端点更新
lazy[rt].ed=y1;
return;
}
PushDown(rt);
int m=(lazy[rt].l+lazy[rt].r)>>1;
if(r<=m) UpData(x1,y1,l,r,rt<<1); //如果中点在右边，向左查询更新
else if(l>m) UpData(x1,y1,l,r,rt<<1|1); //如果中点在左边，向右查询更新
else {
UpData(x1,y1,lson); //如果中点在中间，向两边去更新
UpData(x1,y1,rson);
}
}void Query(int x,int rt) {
if(lazy[rt].st!=-1) {
st1=lazy[rt].st; //【一开始用的是 tree 类型函数返回 一个节点，蜜汁出错。最后还是换成全局整型来标记。】
st2=lazy[rt].ed;
return;
}
int m=(lazy[rt].l+lazy[rt].r)>>1;
if(x<=m) Query(x,rt<<1);
else Query(x,rt<<1|1);
}int main() {
int n,m,op,x,x1,y1;
while(~scanf("%d%d",&n,&m)) {
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
for(int i=1; i<=n; i++) {
scanf("%d",&b[i]);
}
Build(1,n,1);
while(m--) {
scanf("%d",&op);
if(op==1) {
scanf("%d%d%d",&x1,&y1,&k);
UpData(x1,y1,y1,y1+k-1,1);
} else if(op==2) {
scanf("%d",&x);
st1=st2=0;
Query(x,1);
if(st1==0) {
printf("%d\n",b[x]);//如果这点没有标记，则说明没有移动过这点，输出b[aa]；
} else {
printf("%d\n",a[x-st2+st1]);//否则这点就移动过输出移动区间后的值也就是a[aa-Q.ed+Q.st]；
}
}
}
}
return 0;
}