题解 P9337
阈值分治，对于
对于
前半部分时间复杂度
代码懒得写了，退役人哪有空写代码。
写完了。
// Problem: P9337 [Ynoi2001] 冷たい部屋、一人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9337
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//And from now on, YOU are my GUIDING STAR.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[500003],c[500003];
int l2[500003],n=read(),m=read();
vector<int> v[500003];
int arr[2000003],L;
bool flg[2000003];
struct query{int l,r,id;}q[500003],q0[500003];
vector<pair<int,int>> vq[500003];
struct stmax
{
int st[500003][19];
inline void init(int l)
{
st[l][0]=a[l];
for(int i=1; i<19; i++)
st[l][i]=max(st[l][i-1],
st[min(l+(1<<(i-1)),n)][i-1]);
}
inline int query(int l,int r)
{
int L=l2[r-l+1];
return max(st[l][L],st[min(r-(1<<L)+1,n)][L]);
}
void main()
{
for(int i=n; i; --i) init(i);
return ;
}
}S1;
struct stmin
{
int st[500003][19];
inline void init(int l)
{
st[l][0]=a[l];
for(int i=1; i<19; i++)
st[l][i]=min(st[l][i-1],
st[min(l+(1<<(i-1)),n)][i-1]);
}
inline int query(int l,int r)
{
int L=l2[r-l+1];
return min(st[l][L],st[min(r-(1<<L)+1,n)][L]);
}
void main()
{
for(int i=n; i; --i) init(i);
return ;
}
}S0;
struct BIT
{
int pre0[500003],pre1[503];
inline void add(int x)
{
++pre0[x],++pre1[x>>10];
return ;
}
inline int find(int x)
{
int res=0;
for(int i=(x>>10)<<10; i<=x; ++i) res+=pre0[i];
for(int i=0; i<(x>>10); ++i) res+=pre1[i];
return res;
}
}T;
const int B=2000;
ll ans[500003];
vector<int> pos[500003];
int to_[500003],val_[500003],top;
int to[500003],val[500003],buc[500003];
int ta[500003],lsh[500003],inv[500003];
bool tf[500003];
struct range{int fi,se,id;}rg[500003],stk[1000003];
signed main()
{
for(int i=2; i<=n; i++) l2[i]=l2[i>>1]+1;
for(int i=1; i<=n; ++i) c[i]=read(),v[c[i]].push_back(i);
for(int i=1; i<=n; ++i) a[i]=read();
for(int i=1; i<=m; ++i)
rg[i].fi=read(),rg[i].se=read(),rg[i].id=i,
vq[rg[i].fi].emplace_back(rg[i].se,i);
S0.main(),S1.main(),sort(rg+1,rg+m+1,
[&](auto x,auto y){return x.se<y.se;});
for(int i=1; i<=n; ++i)
{
int sz=v[i].size();
if(sz>=B)
{
int N=0,M=0;
memset(buc,0,sizeof(buc));
for(int j=0; j<sz; ++j)
{
ta[++N]=a[v[i][j]],tf[N]=1;
if(j+1<sz&&v[i][j]+1<v[i][j+1])
{
ta[++N]=S0.query(v[i][j]+1,v[i][j+1]-1),tf[N]=0;
if(v[i][j]+2<v[i][j+1])
ta[++N]=S1.query(v[i][j]+1,v[i][j+1]-1),tf[N]=0;
}
}
for(int j=1; j<=N; ++j) lsh[j]=ta[j],++buc[ta[j]];
for(int j=1; j<=n; ++j) buc[j]+=buc[j-1];
sort(lsh+1,lsh+N+1);
for(int j=1; j<=N; ++j)
ta[j]=lower_bound(lsh+1,lsh+N+1,ta[j])-lsh,
inv[ta[j]]=j;
for(int j=1; j<=m; ++j)
{
++M,q0[M].l=buc[rg[j].fi-1]+1,
q0[M].r=buc[rg[j].se],q0[M].id=rg[j].id;
if(q0[M].l>q0[M].r) --M;
}
if(!M) continue;
int C=.7*N/sqrt(M)+1;
memset(buc,0,sizeof(buc));
for(int j=1; j<=M; ++j) ++buc[q0[j].l/C];
for(int j=1; j<=N; ++j) buc[j]+=buc[j-1];
for(int j=M; j>=1; --j) q[buc[q0[j].l/C]--]=q0[j];
ll sum=0;
memset(to,0,(N+2)<<2),memset(val,0,(N+2)<<2);
for(int j=1,tl=C,tr=C-1; j<=M; ++j)
{
if(q[j].l/C!=q[j-1].l/C)
memset(to,0,(N+2)<<2),
memset(val,0,(N+2)<<2),
tl=(q[j].l/C+1)*C,tr=tl-1,sum=0;
if(q[j].l/C==q[j].r/C)
{
ll sum_=0;
for(int k=q[j].l; k<=q[j].r; ++k)
{
int l=inv[k],r=inv[k],sv=tf[inv[k]];
if(to_[l-1])
sum_-=1ll*val_[to_[l-1]]*
(val_[to_[l-1]]-1),
sv+=val_[to_[l-1]],l=to_[l-1];
if(to_[r+1])
sum_-=1ll*val_[r+1]
*(val_[r+1]-1),
sv+=val_[r+1],r=to_[r+1];
sum_+=1ll*sv*(sv-1),
to_[l]=r,to_[r]=l,val_[l]=sv;
}
for(int k=q[j].l; k<=q[j].r; ++k)
to_[inv[k]]=val_[inv[k]]=0;
ans[q[j].id]+=sum_>>1;
continue;
}
while(tr<q[j].r)
{
int k=++tr,l=inv[k],r=inv[k],sv=tf[inv[k]];
if(to[l-1])
sum-=1ll*val[to[l-1]]*
(val[to[l-1]]-1),
sv+=val[to[l-1]],l=to[l-1];
if(to[r+1])
sum-=1ll*val[r+1]
*(val[r+1]-1),
sv+=val[r+1],r=to[r+1];
sum+=1ll*sv*(sv-1),
to[l]=r,to[r]=l,val[l]=sv;
}
ll tsum=sum;
for(int k=tl-1; k>=q[j].l; --k)
{
int l=inv[k],r=inv[k],sv=tf[inv[k]];
if(to[l-1])
tsum-=1ll*val[to[l-1]]*
(val[to[l-1]]-1),
sv+=val[to[l-1]],l=to[l-1];
if(to[r+1])
tsum-=1ll*val[r+1]
*(val[r+1]-1),
sv+=val[r+1],r=to[r+1];
tsum+=1ll*sv*(sv-1),
stk[++top]={to[l],val[l],l},
to[l]=r,val[l]=sv,
stk[++top]={to[r],val[r],r},
to[r]=l;
}
while(top)
to[stk[top].id]=stk[top].fi,
val[stk[top].id]=stk[top].se,--top;
ans[q[j].id]+=tsum>>1;
}
}
else
{
for(int j=0; j<sz; ++j)
{
arr[++L]=a[v[i][j]],flg[L]=1,
pos[arr[L]].push_back(L);
if(j+1<sz&&v[i][j]+1<v[i][j+1])
{
arr[++L]=S0.query(v[i][j]+1,v[i][j+1]-1),
pos[arr[L]].push_back(L);
if(v[i][j]+2<v[i][j+1])
arr[++L]=S1.query(v[i][j]+1,v[i][j+1]-1),
pos[arr[L]].push_back(L);
}
}
arr[++L]=0;
}
}
for(int i=n; i>=1; --i)
{
for(int j:pos[i])
{
for(int l=j,v=arr[j]; arr[l]>=arr[j];
v=max(v,arr[--l])) if(flg[l])
for(int r=j,w=v; r==j||arr[r]>arr[j];
w=max(w,arr[++r])) if(flg[r]&&l<r) T.add(w);
}
for(auto [j,k]:vq[i])
ans[k]+=T.find(j);
}
for(int i=1; i<=m; ++i) printf("%lld\n",ans[i]);
return 0;
}