TAMAYA
挺有意思的维护题。
题面
n个小夫坐成一排，每个小夫有一个真实值vi。小夫们有m场聚会，第i次聚会会在编号为 [li, ri] 的小夫中举办。
聚会之后，这些小夫的真实值会变为他们之中的真实值的最大值。将会发生q次事件，有两类事件。
- 第一类事件，第x个小夫的真实值变成了y。
- 第二类事件，小夫们向你提问，假如第L次聚会到第R次聚会按顺序举办，第x个 小夫的真实值会变成多少。
对于所有测试点：\(n,m,q\leq 5\times 10^5,l_i\leq r_i\leq n,x\leq n,L\leq R,op\in\{1,2\},v_i,y\leq 10^9\)
思路
下文称聚会为操作，提问为查询。
只考虑 \(op=2\) 的情况，对于一个询问中的 \(x_i\)，令 \([lx,rx]=[x_i,x_i]\)。
倒序进行询问中的操作 \([L_i,R_i]\)，若一次操作 \([l_j,r_j](j\in [L_i,R_i])\) 与现在的 \([lx,rx]\) 有交集，那么令 \(lx=\min(lx,l_j)\)，\(rx=\max(rx,r_j)\)；形式化的，若 \([l_j,r_j]\cap[lx,rx]\neq \emptyset\)，那么令 \([lx,rx]=[l_j,r_j]\cup[lx,rx]\)。
最后的答案就是 \([lx,rx]\) 区间中的最大值。
考虑到每一个查询的 \([x_i,x_i]\)，在第一次取并集后，会以一个操作中的区间 \([l_j,r_j]\) 的形式出现。考虑对于一个操作 \(j\)，维护出执行了倒叙执行操作 \(k\sim j(k<j)\) 区间左端点和右端点的变化。
但是这样的复杂度来到了 \(O(m^2)\)。
考虑倍增维护，维护出合并 \(2^k\) 次操作后的区间的左右端点的变化。
由于 \(l_j\) 合并只会变成前面某一次操作的 \(l\)，这样就可以倍增维护出变成了哪一次操作的 \(l\)。
\(r\) 同理。
最后对于查询 \(x_i\)，维护出最后一次被操作覆盖即可。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,q;
int v[maxn],pl[maxn][25],pr[maxn][25],l[maxn],r[maxn],L[maxn],R[maxn],id[maxn],op[maxn],x[maxn];
vector<int>vec[maxn];
namespace linetree
{
#define lch(p) p*2
#define rch(p) p*2+1
struct treenode{int mx,lazy;}tr[maxn*20];
inline void updata(int p) {tr[p].mx=max(tr[lch(p)].mx,tr[rch(p)].mx);}
inline void push_down(int p,int l,int r)
{
if(!tr[p].lazy) return ;
if(l==r) return ;
tr[lch(p)].mx=max(tr[p].lazy,tr[lch(p)].mx);
tr[lch(p)].lazy=max(tr[p].lazy,tr[lch(p)].lazy);
tr[rch(p)].mx=max(tr[p].lazy,tr[rch(p)].mx);
tr[rch(p)].lazy=max(tr[p].lazy,tr[rch(p)].lazy);
tr[p].lazy=0;
}
inline void change(int p,int l,int r,int lx,int rx,int v)
{
if(r<lx||l>rx) return ;
push_down(p,l,r);
if(lx<=l&&r<=rx)
{
tr[p].mx=v;tr[p].lazy=v;
return ;
}
int mid=(l+r)>>1;
change(lch(p),l,mid,lx,rx,v);change(rch(p),mid+1,r,lx,rx,v);
updata(p);
}
inline int qry(int p,int l,int r,int lx,int rx)
{
if(r<lx||l>rx) return 0;
push_down(p,l,r);
if(lx<=l&&r<=rx) return tr[p].mx;
int mid=(l+r)>>1;
return max(qry(lch(p),l,mid,lx,rx),qry(rch(p),mid+1,r,lx,rx));
}
inline void clr(){memset(tr,0,sizeof(tr));}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&op[i],&L[i],&R[i]);
if(op[i]==2) scanf("%d",&x[i]),vec[R[i]].emplace_back(i);
}
for(int i=1;i<=m;i++)
{
pl[i][0]=linetree::qry(1,1,n,l[i],l[i]);
pr[i][0]=linetree::qry(1,1,n,r[i],r[i]);
linetree::change(1,1,n,l[i],r[i],i);
for(auto v:vec[i]) id[v]=linetree::qry(1,1,n,x[v],x[v]);
}
for(int i=1;i<=m;i++) for(int j=1;j<=log2(m);j++)
{
pl[i][j]=pl[pl[i][j-1]][j-1];
pr[i][j]=pr[pr[i][j-1]][j-1];
}
linetree::clr();
for(int i=1;i<=n;i++) linetree::change(1,1,n,i,i,v[i]);
for(int i=1;i<=q;i++)
{
if(op[i]==1)
linetree::change(1,1,n,L[i],L[i],R[i]);
else
{
if(id[i]<L[i]) {printf("%d\n",linetree::qry(1,1,n,x[i],x[i]));continue;}
int lx=id[i],rx=id[i];
for(int j=log2(m);~j;j--) if(pl[lx][j]>=L[i]) lx=pl[lx][j];
for(int j=log2(m);~j;j--) if(pr[rx][j]>=L[i]) rx=pr[rx][j];
printf("%d\n",linetree::qry(1,1,n,l[lx],r[rx]));
}
}
}