ACM模板

---

放暑假了，回歸！！！
自己不會寫暴力，而且好久沒寫代碼了，于是學學分塊的優雅暴力~

「分塊入門-LibreOJ」
「分塊」數列分塊入門1 – 9 by hzwer

數列簡單分塊問題實際上有三項東西要我們思考：

對于每次區間操作：

不完整的塊 的$O(\sqrt{n})$個元素怎么處理？

$O(\sqrt{n})$個 整塊 怎么處理？

要預處理什么信息（復雜度不能超過后面的操作一般$O(N\sqrt{N})$預處理）

下面假設塊的大小為$M$

#6277. 數列分塊入門 1

小塊暴力，大塊懶標記，只需要思考如何快速查詢塊內的答案即可

#include<bits/stdc++.h>using namespace std;constexpr int N=500010;int a[N],n; int b[N]; int sz; void modify(int l,int r,int c) {int idl=l/sz,idr=r/sz;if(idl==idr){for(int i=l;i<=r;i++) a[i]+=c;return;}for(int i=l;i<(idl+1)*sz;i++) a[i]+=c;for(int i=idl+1;i<idr;i++) b[i]+=c;for(int i=idr*sz;i<=r;i++) a[i]+=c; } int query(int r){return a[r]+b[r/sz];} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;sz=sqrt(n);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)modify(l,r,c);elsecout<<query(r)<<'\n';}return 0; }

#6278. 數列分塊入門 2

不完整的塊只需要暴力掃一遍，單詞詢問復雜度$O(M)$
完整的塊內維護有序數列，每次要二分詢問，單詞詢問復雜度為$O(\frac{N}{M}\log M)$

詢問復雜度$O\{K(M+\frac{N}{M}\log M)\}$’

顯然區間假發對于完整的快來說不改變塊內的順序，而不完整的塊每次只需要重新排序暴力維護一邊即可，每次只可能有兩個不完整的塊，因此單詞修改時間復雜度$O(M\log M)$

修改時間復雜度$O\{K(M\log M+\frac{N}{M})\}$

#include<bits/stdc++.h>using namespace std;constexpr int N=50010;int n,a[N],b[N]; int sz; vector<int> vec[810]; int s[N]; void reset(int o) {vec[o].clear();for(int i=(o-1)*sz+1;i<=min(o*sz,n);i++) vec[o].push_back(a[i]);sort(vec[o].begin(),vec[o].end()); } void update(int l,int r,int c) {if(b[l]==b[r]){for(int i=l;i<=r;i++) a[i]+=c;reset(b[l]);//重排序return;}for(int i=l;i<=sz*b[l];i++) a[i]+=c; reset(b[l]);for(int i=(b[r]-1)*sz+1;i<=r;i++) a[i]+=c; reset(b[r]);for(int i=b[l]+1;i<b[r];i++) s[i]+=c; //完整的塊直接加 } int query(int l,int r,int c) {int ans=0;if(b[l]==b[r]){for(int i=l;i<=r;i++) ans+=(a[i]+s[b[i]]<c?1:0);return ans;}for(int i=l;i<=sz*b[l];i++) ans+=(a[i]+s[b[i]]<c?1:0);for(int i=(b[r]-1)*sz+1;i<=r;i++) ans+=(a[i]+s[b[i]]<c?1:0);for(int i=b[l]+1;i<b[r];i++)ans+=lower_bound(vec[i].begin(),vec[i].end(),c-s[i])-vec[i].begin();return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1, vec[b[i]].push_back(a[i]);for(int i=1;i<=b[n];i++) sort(vec[i].begin(),vec[i].end());for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)update(l,r,c);elsecout<<query(l,r,c*c)<<'\n';}return 0; }

#6279. 數列分塊入門 3

接著第二題的解法，其實只要把塊內查詢的二分稍作修改即可。

不過這題其實想表達：可以在塊內維護其它結構使其更具有拓展性，比如放一個 set ，這樣如果還有插入、刪除元素的操作，會更加的方便。

