傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個序列$a$，讓你求有多少個子區間滿足存在一個數是這個區間的絕對眾數，絕對眾數指該數在區間內出現的次數嚴格大于$\frac{r?l+1}{2}$。
$n\le 5e5,0\le a_i\le n?1$

思路：

考慮將每個數單獨拿出來考慮貢獻，將選出來的數原來位置置為$1$，其余位置置為$?1$，設$sum$為修改后數組的前綴和，那么如果$[l,r]$滿足要求的話需要$su{m}_r?su{m}_{l?1}>r?l+1?(su{m}_r?su{m}_{l?1})$，令$l=l+1$并且移項得$2?su{m}_r?r>2?su{m}_l?l$，所以我們就可以維護一個樹狀數組，每次求一下$[?n,2?su{m}_r?r)$有多少數即可。
但是字符集很大，與$n$同階，直接計算是$n^{2}logn$的。
我們某個字符發現有$x$個的時候，可以分為$x+1$段，而且段內都是公差為$?1$的等差數列，單調遞減，所以段內數之間沒有貢獻，我們考慮將整個區間當成整體來看，這樣整體復雜度就從$n^2?>n$了。
怎么將整個區間看成整體呢？
考慮值有可能為負數，我們加一個偏移量即可。設$c_i$是值為$i$的個數，那么每次查詢完區間$[x,y]$，那么給$x,y$區間對應的權值加$1$即可，設$f_i={\sum }_{j=1}^i{c}_j$，代表權值的前綴和，那么$[x,y]$的答案就是${\sum }_{i=x?1}^{y?1}{f}_i$，又是一個前綴和的形式，我們考慮設$g_i={\sum }_{j=1}^i{f}_j$，那么答案就是$g_{y?1}?g_{x?2}$。
到目前位置我們就可以用線段樹實現這個二階前綴和即可，但是樹狀數組更快，所以考慮將$[x,y]$區間操作也打個差分，所以變成了三階前綴和，推導如下(侵刪)

所以維護一下$d_i,d_i?i,d_i?i?i$即可。

// 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("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") #define lowbit(x) ((x)&(-x)) using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } void rd_ac() { freopen("d://dp//in.in","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=4000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,type; LL tr1[N],tr2[N],tr3[N]; int a[N]; vector<int>pos[N];void add(int x,int c) {for(int i=x;i<=n*2+2;i+=lowbit(i)) {tr1[i]+=c;tr2[i]+=1ll*c*x;tr3[i]+=1ll*c*x*x;} }LL sum(int x) {if(x<=0) return 0;LL ans=0;for(int i=x;i;i-=lowbit(i)) ans+=tr1[i]*(x+2)*(x+1)-tr2[i]*(2*x+3)+tr3[i];return ans/2; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);// rd_ac();int _; scanf("%d",&_);while(_--) {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]].pb(i);int rc=n+1; LL ans=0;for(auto t:pos) {t.pb(n+1);int pre=0,cnt=0;for(auto now:t) {int x=2*cnt-(now-1)+rc,y=2*cnt-pre+rc;ans+=sum(y-1)-sum(x-2);add(x,1); add(y+1,-1);cnt++; pre=now;}pre=0; cnt=0;for(auto now:t) {int x=2*cnt-(now-1)+rc,y=2*cnt-pre+rc;add(x,-1); add(y+1,1);cnt++; pre=now;}}printf("%lld\n",ans);for(int i=1;i<=n;i++) pos[a[i]].clear();}return 0; } /**/

總結

以上是生活随笔為你收集整理的P4062 [Code+#1]Yazid 的新生舞会 树状数组维护三阶差分的全部內容，希望文章能夠幫你解決所遇到的問題。

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