【题解】P8313 [COCI2021-2022#4] Izbori
lnwhl
·
·
题解
前言
更棒的阅读体验
很棒的一道题，建议评紫。
这里提供一种 \mathcal O(n\log n) 的树状数组的解法，并有详细的部分分题解，可能比较长，如果只想看正解可以直接看 Subtask 4，代码在最后面（包括部分分代码）。
Subtask 1
暴力穷举区间，枚举众数判断即可。复杂度 \mathcal O(n^3)。
Subtask 2
暴力穷举区间，区间元素个数用一个桶维护起来，区间 (i,j+1) 的各个元素的个数可以由区间 (i,j) 递推得。但由于 a_i 得范围达到了 10^9，需要离散化一下。复杂度 \mathcal O(n^2)。
Subtask 3
考虑到只有 1，2 两种数字，所以区间不合法只有一种情况：区间内 1，2 个数相等。考虑将 1 的值设成 1，2 的值设成 -1，所以不合法的区间的区间和为 0，可以记录一个前缀桶来维护。复杂度 \mathcal O(n)。
Subtask 4
受 Subtask 3 的启发，穷举每个种类的数，分别计算贡献。
$$2(S_r-S_l)> r-l$$
移一下项就变为
$$2S_r-r>2S_l-l$$
这样问题就变成了：对于每一个 $r$，$0\sim r-1$ 中由多少个 $l$ 使 $2S_l-l<2S_r-r$，是一个二维偏序问题，可以通过树状数组维护，复杂度是 $\mathcal O(kn\log n)$ 的，其中 $k$ 为不同数字的个数。但是这样还是只能通过前三个 Subtask，需要优化。
设 $B_i=2S_i-i$，对于每一个 $x$，考虑 $B_i$ 的变化情况。举个例子：
可以发现如果有 $m$ 个 $x$，那么 $B_i$ 可以被分成 $m+1$ 个区间，每个区间都是一个公差为 $-1$ 的等差数列。考虑到所有的 $m$ 的和为 $n$，我们其实只需要快速处理每一段里的数。
假设这个等差数列为 $s,s-1,\cdots,e+1,e$，用一个数组 $C_i$ 来记录每一个数的个数，那么就是 $[e,s]$ 区间的每个 $C_i$ 都加 $1$。
设 $D_i$ 表示 $C_i$ 的前缀和，即 $D_i=\sum\limits_{j=1}^iC_j$，对于每个 $B_i$，贡献即为 $D_{B_i-1}$，所以对于 $[e,s]$ 这个区间内的所有数，总贡献即为 $\sum\limits_{i=e-1}^{s-1}D_i$，这又变成了一个区间和问题，我们再维护一个数组 $E_i$ 表示 $C_i$ 前缀和的前缀和，即为 $D_i$ 数组的前缀和，即 $E_i=\sum\limits_{j=1}^iD_j$，这样总贡献就变成了
$$\sum\limits_{i=e-1}^{s-1}D_i=E_{s-1}-E_{e-2}$$
至此问题就变成了一个**区间修改，求二阶前缀和**的问题。这就有很多解法了，这里只提供一个树状数组的解法。
考虑到区间修改可以通过**单点修改，求前缀和**来解决，问题就可已转化为**单点修改，求三阶前缀和**。
推的过程比较繁琐，如果不理解可以自己手模两组数据来理解。
------------
现在问题变成了**单点修改，求三阶前缀和**，该如何处理？
如果不会建议先看一看这道题，[ABC 256 F Cumulative Cumulative Cumulative Sum](https://atcoder.jp/contests/abc256/tasks/abc256_f)，这里讲一下树状数组的思路。
先假设 $A_i$ 为原数组，$B_i$ 数组为 $A_i$ 的前缀和，$C_i$ 数组为 $A_i$ 数组的二阶前缀和，$D_i$ 数组为 $A_i$ 的三阶前缀和。
考虑 $A_i$ 对 $B_x$ ($i\le x$) 的贡献为 $1$。
考虑 $A_i$ 对 $C_x$ ($i\le x$) 的贡献为 $x-i+1$。
考虑 $A_i$ 对 $D_x$ ($i\le x$) 的贡献为 $\dfrac{(x-i+1)(x-i+2)}{2}$。
$$D_i=\sum\limits_{i=1}^x\dfrac{(x-i+1)(x-i+2)}{2}A_i$$
$$D_i=\dfrac{(x+1)(x+2)}{2}\sum\limits_{i=1}^xA_i-\dfrac{2x+3}{2}\sum\limits_{i=1}^xiA_i+\dfrac{1}{2}\sum\limits_{i=1}^xi^2A_i$$
用树状数组分别维护 $A_i,iA_i,i^2A_i$，可以解决。
------------
至此，问题就完全解决了。代码在最下面，写了注释。
## 代码
### Subtask 2
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N],cop[N],tong[N];
ll ans=0;
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],cop[i]=a[i];//cop为离散化数组
sort(cop+1,cop+n+1);
int cntl=unique(cop+1,cop+n+1)-cop-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(cop+1,cop+cntl+1,a[i])-cop;//离散化
for(int l=1;l<=n;++l)
{
int cur=a[l];
for(int r=l;r<=n;++r)
{
tong[a[r]]++;//更新桶数组
if(tong[a[r]]>tong[cur])cur=a[r];//打擂台得出出现次数最多的元素
if(tong[cur]*2>r-l+1)ans++;//判断区间众数个数一半
}
for(int r=l;r<=n;++r)tong[a[r]]--;//清空tong数组
}
cout<<ans;
return 0;
}
```
### Subtask 3
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N],b[N],tong[N<<1];
ll ans=0;
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
if(a[i]==1)b[i]=1;
else b[i]=-1;
}
//因为前缀和会出现负数，所以要统一偏移n
int sum=0;tong[n]++;
for(int i=1;i<=n;++i)
{
sum+=b[i];//前缀和
ans+=tong[sum+n];//更新答案
tong[sum+n]++;//更新桶
}
cout<<1ll*n*(n+1)/2-ans;//合法区间-不合法区间
return 0;
}
```
### Subtask 4 不加优化做法
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N],cop[N],bsum[N<<1],s[N];
ll ans=0;
inline int lowbit(int x){return x&-x;}
inline void add(int i,int x)
{
while(i<=2*n+2)bsum[i]+=x,i+=lowbit(i);
}
inline int query(int i)
{
int res=0;
while(i)res+=bsum[i],i-=lowbit(i);
return res;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],cop[i]=a[i];//cop为离散化数组
sort(cop+1,cop+n+1);
int cntl=unique(cop+1,cop+n+1)-cop-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(cop+1,cop+cntl+1,a[i])-cop;//离散化
for(int i=1;i<=cntl;++i)
{
for(int j=1;j<=n;++j)
s[j]=s[j-1]+(a[j]==i);//求出前缀和
add(n+1,1);//n+1的偏移量
for(int j=1;j<=n;++j)
{
ans+=query(2*s[j]-j+n);//树状数组查询
add(2*s[j]-j+n+1,1);
}
add(n+1,-1);
for(int j=1;j<=n;++j)
add(2*s[j]-j+n+1,-1);//清空树状数组
}
cout<<ans;
return 0;
}
```
### Subtask 4 AC 代码
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,a[N],cop[N];
ll ans=0,bs1[N<<1],bs2[N<<1],bs3[N<<1];
//bs1，bs2，bs3维护树状数组，需要进行n+1的偏移量
vector<int>t[N];
inline int lowbit(int x){return x&-x;}
inline void add(int i,ll d)
{
int x=i;
while(i<=2*n+2)
{
bs1[i]+=d;bs2[i]+=d*x;bs3[i]+=d*x*x;
i+=lowbit(i);
}
}
inline ll query(int i)
{
ll res=0;int x=i;
while(i)
{
res+=bs1[i]*(x+2)*(x+1)-bs2[i]*(2*x+3)+bs3[i];
i-=lowbit(i);
}
return res/2;
}
//树状数组
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],cop[i]=a[i];//cop为离散化数组
sort(cop+1,cop+n+1);
int cntl=unique(cop+1,cop+n+1)-cop-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(cop+1,cop+cntl+1,a[i])-cop;//离散化
for(int i=1;i<=n;++i)t[a[i]].push_back(i);//每一类数组又一个向量存起来
for(int i=1;i<=cntl;++i)//穷举数字
{
t[i].push_back(n+1);
int lst=0;
for(int j=0;j<t[i].size();++j)
{
int y=2*j-lst+n+1,x=2*j-t[i][j]+n+2;
ans+=query(y-1)-(x>=3?query(x-2):0);//树状数组查询
add(x,1);add(y+1,-1);lst=t[i][j];
}
lst=0;
for(int j=0;j<t[i].size();++j)
{
int y=2*j-lst+n+1,x=2*j-t[i][j]+n+2;
add(x,-1);add(y+1,1);lst=t[i][j];
}//清空树状数组
}
cout<<ans;
return 0;
}
```