#include<bits/stdc++.h>using namespace std;constexpr int N=100010;int n,a[N],b[N]; int sz; vector<int> vec[1010]; int s[N]; void reset(int o) {vec[o].clear();for(int i=(o-1)*sz+1;i<=min(o*sz,n);i++) vec[o].push_back(a[i]);sort(vec[o].begin(),vec[o].end()); } void update(int l,int r,int c) {if(b[l]==b[r]){for(int i=l;i<=r;i++) a[i]+=c;reset(b[l]);return;}for(int i=l;i<=sz*b[l];i++) a[i]+=c; reset(b[l]);for(int i=(b[r]-1)*sz+1;i<=r;i++) a[i]+=c; reset(b[r]);for(int i=b[l]+1;i<b[r];i++) s[i]+=c; } int query(int l,int r,int c) {int ans=-1;if(b[l]==b[r]){for(int i=l;i<=r;i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);return ans;}for(int i=l;i<=sz*b[l];i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);for(int i=(b[r]-1)*sz+1;i<=r;i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);for(int i=b[l]+1;i<b[r];i++){auto t=lower_bound(vec[i].begin(),vec[i].end(),c-s[i]);if(t!=vec[i].begin()) --t;if(*t<c-s[i]) ans=max(ans,*t+s[i]);}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1, vec[b[i]].push_back(a[i]);for(int i=1;i<=b[n];i++) sort(vec[i].begin(),vec[i].end());for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)update(l,r,c);elsecout<<query(l,r,c)<<'\n';}return 0; }

multiset

#include<bits/stdc++.h>using namespace std;constexpr int N=100010;int n,a[N],b[N]; int sz; multiset<int> st[1010]; int s[N];void update(int l,int r,int c) {if(b[l]==b[r]){for(int i=l;i<=r;i++) st[b[l]].erase(st[b[l]].find(a[i])),st[b[l]].insert(a[i]+c),a[i]+=c;return;}for(int i=l;i<=sz*b[l];i++) st[b[l]].erase(st[b[l]].find(a[i])),st[b[l]].insert(a[i]+c),a[i]+=c;for(int i=(b[r]-1)*sz+1;i<=r;i++) st[b[r]].erase(st[b[r]].find(a[i])),st[b[r]].insert(a[i]+c),a[i]+=c;for(int i=b[l]+1;i<b[r];i++) s[i]+=c; } int query(int l,int r,int c) {int ans=-1;if(b[l]==b[r]){for(int i=l;i<=r;i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);return ans;}for(int i=l;i<=sz*b[l];i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);for(int i=(b[r]-1)*sz+1;i<=r;i++) if(a[i]+s[b[i]]<c) ans=max(ans,a[i]+s[b[i]]);for(int i=b[l]+1;i<b[r];i++){auto t=st[i].lower_bound(c-s[i]);if(t!=st[i].begin()) --t;if(*t<c-s[i]) ans=max(ans,*t+s[i]);}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1, st[b[i]].insert(a[i]);for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)update(l,r,c);elsecout<<query(l,r,c)<<'\n';}return 0; }

#6280. 數列分塊入門 4

詢問變成了區間上的詢問，不完整的塊還是暴力；而要想快速統計完整塊的答案，需要維護每個塊的元素和，先要預處理一下。

考慮區間修改操作，不完整的塊直接改，順便更新塊的元素和；完整的塊類似之前標記的做法，直接根據塊的元素和所加的值計算元素和的增量。

#include<bits/stdc++.h>using namespace std;constexpr int N=100010;int n,a[N],b[N]; int sz; long long s[N],tag[N]; void update(int l,int r,int c) {if(b[l]==b[r]){for(int i=l;i<=r;i++) a[i]+=c,s[b[i]]+=c;return;}for(int i=l;i<=sz*b[l];i++) a[i]+=c,s[b[i]]+=c;for(int i=(b[r]-1)*sz+1;i<=r;i++) a[i]+=c,s[b[i]]+=c;for(int i=b[l]+1;i<b[r];i++) s[i]+=1ll*c*sz,tag[i]+=c; } long long query(int l,int r,int mod) {long long ans=0;if(b[l]==b[r]){for(int i=l;i<=r;i++) ans+=a[i]+tag[b[i]],ans%=mod;return ans;}for(int i=l;i<=sz*b[l];i++) ans+=a[i]+tag[b[i]],ans%=mod;for(int i=(b[r]-1)*sz+1;i<=r;i++) ans+=a[i]+tag[b[i]],ans%=mod;for(int i=b[l]+1;i<b[r];i++) ans+=s[i],ans%=mod;return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1,s[b[i]]+=a[i];for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)update(l,r,c);elsecout<<query(l,r,c+1)<<'\n';}return 0; }

#6281. 數列分塊入門 5

對于一個數，開方多次后就會變成1
不完整的塊直接暴力開方，而完整的塊記錄下當前塊內的數是不是已經全為1了，如果全為1就不需要開發，如果不是暴力開方。

