題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的序列，現在要求存在 絕對眾數 的子區間個數

所謂 絕對眾數，就是對于區間 $[l,r]$ 來說，存在一個數字的出現次數 $cnt$，滿足不等式 $cnt?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)?\sum _{j=?\infty }^{L?1}sum[j]+\sum _{i=L}^R\sum _{j=L}^{i?1}sum[j]\\ & =(R?L+1)?\sum _{j=?\infty }^{L?1}sum[j]+\sum _{i=L}^R(R?i)?sum[i]\\ & =(R?L+1)?\sum _{j=?\infty }^{L?1}sum[j]+R?\sum _{i=L}^{R}sum[i]?\sum _{i=L}^{R}i?sum[i]\end{array}$$

然后我們發現，只需要用線段樹維護一下 $sum[i]$ 和 $i?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 的新生舞会(推公式+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。