题目：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=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } int Mx(int a,int b){return a>b?a:b;} const int N=4e5+5,M=1005; 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]+1;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-1]<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=1;i<=n;i++)a[i]=rdn(); L[1]=1; m=1; for(int i=1,j=0;i<=n;i++) { j++; if(j>bs){R[m]=i-1;m++;L[m]=i;j=1;} 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(1,r,x); printf("%d ",x); } return 0; }