#include<bits/stdc++.h>using namespace std;constexpr int N=100010;int n,a[N],b[N]; int sz; int s[N],fg[N]; void solve(int k) {if(fg[k]) return; // 該塊已經全為1了fg[k]=1;s[k]=0;for(int i=(k-1)*sz+1;i<=k*sz;i++) //暴力開方{a[i]=sqrt(a[i]);s[k]+=a[i];if(a[i]>1) fg[k]=0;} } void update(int l,int r) {if(b[l]==b[r]) {for(int i=l;i<=r;i++) s[b[i]]-=a[i],a[i]=sqrt(a[i]),s[b[i]]+=a[i];return;}for(int i=l;i<=b[l]*sz;i++) s[b[i]]-=a[i],a[i]=sqrt(a[i]),s[b[i]]+=a[i];for(int i=(b[r]-1)*sz+1;i<=r;i++) s[b[i]]-=a[i],a[i]=sqrt(a[i]),s[b[i]]+=a[i];for(int i=b[l]+1;i<b[r];i++) solve(i); } int query(int l,int r) {int ans=0;if(b[l]==b[r]){for(int i=l;i<=r;i++) ans+=a[i];return ans;}for(int i=l;i<=b[l]*sz;i++) ans+=a[i];for(int i=(b[r]-1)*sz+1;i<=r;i++) ans+=a[i];for(int i=b[l]+1;i<b[r];i++) ans+=s[i];return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1,s[b[i]]+=a[i];for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)update(l,r);elsecout<<query(l,r)<<'\n';}return 0; }

#6282. 數列分塊入門 6

隨機數據的情況

我們完整塊內可以用數組以外的數據結構，能夠支持其它不一樣的操作，比如此題每塊內可以放一個動態的數組vector，每次插入時先找到位置所在的塊，再暴力插入，把塊內的其它元素直接向后移動一位，當然用鏈表也是可以的。

如果先在一個塊有大量單點插入，這個塊的大小會大大超過√n，那塊內的暴力就沒有復雜度保證了。

每$\sqrt{N}$插入后，重新把數列平均分一下塊，重構需要的復雜度為O(N)，重構的次數為$\sqrt{N}$，所以重構的復雜度沒有問題，而且保證了每個塊的大小相對均衡。
當然，也可以當某個塊過大時重構，或者只把這個塊分成兩半。

#include<bits/stdc++.h>using namespace std;constexpr int N=200010; int a[N],b[N]; int n,m,sz; vector<int> vec[1010]; int bkp[N];pair<int,int> query(int k) {int now=1;while(k>vec[now].size()){k-=vec[now].size();now++;}return make_pair(now,k-1);//vector 下標從0開始 } void rebuild() {int tot=0;for(int i=1;i<=m;i++){for(auto t:vec[i]) bkp[++tot]=t;vec[i].clear();}int gap=sqrt(tot);for(int i=1;i<=tot;i++) b[i]=(i-1)/gap+1,vec[b[i]].push_back(bkp[i]);m=(tot-1)/gap+1; } void insert(int k,int x) {auto t=query(k);vec[t.first].insert(vec[t.first].begin()+t.second,x);if(vec[t.first].size()>20*sz) rebuild(); } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1,vec[b[i]].push_back(a[i]);m=(n-1)/sz+1;for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)insert(l,r);else{auto t=query(r);cout<<vec[t.first][t.second]<<'\n';}}return 0; }

#6283. 數列分塊入門 7

類似線段樹的區間+和區間×即可。
每次區間×的時候可以reset一下，去除以前的塊標記。

