题目：https://loj.ac/problem/2736
如果每个询问都是 l = 1 , r = n ，那么每次输出序列的 n 个数与本次操作的数的最大值即可。可以用堆维护。
不同区间的询问，可以分块！
考虑如果 l = 1 , r = n ，怎么知道最后的序列每个位置是什么。
可以这样：把所有操作的数字都放进小根堆里，依次遍历每个位置，如果堆顶比该位置的值小，就把该位置的值换成堆顶的值，堆里删掉原堆顶，加入该位置原来的值。
分块的话，每个块开两个大根堆，一个 yq 维护原序列的数字，一个 q 维护新加入的数字，再维护住 a[ ] 表示上次更新之后每个位置的值。
对整块操作一个数 x ，可以知道 yq 和 q 两个堆总体的最大值会被删掉（如果这个最大值是 > x 的）。于是在最大值所在的堆里删掉最大值，把 x 放进 q 里。
最后想知道这块每个位置的值，就拿着 q 在各位置走一遍，一边换一番。所以之所以要开一个 yq ，是为了体现 “原来在自己后面的比自己小的值不能挪到自己位置上” 。
每个询问，如果是在不整的块上，就先把那个块按上面的步骤做一遍，那么 a[ ] 维护的就是真实值了；做完把 q 清空，然后暴力枚举位置把 a[ ] 更新，再把 yq 更新即可。
经过一个零散块或者整块之后，操作的 x 可能改变；把改变后的 x 当作输入给下一个块就行了。
复杂度是 \( n \sqrt{n} logn \) ，9 s 还是可以的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
const int N=4e5+,M=;
int n,m,a[N],bs,bh[N],L[M],R[M];
priority_queue<int> q[M],yq[M];
priority_queue<int,vector<int>,greater<int> > tq[M];
int bl(int l,int r,int x)
{
int k=bh[l];
while(tq[k].size())tq[k].pop();
while(q[k].size())tq[k].push(q[k].top()),q[k].pop();
if(tq[k].size())//
{
for(int i=L[k];i<=R[k];i++)
{
int d=tq[k].top(); if(d>=a[i])continue;
tq[k].pop(); tq[k].push(a[i]); a[i]=d;
}
}
for(int i=l;i<=r;i++) if(x<a[i])swap(a[i],x);
while(yq[k].size())yq[k].pop();
for(int i=L[k];i<=R[k];i++)yq[k].push(a[i]);
return x;
}
int solve(int l,int r,int x)
{
if(bh[l]==bh[r])return bl(l,r,x);
x=bl(l,R[bh[l]],x); int k;
for(k=bh[l]+;k<=m&&R[k]<=r;k++)//k<=m
{
if(yq[k].size()&&q[k].size())
{
int d0=q[k].top(), d1=yq[k].top();
if(Mx(d0,d1)<=x)continue;
if(d0>d1)
{q[k].pop(); q[k].push(x); x=d0;}
else
{yq[k].pop(); q[k].push(x); x=d1;}//q.push
}
else if(yq[k].size())
{
int d=yq[k].top();
if(d>x){yq[k].pop();q[k].push(x);x=d;}
}
else if(q[k].size())
{
int d=q[k].top();
if(d>x){q[k].pop();q[k].push(x);x=d;}
}
}
if(k<=m&&R[k-]<r)x=bl(L[k],r,x);//k<=m//R[k-1] not R[k]
return x;
}
int main()
{
n=rdn(); int Q=rdn(); bs=sqrt(n);
for(int i=;i<=n;i++)a[i]=rdn();
L[]=; m=;
for(int i=,j=;i<=n;i++)
{
j++; if(j>bs){R[m]=i-;m++;L[m]=i;j=;}
bh[i]=m; yq[m].push(a[i]);
}
R[m]=n;
int l,r,x;
while(Q--)
{
l=rdn();r=rdn();x=rdn();
if(l<=r)x=solve(l,r,x);
else x=solve(l,n,x), x=solve(,r,x);
printf("%d\n",x);
}
return ;
}