洛谷 - P4062 [Code+#1]Yazid 的新生舞会(推公式+线段树)

题目链接：点击查看

题目大意：给出一个长度为 $n$ 的序列，现在要求存在 绝对众数 的子区间个数

所谓 绝对众数，就是对于区间 $[l,r]$ 来说，存在一个数字的出现次数 $cnt$，满足不等式 $cnt\ast 2>r-l+1$

题目分析：假如字符集很小，我们可以对每个字符集单独讨论，即枚举每个字符作为众数，判断合法的区间个数。如何判断？设置一个辅助数组 $b$，若原数组的 $i$ 位置是该字符，则令 $b[i]=1$，否则 $b[i]=-1$，对 $b$ 数组维护一个前缀和 $sum$，不难看出区间和严格大于 $0$ 的区间是合法的区间，即需要寻找合法二元对 $(i,j)$ 的个数满足 $sum[i]<sum[j]$ 且 $i<j$。不难看出这就是基于 $sum$ 的一个顺序对。可以用树状数组简单维护，时间复杂度 $O(knlogn)$，$k$ 为字符集大小。

但是对于本题而言，字符集特别大，和 $n$ 同阶，所以考虑优化。

如果对于每个字符都继续沿用上述过程求解的话，我们发现 $b$ 数组中绝大部分都是 $-1$，且 $\sum 1=n$

将 $b$ 数组中 $-1$ 特别多的情况自己手玩一下，发现对于前缀和 $sum$ 而言，假设 $a[st]=a[ed]$，且区间 $(st,ed)$ 不再有 $a[i]=a[st]$ 的位置 $i$，那么 $sum[st:ed]$ 将会是一个公差为 $-1$ 的等差数列。

我们最终的目的仍然是需要求解“顺序对”的个数，所以线段树一定是跑不了的，考虑如何快速用线段树维护这个等差数列，以及计算这个等差数列的贡献。

回顾计算顺序对最朴素的方法：

枚举每个位置 $i$

$ans+=sum(-\infty :a[i]-1]$

将 $a[i]$ 放进线段树

假设我们需要维护的等差数列，$x$ 的坐标为 $[st,ed]$，$y$ 对应的区间为 $[L,R]$，更通俗的讲就是，$a[st]=R,a[st+1]=R-1,...,a[ed]=L$

然后我们就很神奇的发现，我们需要维护的这个等差数列，他自己不会提供给自己贡献。具体来说就是，因为对于每个位置 $i$，我们需要统计 $sum(-\infty :a[i]-1]$，而这个等差数列 $i$ 前面的位置都是大于 $a[i]$ 的，所以并不会提供贡献

所以根据上述朴素的方法，我们可以得到这个等差数列的贡献为：$\sum _{i=st}^{ed}\sum _{j=-\infty }^{i-1}sum[j]$

简单推导一下得到：
$$\begin{array}{rl}& \sum _{i=L}^R\sum _{j=-\infty }^{i-1}sum[j]\\ & =\sum _{i=L}^R(\sum _{j=-\infty }^{L-1}sum[j]+\sum _{j=L}^{i-1}sum[j])\\ & =(R-L+1)\ast \sum _{j=-\infty }^{L-1}sum[j]+\sum _{i=L}^R\sum _{j=L}^{i-1}sum[j]\\ & =(R-L+1)\ast \sum _{j=-\infty }^{L-1}sum[j]+\sum _{i=L}^R(R-i)\ast sum[i]\\ & =(R-L+1)\ast \sum _{j=-\infty }^{L-1}sum[j]+R\ast \sum _{i=L}^{R}sum[i]-\sum _{i=L}^{R}i\ast sum[i]\end{array}$$

然后我们发现，只需要用线段树维护一下 $sum[i]$ 和 $i\ast sum[i]$ 就好了，涉及到的操作只有区间加和区间查询，虽然说整体复杂度是 $O(nlogn)$ 的，但是常数大的离谱

代码：

// Problem: P4062 [Code+#1]Yazid 的新生舞会 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P4062 // Memory Limit: 500 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int BASE=500000; const int N=BASE+100; vector<int>node[N]; int a[N]; struct Node {int l,r,lazy;LL len,sum,sumi,i; }tree[N<<4]; void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;tree[k].sumi=tree[k<<1].sumi+tree[k<<1|1].sumi;tree[k].i=tree[k<<1].i+tree[k<<1|1].i; } void pushdown(int k) {if(tree[k].lazy) {LL lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;tree[k<<1].sum+=tree[k<<1].len*lz;tree[k<<1|1].sum+=tree[k<<1|1].len*lz;tree[k<<1].sumi+=tree[k<<1].i*lz;tree[k<<1|1].sumi+=tree[k<<1|1].i*lz;} } void build(int k,int l,int r) {tree[k]={l,r,0,r-l+1,0,0,0};if(l==r) {tree[k].i=l-BASE;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].lazy+=val;tree[k].sum+=tree[k].len*val;tree[k].sumi+=tree[k].i*val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); } LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].sum;}pushdown(k);return query(k<<1,l,r)+query(k<<1|1,l,r); } LL queryi(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].sumi;}pushdown(k);return queryi(k<<1,l,r)+queryi(k<<1|1,l,r); } int id(int x) {return x+BASE; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);build(1,0,BASE*2);int n,type;read(n),read(type);for(int i=0;i<n;i++) {node[i].push_back(0);}for(int i=1;i<=n;i++) {read(a[i]);node[a[i]].push_back(i);}for(int i=0;i<n;i++) {node[i].push_back(n+1);}LL ans=0;for(int i=0;i<n;i++) {if((int)node[i].size()==2) {//emptycontinue;}int sum=0;//calculateupdate(1,id(0),id(0),1);for(int j=1;j<(int)node[i].size();j++) {if(node[i][j]!=node[i][j-1]+1) {//[node[i][j-1],node[i][j]-1]int l=sum-(node[i][j]-node[i][j-1]-1),r=sum-1;ans+=(r-l+1)*query(1,0,id(l-1));ans+=r*query(1,id(l),id(r));ans-=queryi(1,id(l),id(r));update(1,id(l),id(r),1);sum=l;}if(node[i][j]!=n+1) {sum++;ans+=query(1,0,id(sum-1));update(1,id(sum),id(sum),1);}}sum=0;//clearupdate(1,id(0),id(0),-1);for(int j=1;j<(int)node[i].size();j++) {if(node[i][j]!=node[i][j-1]+1) {//[node[i][j-1],node[i][j]-1]int l=sum-(node[i][j]-node[i][j-1]-1),r=sum-1;update(1,id(l),id(r),-1);sum=l;}if(node[i][j]!=n+1) {sum++;update(1,id(sum),id(sum),-1);}}}cout<<ans<<endl;return 0; }

总结

以上是生活随笔为你收集整理的洛谷 - P4062 [Code+#1]Yazid 的新生舞会(推公式+线段树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。