#include<bits/stdc++.h>using namespace std;constexpr int N=200010; constexpr int mod=10007; int a[N],b[N]; int n,m,sz; int tga[N],tgm[N]; int query(int k){return (a[k]*tgm[b[k]]%mod+tga[b[k]])%mod;} void reset(int k) {for(int i=(k-1)*sz+1;i<=min(n,sz*k);i++) a[i]=query(i);tga[k]=0,tgm[k]=1; } void add(int l,int r,int c) {if(b[l]==b[r]){reset(b[l]);for(int i=l;i<=r;i++) a[i]+=c,a[i]%=mod;return;}reset(b[l]),reset(b[r]);for(int i=l;i<=b[l]*sz;i++) a[i]+=c,a[i]%=mod;for(int i=(b[r]-1)*sz+1;i<=r;i++) a[i]+=c,a[i]%=mod;for(int i=b[l]+1;i<b[r];i++) tga[i]+=c,tga[i]%=mod; } void mul(int l,int r,int c) {c%=mod;if(b[l]==b[r]){reset(b[l]);for(int i=l;i<=r;i++) a[i]*=c,a[i]%=mod;return;}reset(b[l]),reset(b[r]);for(int i=l;i<=b[l]*sz;i++) a[i]*=c,a[i]%=mod;for(int i=(b[r]-1)*sz+1;i<=r;i++) a[i]*=c,a[i]%=mod;for(int i=b[l]+1;i<b[r];i++) tgm[i]*=c,tgm[i]%=mod,tga[i]*=c,tga[i]%=mod; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1;for(int i=1;i<=b[n];i++) tgm[i]=1;for(int i=1;i<=n;i++){int op,l,r,c;cin>>op>>l>>r>>c;if(op==0)add(l,r,c);else if(op==1)mul(l,r,c);elsecout<<query(r)<<'\n';}return 0; }

#6284. 數列分塊入門 8

區間修改沒有什么難度，這題難在區間查詢比較奇怪，因為權值種類比較多，似乎沒有什么好的維護方法。

模擬一些數據可以發現，詢問后一整段都會被修改，幾次詢問后數列可能只剩下幾段不同的區間了。

我們思考這樣一個暴力，還是分塊，維護每個分塊是否只有一種權值，區間操作的時候，對于同權值的一個塊就O(1)統計答案，否則暴力統計答案，并修改標記，不完整的塊也暴力。

這樣看似最差情況每次都會耗費O(n)的時間，但其實可以這樣分析：

假設初始序列都是同一個值，那么查詢是O(√n)，如果這時進行一個區間操作，它最多破壞首尾2個塊的標記，所以只能使后面的詢問至多多2個塊的暴力時間，所以均攤每次操作復雜度還是O(√n)。

換句話說，要想讓一個操作耗費O(n)的時間，要先花費√n個操作對數列進行修改。

初始序列不同值，經過類似分析后，就可以放心的暴力啦。

#include<bits/stdc++.h>using namespace std;constexpr int N=100010; constexpr int mod=10007; int a[N],b[N]; int n,m,sz; int tg[N]; void reset(int k) {if(tg[k]==-1) return;for(int i=(k-1)*sz+1;i<=min(n,k*sz);i++) a[i]=tg[k];tg[k]=-1; } int solve(int l,int r,int c) {int ans=0;reset(b[l]);for(int i=l;i<=min(r,b[l]*sz);i++){if(a[i]==c) ans++;else a[i]=c;}if(b[l]!=b[r]){reset(b[r]);for(int i=(b[r]-1)*sz+1;i<=r;i++){if(a[i]==c) ans++;else a[i]=c;}}for(int i=b[l]+1;i<b[r];i++){if(tg[i]!=-1){if(tg[i]==c) ans+=sz;else tg[i]=c;}else{for(int j=(i-1)*sz+1;j<=i*sz;j++){if(a[j]==c) ans++;else a[j]=c;}tg[i]=c;}}return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sz=sqrt(n);memset(tg,-1,sizeof tg);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1;for(int i=1;i<=n;i++){int l,r,c;cin>>l>>r>>c;cout<<solve(l,r,c)<<'\n';}return 0; }

#6285. 數列分塊入門 9

由于$a_i$在$[?2^{31},2^{31}?1]$，因此需要離散化

然后建立一個vector<int>vec[N]存儲每個數出現的位置，有了這個,我們就可以二分查找出一個數在區間l~r內出現的次數
區間眾數一定是大塊的眾數或者是邊界小塊出現過的數
預處理大塊之間的眾數，小塊暴力查詢每個數在[l,r]出現的次數。

如果塊的大小為$\sqrt{N}$，時間復雜度為$O\{N\sqrt{N}\log N\}$

