P6604 [HNOI2016]序列 加强版（猫树）
panyf
·
·
题解
猫树学习笔记
不需要单调栈，用双指针就行。
存储结点信息的结构体：
struct T{ll la,ra,s,g;int m,l,r;}s[19][N];
其中 l,r 分别表示所在区间左右端点；
$m$ 表示 $x$ 到中点（这里对于左区间的 $x$，中点表示 $mid$，否则表示 $mid+1$）的 $a$ 的最小值；
$s$ 表示 $x$ 到中点的所有点的 $m$ 之和。
$g$ 表示一个端点为 $x$ 到中点的所有点，另一个端点为区间另一侧的所有点，所有这样的子段的最小值之和。
$l,r,m,s$ 可以直接求出。
左区间的 $la$ 和右区间的 $ra$ 直接继承下一层。
$g$ 可以双指针求出，具体做法：假设当前在求左区间的点 $x$ 的 $g$，将右区间分为两段，一段大于 $m_x$，另一段小于等于 $m_x$。两段分别求答案。两段的分界点用双指针维护。
左区间的 $ra$ 和右区间的 $la$ 用 $g$ 和下一层的 $la,ra$ 求出。
有了这些信息就可以 $O(1)$ 回答询问。
具体实现见代码。
定位询问区间的部分和 immortalCO 的博客略有不同（没有补全 $2^k$，但需要额外记录叶子结点编号），具体见[猫树学习笔记](https://www.luogu.com.cn/blog/221955/mao-shu)
。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+3;
int a[N],p[N],lg[N*4];
struct T{ll la,ra,s,g;int m,l,r;}s[19][N];
void wk(int d,int k,int l,int r){//d是当前深度，k是区间编号
T*f=s[d],*g=s[d+1];
int m=l+r>>1,i,t;
for(i=l;i<=r;++i)f[i].l=l,f[i].r=r;
if(l==r)return f[l].la=f[l].ra=a[l],void(p[l]=k);//记录叶子结点区间编号
ll w=0,u=0;
wk(d+1,k*2,l,m),wk(d+1,k*2+1,m+1,r);
for(g[m].m=g[m].s=a[m],i=m-1;f[i+1].la=g[i+1].la,i>=l;--i)g[i].s=g[i+1].s+(g[i].m=min(g[i+1].m,a[i]));
for(g[m+1].m=g[m+1].s=a[m+1],i=m+2;f[i-1].ra=g[i-1].ra,i<=r;++i)g[i].s=g[i-1].s+(g[i].m=min(g[i-1].m,a[i]));
for(i=r,t=m+1;i>m;--i)w+=g[i].m;
for(;i>=l;--i){//双指针部分
while(t<=r&&a[i]<a[t])w-=g[t++].m;
u=g[i].g=u+w+g[i].m*1ll*(t-m-1),f[i].ra=g[i].ra+g[r].la+u;
}
for(i=l,t=m,u=w=0;i<=m;++i)w+=g[i].m;
for(;i<=r;++i){
while(t>=l&&a[i]<a[t])w-=g[t--].m;
u=g[i].g=u+w+g[i].m*1ll*(m-t),f[i].la=g[i].la+g[l].ra+u;
}
}
using ull=unsigned long long;
ull S,A,B,C,l;
ull rd(){return S^=(A+B*l)%C;}
int main(){
int n,q,o,i,j,x,y;
ull w=0;
T*g;
for(i=1;i<N*4;++i)lg[i]=lg[i>>1]+1;//预处理lg表示log2(x)+1下取整
for(i=1,scanf("%d%d%d",&n,&q,&o);i<=n;++i)scanf("%d",a+i);
if(o)cin>>S>>A>>B>>C;
for(wk(0,1,1,n);q--;){
if(o){
x=rd()%n+1,y=rd()%n+1;
if(x>y)swap(x,y);
}else scanf("%d%d",&x,&y);
if(x==y)w^=(l=(ull)a[x]);else{
if(i=p[x],j=p[y],i<j)swap(i,j);
i>>=lg[i]-lg[j],i=lg[i>>lg[i^j]],g=s[i];
w^=(l=g[x].ra+g[y].la+(g[x].m<g[y].m?g[y].g-(y-g[x].r)*(g[g[x].l].s-g[x].s):g[x].g-(g[y].l-x)*(g[g[y].r].s-g[y].s)));
}
}
cout<<w;
return 0;
}
```