P4062 [Code+#1]Yazid 的新生舞会
分析
这个题目还是很有意思的，我们来一步步分析一下。
首先，我们来定一下我们的解题方向。涉及到众数，我们一般是考虑从每一个数字去考虑。
我们算的是满足某一个数字
- 在该区间为众数
- 且在该区间该数字的数量\(>\frac{r-l+1}{2}\)
条件的区间的数量。
我们假设，我们此时统计的数字是w。同时假设\(S_i\)为前i项，该数字的个数。
我们考虑如果一个区间[l,r]其满足我们说的条件，则即为满足一个式子。\(S_r-S_{l-1}>\frac{r-l+1}{2}\)，我们把式子变形一下，\(2S_r-r>2S_{l-1}-(l-1)\)。
则对于某一个具体的位置r，以其为右端点的满足条件的区间的数量，即为满足\(2S_r-r>2S_{l-1}-(l-1)\)的式子。
到这里，如果我们直接去维护\(2S_i-i\)，那时间复杂度就是\(O(n^2logn)\)，这还远远达不到我们的要求。
这里是看了题解的大佬的写法，真的奇妙啦。我来加一些自己的理解再说一说。
我们设一个新的变量，\(P_i=2S_i-i\)。
然后观察对某个选中的数 w，其 \(P_i\) 的变化情况。可以发现如果有 k 个 w，那么可以分成 k+1 个区间（以 0 位置及每个 w 为开头到下个 w 之前的数为止），每个区间内部的 \(P_i\) 值都是公差为 -1 的等差数列。
我们假设其中一段为，y,y-1,y-2,...,x，则对应的值域范围为[x,y]。
举个例子：
这样如果我们能用某种方法把每段里的数同时处理，那么总共需要处理的段数就是 \(O(n)\) 的了。
此时，我们考虑，对于一个具体的下标i，其对应的是\(P_i\)，那么对于其而言所有合法的解，即为，前面所有小于\(P_i\)的值的数量。下面用数学的语言表述。
首先我们设\(c_i\)为\(i\)的数量，\(T_i=\sum_{j=1}^{i}c_j\)。那么上面的描述就是，对于一个具体的下标i，其对应的是\(P_i\)，则对于其为右端点的所有合法解的数量即为\(T_{P_i-1}\)。
然后，我们来看对于某一个具体的段，因其中是递减的，因此，是一个连续的一段[x,y]，则这一段的所有合法解数量为，\(\sum_{i=x-1}^{y-1}T_i\)。
我们再设一个变量为\(G_i=\sum_{j=1}^{i}T_i\)
最后，我们总结简化一下，对于我们拆分的某一个具体的段，我们这一段的所有合法解即为\(G_{y-1}-G_{x-2}\)。
同时每次新加一个段时，我们先进行询问，再进行修改。
修改操作即为将区间内所有\(P_i\)对应的\(c_{P_i}\)加一，即为将\(c_i\)的对应的[x,y]区间范围内加一。
我们如何通过这样的修改，去完成我们的询问呢？
树状数组
先回忆一下，在我们学习树状数组还未学习线段树之前，我们求"区间加，区间求和"，是如何用树状数组实现的。
本质上，我们就是维护了原序列的差分数组，从而用维护两个树状数组的方法，将问题转化为了，单点修，区间求二次前缀和。
其实，我们是可以使用n个树状数组，完成单点修，查询n阶的前缀和。
比如n=3时，
设c为b的前缀和，b为a的前缀和，a是d的前缀和。
那么我们可以进行推导。
\[c_x=\sum_{i=1}^{x}b_i \\=\sum_{i=1}^{x}\sum_{j=1}^{i}a_j \\=\sum_{i=1}^{x}\sum_{j=1}^{i}\sum_{k=1}^{j}d_k \\=\sum_{k=1}{x}\frac{(x+2-k)(x+1-k)}{2}d_k \\=\frac{(x+2)(x+1)}{2}\sum_{k=1}^{x}d_k - \frac{2x+3}{2}\sum_{k=1}^{x}d_k*k+\frac{1}{2}\sum_{k=1}^{x}d_k*k^2 \]因此，问题就转化结束了，我们只需要把问题转化为维护三个树状数组，分别维护\(d_i,d_i*k,d_i*k^2\)，就可以了。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll tr[3][N*2];
int a[N],n;
vector<int> b[N];
void add(int x,int c)
{
ll t = x;
while(x<=2*n+1)
{
tr[0][x] += c;
tr[1][x] += c*t;
tr[2][x] += c*t*t;
x += x & -x;
}
}
ll sum(int x)
{
ll res = 0,t = x;
while(x>0)
{
ll tmp = 0;
tmp += tr[0][x]*(t+2)*(t+1);
tmp -= tr[1][x]*(t*2+3);
tmp += tr[2][x];
res += tmp/2;
x -= x & -x;
}
return res;
}
int main()
{
int ty;cin>>n>>ty;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]].push_back(i);
}
ll ans = 0,wc = n + 1;
for(auto nums:b)
{
ll last = 0;
if(nums.size()) nums.push_back(n+1);
for(int i=0;i<nums.size();i++)
{
int y = 2*i - last + wc,x = 2*i - (nums[i] - 1) + wc;
ans += sum(y-1) - sum(x-2);
cout<<sum(y-1) - sum(x-2)<<endl;
// cout<<last<<" "<<nums[i]<<" "<<ans<<endl;
add(x,1);add(y+1,-1);
last = nums[i];
}
if(nums.size()) cout<<'\n';
last = 0;
for(int i=0;i<nums.size();i++)
{
int y = 2*i - last + wc,x = 2*i - (nums[i] - 1) + wc;
add(x,-1);add(y+1,1);
last = nums[i];
}
}
cout<<ans<<'\n';
return 0;
}
线段树
其实也可以用两棵线段树来求二阶前缀和，但这就没有意思了，和树状数组维护三阶前缀和没区别。
我的方法是用线段树维护权值的前缀和 \(T_i\) ，这样在 [x,y] 上的区间加 1 就变成了：在 [x,y] 上加等差数列 1,2,3,\(\ldots\),y-x+1在 [y+1,2n+1]上加上 y-x+1。后者也可看成是公差为 0 的等差数列。
那么线段树怎么维护等差数列呢？
我们可以发现任意个等差数列的和都是等差数列，只是公差和首项发生了变化。
那么只要把公差和首项作为延迟标记，来维护区间和就好了，具体实现见代码。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
struct Node
{
int l,r;
ll sum,val,d;
}tr[N<<2];
int a[N];
vector<int> b[N];
int n,ty;
void build(int u,int l,int r)
{
tr[u] = {l,r};
if(l==r) return ;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void pushdown(int u)
{
auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
if(root.val||root.d)
{
left.val += root.val,left.d += root.d;
left.sum += (2ll*root.val + root.d*(left.r-left.l))*(left.r - left.l + 1)/2;
ll t = root.val + root.d*(left.r - left.l + 1);
right.val += t,right.d += root.d;
right.sum += (2ll*t + root.d*(right.r-right.l))*(right.r - right.l + 1)/2;
root.val = 0,root.d = 0;
}
}
void modify(int u,int l,int r,int a,int d)
{
if(l>tr[u].r||r<tr[u].l) return ;
if(l<=tr[u].l&&tr[u].r<=r)
{
ll t = a + (tr[u].l - l)*d;
tr[u].val += t;tr[u].d += d;
tr[u].sum += (2ll*t + 1ll*d*(tr[u].r - tr[u].l))*(tr[u].r - tr[u].l + 1)/2;
return ;
}
pushdown(u);
modify(u<<1,l,r,a,d);modify(u<<1|1,l,r,a,d);
pushup(u);
}
ll query(int u,int l,int r)
{
if(l>tr[u].r||r<tr[u].l) return 0;
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
pushdown(u);
return query(u<<1,l,r) + query(u<<1|1,l,r);
}
int main()
{
ios;
cin>>n>>ty;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]].push_back(i);
}
build(1,1,n*2+1);
ll ans = 0,wc = n + 1;
for(auto nums:b)
{
if(nums.size()) nums.push_back(n+1);
int last = 0;
for(int i=0;i<nums.size();i++)
{
int y = 2*i - last + wc,x = 2*i - (nums[i] - 1) + wc;
// cout<<x<<' '<<y<<' ';
// cout<<query(1,x>=2?x-1:1,y-1)<<endl;
ans += query(1,x>=2?x-1:1,y-1);
// cout<<last<<" "<<nums[i]<<" "<<ans<<endl;
modify(1,x,y,1,1);modify(1,y+1,2*n+1,y-x+1,0);
last = nums[i];
}
// if(nums.size()) cout<<'\n';
last = 0;
for(int i=0;i<nums.size();i++)
{
int y = 2*i - last + wc,x = 2*i - (nums[i] - 1) + wc;
modify(1,x,y,-1,-1);modify(1,y+1,2*n+1,-y+x-1,0);
last = nums[i];
}
}
cout<<ans<<'\n';
return 0;
}