My Blogs
P8078 [WC2022] 秃子酋长
没救了。
一眼回滚莫队，但是题解说能 $\log^2$。不会。
因为前缀询问是好做的，所以考虑分治，处理跨过中点的询问。对于右边排序后相邻的两个点 $a_i,a_j(a_i<a_j)$，考虑他们的贡献。
如果左侧有 $a_i,a_j$ 之间的点，贡献是 $i+j$，否则是 $\vert i-j\vert$。这可以求出来左侧第一次出现的位置，然后就是一个关于 $l$ 的区间加。
所以扫描 $r$ 从大到小扫，用链表找到合并的两个区间，BIT 维护 $l$ 的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
int n,m,ans[500010];
int l[500010],r[500010];
int a[500010],t[500010];
int F[19][500010];
inline int ask(int l,int r)
{
int k=__lg(r-l+1);
return max(F[k][l],F[k][r-(1<<k)+1]);
}
struct BIT
{
int t[500010],all;
inline void add(int x,int y){for(;x<=n;x+=x&-x)t[x]+=y;}
inline int ask(int x){int s=0;for(;x;x-=x&-x)s+=t[x];return all+s;}
inline void modify(int l,int r,int x){add(l,x),add(r+1,-x);}
}T;
int nex[500010],pre[500010],id[500010];
vi qu[500010];
void solve(int L,int R,vi ve)
{
if(L==R)return;
if(ve.empty())return;
int mid=(L+R)>>1,n=R-L+1,tm=__lg(n);
vi vl,vr,nw;
for(auto p:ve)
{
if(r[p]<=mid)vl.eb(p);
else if(l[p]>mid)vr.eb(p);
else nw.eb(p);
}
auto calc=[&](int typ)->void
{
for(int i=1;i<=n;++i)F[0][i]=0;
for(int i=L;i<=mid;++i)F[0][a[i]]=i;
for(int i=1;i<=tm;++i)for(int j=1;j+(1<<i)-1<=n;++j)
F[i][j]=max(F[i-1][j],F[i-1][j+(1<<(i-1))]);
for(int i=1;i<=n;++i)id[i]=nex[i]=pre[i]=0;
for(int i=mid+1;i<=R;++i)id[a[i]]=typ?i:(-(L+R-i));
id[n+1]=n+1;
auto modify=[&](int l,int r,int v)->void
{
if(r==n+1)
{
T.all+=v*id[l];
return T.add(ask(l,n)+1,-v*id[l]);
}
if(!l)
{
T.all+=v*id[r];
return T.add(ask(1,r)+1,-v*id[r]);
}
int d=ask(l,r);
T.all+=v*(id[l]+id[r]);
T.add(d+1,v*(abs(id[l]-id[r]))-v*(id[l]+id[r]));
};
for(int i=mid+1;i<=R;++i)
{
int p=a[i]+1;
while(p<=n&&!id[p])++p;
nex[a[i]]=p,pre[p]=a[i];
}
int p=1;
while(p<=n&&!id[p])++p;
nex[0]=p,pre[p]=0;
for(int i=0;i<=n;++i)if(nex[i])modify(i,nex[i],1);
for(int i=mid+1;i<=R;++i)qu[i].clear();
for(auto p:nw)qu[r[p]].eb(p);
for(int i=R;i>mid;--i)
{
for(auto p:qu[i])ans[p]+=T.ask(l[p]);
int v=a[i];
modify(v,nex[v],-1),modify(pre[v],v,-1);
modify(pre[v],nex[v],1);
nex[pre[v]]=nex[v],pre[nex[v]]=pre[v];
}
modify(0,n+1,-1);
};
calc(1);
for(auto p:nw)l[p]=L+R-l[p],r[p]=L+R-r[p],swap(l[p],r[p]);
reverse(a+L,a+R+1);
mid=(L+R)-mid-1;
calc(0);
reverse(a+L,a+R+1);
mid=(L+R)-mid-1;
auto fix=[&](int l,int r)->void
{
for(int i=0;i<=n;++i)t[i]=0;
for(int i=l;i<=r;++i)++t[a[i]];
for(int i=1;i<=n;++i)t[i]+=t[i-1];
for(int i=l;i<=r;++i)a[i]=t[a[i]];
};
fix(L,mid),fix(mid+1,R);
solve(L,mid,vl),solve(mid+1,R,vr);
}
inline void mian()
{
read(n,m);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=m;++i)read(l[i],r[i]);
vi ve(m);iota(all(ve),1);
solve(1,n,ve);
for(int i=1;i<=m;++i)write(ans[i],'\n');
}
inline void Mian()
{
int T=1,o;
// read(T);
while(T--)mian();
}