【题目大意】
给一个n个数的序列，q次操作，每次选择区间$[l,r]$，给出数p，对于区间$[l,r]$的每个数$x$，做如下操作：
如果$x > p$，就交换$x$和$p$。求每次操作后$p$的值。
$1\leq n\leq 4\times 10^5, 1\leq q \leq 25000$
【题解】
这个q的范围就提示我们可以用根号算法了（逃）
由于有一个性质，p最后一定是变成[l,r]区间内最大的那个数，可是还要修改，所以我们需要分块。
我们对于区间分块，然后对于每个块维护一个堆存储元素，同时维护一个tag维护这个块被几个p给做过操作（由于做操作的时候，如果是一整块，那么我们知道这块做完后，答案一定是这块的最大值和p中取个最大的，所以我们不需要实际做操作，只要打个tag即可）
当访问到块内（头、尾），我们把块内的tag传到值上，我们一定是用tag这个堆里最小的跟区间的每个值依次比较，比较成功就交换，我们可以用堆。
还有一些优化就是我们用vector存tag，然后用强制类型转换来线性建堆（？）
我们修改直接应用在数组上，修改完，再把数组拿去线性建堆（？）
然后你96分了。。换一个读入优化板子就过了。
# include <queue>
# include <math.h>
# include <ctype.h>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm> using namespace std; typedef long long ll;
typedef unsigned long long ull;
typedef long double ld; const int N = 4e5 + , M = 2e5 + , F = ; # define RG register
# define ST static int n, Q, BLOCK, B;
ST int a[N], bl[N];
ST int bg[F], ed[F]; #define BUFSIZE 300000
namespace fib {char b[BUFSIZE]={},*f=b;}
#define gc ((*fib::f)?(*(fib::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
int g_i()
{
int tmp=; bool fu=; char s;
while(s=gc,s!='-'&&(s<''||s>'')) ;
if(s=='-') fu=; else tmp=s-'';
while(s=gc,s>=''&&s<='') tmp=tmp*+s-'';
if(fu) return -tmp; else return tmp;
}
#define gi g_i()
namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce {~foce() {pob; fflush(stdout);}} _foce;
namespace ib {char b[];}
inline void pint(int x)
{
if(x==) {pc(); return;}
if(x<) {pc('-'); x=-x;}
char *s=ib::b;
while(x) *(++s)=x%, x/=;
while(s!=ib::b) pc((*(s--))+);
} priority_queue<int> q[F];
vector<int> tag[F]; inline void rebuild(int id) {
RG int l = bg[id], r = ed[id];
q[id] = priority_queue<int> (a+l, a+r+);
} inline void tagdown(int id) {
if(!tag[id].size()) return ;
priority_queue < int, vector<int>, greater<int> > heap(tag[id].begin(), tag[id].end());
for (RG int i=bg[id], tp; i<=ed[id]; ++i) {
tp = heap.top();
if(a[i] > tp) {
heap.pop();
heap.push(a[i]);
a[i] = tp;
}
}
rebuild(id);
tag[id].clear();
} // tag down and force
inline int work(int id, int l, int r, int p) {
tagdown(id);
for (int i=l; i<=r; ++i) if(a[i] > p) swap(a[i], p);
rebuild(id);
return p;
} // cover whole
inline int work(int id, int p) {
RG int tp = q[id].top();
if(tp > p) {
tag[id].push_back(p);
q[id].pop();
q[id].push(p);
p = tp;
}
return p;
} inline int solve(int l, int r, int p) {
int BL = bl[l], BR = bl[r];
if(BL == BR) return work(BL, l, r, p);
else {
p = work(BL, l, ed[BL], p);
for (int i=BL+; i<BR; ++i) p = work(i, p);
return work(BR, bg[BR], r, p);
}
} int main() {
// freopen("sushi.in", "r", stdin);
// freopen("sushi.out", "w", stdout);
n = gi; Q = gi;
for (RG int i=; i<=n; ++i) a[i] = gi;
BLOCK = sqrt(n);
for (RG int i=; i<=n; ++i) bl[i] = (i-) / BLOCK + ;
B = bl[n];
for (RG int i=; i<=B; ++i) {
bg[i] = (i-) * BLOCK + ;
ed[i] = i * BLOCK;
if(i == B) ed[i] = n;
}
for (RG int i=; i<=n; ++i) q[bl[i]].push(a[i]);
RG int l, r, p;
while(Q --) {
l = gi, r = gi, p = gi;
if(l <= r) pint(solve(l, r, p)), pc();
else {
p = solve(l, n, p);
pint(solve(, r, p)), pc();
}
}
return ;
}