题解 P4062 【[Code+#1]Yazid 的新生舞会】

人傻常数大…… 只是理论复杂度$O(nlogn)$实际上被$O(nlog^2n)$的解法爆踩 _________________ ## 本题题解 题意简单明了，求区间众数出现次数过半的子区间数目 那么我们会发现这是一个非常奇怪的限制，为什么一定要过半呢? 答案是这个条件保证了“新生舞会”的区间的众数是唯一的~~(那个相同就取最小的限制是唬你的)~~ 因此我们可以尝试枚举所有可能的众数值k，然后统计众数为k的新生舞会的区间有多少个，最后将这些数加起来就是我们要求的“新生舞会”的区间的总数目了 好了那么问题来了我们怎么求呢？ 一个简明易懂的想法是我们将所有等于k的数设成1，所有不是k的数字设成-1，然后我们会发现这个序列变成了一个+1,-1序列，此时众数为k的一个“新生舞会”的区间，和这个转化后的序列上一个区间和大于0的区间是一一对应的，因此我们只需求出这个序列有多少子区间和为0即可了 发现还是不好做，那么让我们接着转化 我们采取求区间和的经典套路，将区间和表示成两个前缀和相减的形式 那么我们要做的是对于每个i求出有多少j满足$sum_{i}>sum_{j}$且$i>j$这样的话就可以满足$[j+1,i]$这个区间和大于0了 换句话说就是求前缀和序列的顺序对个数咯 那么此时那个$A_{i}<=7$的部分分就非常可做了 **每次暴力扫一遍整个序列，树状数组求一遍顺序对即可了** 好了但是这个东西放到$A_{i}$无限制这个东西上面就立马炸了 考虑一下为什么会炸 假设我们在做一个1很少-1很多的序列 那么你会发现前缀和数组很多地方是一个公差为-1的等差数列 因为我们求的是顺序对，所以你会发现这段区间的顺序对显然是0 这样就非常的不好了…… 所以我们考虑你线段树求逆序对的过程 **foreach i** _1.ans+=线段树上$0,sum_{i}-1$的区间和_ _2.在线段树$sum_{i}$的位置加上1_ 然后我们现在尝试这将每一段等差数列一口气加到线段树里面 可以发现的是对应的修改应该是线段树上一段区间+1 并且发现另一个更为有趣的事实是由于每次插入的数刚好比前一个数少1，所以前面的数字有没有被插入根本不影响求区间和的过程 然后我们尝试着求出这个等差数列(从st到ed)对于答案的贡献，其中$cnt_{j}$ 是线段树所维护的数组 可以发现是这个式子 $$\sum_{i=st}^{ed}\sum_{j=- \infty}^{i-1}cnt_{j}$$ 简单的交换一发求和号就是 $$(ed-st+1)\sum_{i= -\infty}^{st-1}cnt_{i}+\sum_{i=st}^{ed}(ed-i)cnt_{i}$$ 所以我们只需要用线段树维护$cnt_{i}$以及$i×cnt_{i}$的和就行了,线段树所资瓷的操作是区间加 当然，对于那些不属于等差数列的前缀和点，我们求线段树的区间和，然后单点加就行了 这样的话,我们会发现对于每一个众数的值复杂度为$O(mlogn)$m为这个值在序列中的出现次数 所以总复杂度是$O(nlogn)$常数奇大无比，又加上我人懒直接吧线段树的值域开成了2n常数就更大了…… 上代码 ```C #include<cstdio> #include<algorithm> #include<vector> using namespace std;const int N=5*1e5+10;typedef long long ll; vector <int> po[N];int n;ll ans;int t; struct linetree//线段树 { ll sum[8*N];ll isum[8*N];ll add[8*N]; inline void pd(int p,int l,int r) { if(add[p]==0)return;int mid=(l+r)/2;int l1=mid-l;int l2=r-mid; sum[p<<1]+=add[p]*l1;add[p<<1]+=add[p];isum[p<<1]+=(add[p]*(l+1)+add[p]*mid)*l1/2; sum[p<<1|1]+=add[p]*l2;add[p<<1|1]+=add[p];isum[p<<1|1]+=(add[p]*(mid+1)+add[p]*r)*l2/2;add[p]=0; } inline void ud(int p){sum[p]=sum[p<<1]+sum[p<<1|1];isum[p]=isum[p<<1]+isum[p<<1|1];} inline void setadd(int p,int l,int r,int dl,int dr,ll ad) { if(dl==l&&dr==r){sum[p]+=ad*(r-l);isum[p]+=(ad*(l+1)+ad*r)*(r-l)/2;add[p]+=ad;return;} pd(p,l,r);int mid=(l+r)/2; if(dl<mid)setadd(p<<1,l,mid,dl,min(dr,mid),ad); if(mid<dr)setadd(p<<1|1,mid,r,max(dl,mid),dr,ad);ud(p); } inline ll gsum(int p,int l,int r,int dl,int dr,ll* val) { if(dl==l&&dr==r)return val[p];pd(p,l,r);int mid=(l+r)/2;ll res=0; if(dl<mid)res+=gsum(p<<1,l,mid,dl,min(dr,mid),val); if(mid<dr)res+=gsum(p<<1|1,mid,r,max(dl,mid),dr,val);return res; } inline void ins(int l,int r){setadd(1,0,2*n,n+l,n+r,1);} inline void ins(int x){setadd(1,0,2*n,n+x-1,n+x,1);} inline void del(int l,int r){setadd(1,0,2*n,n+l,n+r,-1);} inline void del(int x){setadd(1,0,2*n,n+x-1,n+x,-1);} inline ll csum(int l,int r,ll* val){return gsum(1,0,2*n,n+l,n+r,val);} }lt; inline void calc(ll st,ll ed) {ans+=(ed-st+1)*lt.csum(-n,st-1,lt.sum)+(ed+n)*lt.csum(st-1,ed,lt.sum)-lt.csum(st-1,ed,lt.isum);} int main() { scanf("%d%d",&n,&t); for(int i=1,t;i<=n;i++)scanf("%d",&t),po[t].push_back(i);lt.ins(0); for(int i=0;i<n;i++)//大力分情况讨论一下插入的等差序列就行了 { if(po[i].empty())continue;int up=po[i].size(); if(po[i][0]!=1)lt.ins(-po[i][0],-1);ans++;lt.ins(-po[i][0]+2); for(int j=1,st,ed;j<up;j++) { st=2*j-po[i][j]+1;ed=2*j-po[i][j-1]-1; if(st<=ed)calc(st,ed),lt.ins(st-1,ed);ans+=lt.csum(-n,st,lt.sum);lt.ins(st+1); }int ed=2*up-po[i][up-1]-1;int st=2*up-n;if(st<=ed)calc(st,ed); if(po[i][0]!=1)lt.del(-po[i][0],-1);lt.del(-po[i][0]+2); for(int j=1,st,ed;j<up;j++) {st=2*j-po[i][j]+1;ed=2*j-po[i][j-1]-1;if(st<=ed)lt.del(st-1,ed);lt.del(st+1);} }printf("%lld",ans);return 0; } ```