#include<bits/stdc++.h>using namespace std;constexpr int N=100010; constexpr int mod=10007; int a[N],va[N],b[N]; int n,m,sz; int idx; int dp[1005][1005]; vector<int> vec[N]; int rd() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } void prework() {// 離散化sort(va+1,va+1+m);m=unique(va+1,va+1+m)-va-1;for(int i=1;i<=n;i++) {a[i]=lower_bound(va+1,va+1+m,a[i])-va;vec[a[i]].push_back(i);}sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1;// 預處理塊眾數for(int k=1;k<=b[n];k++){static int cnt[N];memset(cnt,0,sizeof cnt);int ans=0,mx=0;for(int i=(k-1)*sz+1;i<=n;i++){cnt[a[i]]++;if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&va[a[i]]<va[ans])){ans=a[i];mx=cnt[a[i]];}dp[k][b[i]]=ans;}} } int solve(int l,int r,int x){return upper_bound(vec[x].begin(),vec[x].end(),r)-lower_bound(vec[x].begin(),vec[x].end(),l);} int query(int l,int r) {int ans=dp[b[l]+1][b[r]-1];int mx=solve(l,r,ans);for(int i=l;i<=min(r,sz*b[l]);i++){int tmp=solve(l,r,a[i]);if(tmp>mx||(tmp==mx&&va[a[i]]<va[ans])){mx=tmp;ans=a[i];}}if(b[l]!=b[r]){for(int i=(b[r]-1)*sz+1;i<=r;i++){int tmp=solve(l,r,a[i]);if(tmp>mx||(tmp==mx&&va[a[i]]<va[ans])){mx=tmp;ans=a[i];}}}return ans; } int main() {n=rd();for(int i=1;i<=n;i++){a[i]=rd();va[++m]=a[i];}prework();for(int i=1;i<=n;i++){int l=rd(),r=rd();printf("%d\n",va[query(l,r)]);}return 0; }

如何快速查詢塊之間一個數出現次數？
預處理s[i][j]前綴和 0~i塊中j出現的次數
小塊暴力枚舉，大塊查表
這樣的時間復雜度是標準的$O(N\sqrt{N})$

#include<bits/stdc++.h>using namespace std;constexpr int N=100010; constexpr int mod=10007; int a[N],va[N],b[N]; int n,m,sz; int dp[1005][1005]; int s[1005][N]; int rd() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } void prework() {// 離散化sort(va+1,va+1+m);m=unique(va+1,va+1+m)-va-1;for(int i=1;i<=n;i++) a[i]=lower_bound(va+1,va+1+m,a[i])-va;sz=sqrt(n);for(int i=1;i<=n;i++) b[i]=(i-1)/sz+1;// 預處理塊眾數for(int k=1;k<=b[n];k++){static int cnt[N];memset(cnt,0,sizeof cnt);int ans=0,mx=0;for(int i=(k-1)*sz+1;i<=n;i++){cnt[a[i]]++;if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&va[a[i]]<va[ans])){ans=a[i];mx=cnt[a[i]];}dp[k][b[i]]=ans;}}//預處理前綴和塊for(int i=1;i<=n;i++){s[b[i]][a[i]]++;if(b[i+1]!=b[i])// i是該塊的最后一個for(int j=1;j<=n;j++) s[b[i]][j]+=s[b[i]-1][j];} } int solve(int l,int r,int x) {if(l>r) return 0;return s[r][x]-s[l-1][x]; } int query(int l,int r) {int ans=dp[b[l]+1][b[r]-1];// 塊間眾數int mx=solve(b[l]+1,b[r]-1,ans);static int mp[N];memset(mp,0,sizeof mp);for(int i=l;i<=min(r,sz*b[l]);i++) mp[a[i]]++;if(b[l]!=b[r]) for(int i=(b[r]-1)*sz+1;i<=r;i++) mp[a[i]]++;for(int i=l;i<=min(r,sz*b[l]);i++)if((mp[a[i]]+solve(b[l]+1,b[r]-1,a[i])>mx)||(mp[a[i]]+solve(b[l]+1,b[r]-1,a[i])==mx&&va[a[i]]<va[ans])){mx=mp[a[i]]+solve(b[l]+1,b[r]-1,a[i]);ans=a[i];}if(b[l]!=b[r]) for(int i=(b[r]-1)*sz+1;i<=r;i++){if((mp[a[i]]+solve(b[l]+1,b[r]-1,a[i])>mx)||(mp[a[i]]+solve(b[l]+1,b[r]-1,a[i])==mx&&va[a[i]]<va[ans])){mx=mp[a[i]]+solve(b[l]+1,b[r]-1,a[i]);ans=a[i];}}return va[ans]; } int main() {n=rd();for(int i=1;i<=n;i++){a[i]=rd();va[++m]=a[i];}prework();for(int i=1;i<=n;i++){int l=rd(),r=rd();printf("%d\n",query(l,r));}return 0; }

要加油哦~

總結

以上是生活随笔為你收集整理的「分块」数列分块入门1 – 9的全部內容，希望文章能夠幫你解決所遇到的問題。

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