题意：
庭院中有 n 个围栏，每个围栏上都被涂上了不同的颜色（数字表示）；
有 m 条指令，每条指令给出一个整数 x ，你要做的就是将区间[ x第一次出现的位置 , x最后出现的位置 ]中的围栏
全部涂成 x ，经过 m 次操作后，输出每个围栏的涂色情况；
题解：
比赛的时，在读完题后，一瞬间，想到了线段树的区间更新，懒惰标记，but 我已经好久好久没写过线段树的代码了（嫌代码太长，逃）；
所以，比赛时，就不了了之，去看其他题了；
今天，温习了一下线段树的用法，重新思考了本题的解题思路，感觉，线段树可以做出来；
然后，对着电脑撸了一个线段树版的代码，一发AC，哈哈，开森~~~~~~
手动艾特两个不相信线段树可以AC的童鞋，哈哈哈！
具体思路：
首先准备一个双端队列 q[ maxn ]; （maxn = 3e5+50 ，因为 ci ≤ 3*105 ）
q[ i ] 中存储的是所有的被涂上颜色 i 的栅栏编号，按顺序从小到大存储；
对于每一个指令 x ，首先判断 q[x].size() 是否大于 1，如果大于 1，令 f = q[x].front() , e = q[x].end();
然后，判断下标 f 和 e 对应的栅栏的颜色是否为 x ，如果是，通过线段树的区间更新+懒惰标记将区间[f,e]染成 x，接着执行下一条指令；
如果 f 或 e 对应的栅栏颜色在之前被涂成了其他颜色，那么在 q[x] 中查找下一个满足条件的区间，如果找不到，不操作，执行下一条指令；
最后，调用线段树的查询操作，输出答案。
AC代码：
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int maxn=3e5+; int n,m;
int a[maxn];
deque<int >q[maxn];
struct SegmentTree
{
int l,r;
int color;
int mid()
{
return l+((r-l)>>);
}
}segTree[*maxn]; void buildSegTree(int pos,int l,int r)
{
segTree[pos].l=l;
segTree[pos].r=r;
segTree[pos].color=;
if(l == r)
{
segTree[pos].color=a[l];
return ;
} int mid=l+((r-l)>>);
buildSegTree(ls(pos),l,mid);
buildSegTree(rs(pos),mid+,r);
} /**
向下更新，与区间更新懒惰标记不同的是
直接将pos的左右儿子的color赋值为x
*/
void pushDown(int pos)
{
int &x=segTree[pos].color;
if(x != )
{
segTree[ls(pos)].color=x;
segTree[rs(pos)].color=x;
x=;
}
}
/**
将区间[l,r]所包含的子区间的color值赋为x
出现的bug:起初直接将64行的赋值操作写成了
segTree[pos].color=a[l];
调试了好大会；
因为 a[l] 是改变前的涂色情况，如果l号栅栏在之前被染成了其他颜色
那么l号栅栏的颜色就不是a[l]了
*/
void Update(int pos,int l,int r,int x)
{
if(l <= segTree[pos].l && r >= segTree[pos].r)
{
segTree[pos].color=x;
return ;
}
pushDown(pos); int mid=segTree[pos].mid();
if(r <= mid)
Update(ls(pos),l,r,x);
else if(l > mid)
Update(rs(pos),l,r,x);
else
{
Update(ls(pos),l,mid,x);
Update(rs(pos),mid+,r,x);
}
}
int Query(int pos,int index)
{
if(segTree[pos].l == segTree[pos].r)
return segTree[pos].color; pushDown(pos); int mid=segTree[pos].mid();
if(index <= mid)
return Query(ls(pos),index);
else
return Query(rs(pos),index);
}
void Solve()
{
buildSegTree(,,n);
for(int i=;i <= m;++i)
{
int x;
scanf("%d",&x);
if(q[x].size() <= )
continue; /**
寻找可行的区间[f,e]
*/
int f=q[x].front();
int e=q[x].back();
while(Query(,f) != x && !q[x].empty())
{
q[x].pop_front();
if(!q[x].empty())
f=q[x].front();
}
while(Query(,e) != x && !q[x].empty())
{
q[x].pop_back();
if(!q[x].empty())
e=q[x].back();
}
//确保f != e
if(q[x].size() > )
Update(,f,e,x);
}
for(int i=;i <= n;++i)
printf("%d ",Query(,i));
printf("\n");
}
int main()
{
// freopen("C:/Users/hyacinthLJP/Desktop/stdin/contest","r",stdin);
scanf("%d",&n);
for(int i=;i <= n;++i)
{
scanf("%d",a+i);
q[a[i]].push_back(i);
}
scanf("%d",&m);
Solve(); return ;
}