【题目大意】
给一个n个数的序列，q次操作，每次选择区间$[l,r]$，给出数p，对于区间$[l,r]$的每个数$x$，做如下操作：
如果$x > p$，就交换$x$和$p$。求每次操作后$p$的值。
$1leq nleq 4 imes 10^5, 1leq 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 + 10, M = 2e5 + 10, F = 3010; # 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=0; bool fu=0; char s; while(s=gc,s!='-'&&(s<'0'||s>'9')) ; if(s=='-') fu=1; else tmp=s-'0'; while(s=gc,s>='0'&&s<='9') tmp=tmp*10+s-'0'; if(fu) return -tmp; else return tmp; } #define gi g_i() namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-2;} #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[100];} inline void pint(int x) { if(x==0) {pc(48); return;} if(x<0) {pc('-'); x=-x;} char *s=ib::b; while(x) *(++s)=x%10, x/=10; while(s!=ib::b) pc((*(s--))+48); } 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+1); } 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+1; 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=1; i<=n; ++i) a[i] = gi; BLOCK = sqrt(n); for (RG int i=1; i<=n; ++i) bl[i] = (i-1) / BLOCK + 1; B = bl[n]; for (RG int i=1; i<=B; ++i) { bg[i] = (i-1) * BLOCK + 1; ed[i] = i * BLOCK; if(i == B) ed[i] = n; } for (RG int i=1; 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(10); else { p = solve(l, n, p); pint(solve(1, r, p)), pc(10); } } return 0; }