题解 | #智乃的最大子段#

解题思路

核心利用前缀和 + 有序映射（map） 优化查找

时间复杂度 O(n log n)

最大化模值： 若存在 pre[l] > pre[r]，则 (pre[r] - pre[l] + p) % p = pre[r] - pre[l] + p，值越大越好； 若所有 pre[l] ≤ pre[r]，则直接取 pre[r] - pre[l] 的最大值。

有序映射优化：用 map 存储已遍历的 pre 值及其下标，通过 upper_bound 快速找到第一个大于当前 pre[r] 的 pre[l]，计算第一种情况的最大值；同时检查 map 中最小的 pre[l]，计算第二种情况的最大值。

代码演示：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
const int N = 500010;
const int mod=1000000007;
int n,p;
map<int,int> mp;
void solve(){
	int pre=0,ans=-1,x,l,r;
	cin>>n>>p;
	mp[0]=0;
	for(int i=1; i<=n; i++){
		cin>>x;
		pre=(pre+x)%p;
		auto it=mp.upper_bound(pre);
		if(it!=mp.end()){
			int v=pre-it->first+p;
			if(v>ans){
				ans=v;
				l=it->second;
				r=i-1;
			}
		}
		pair<int,int> t=*mp.begin();
		if(t.first<=pre){
			int v=pre-t.first;
			if(v>ans){
				ans=v;
				l=it->second;
				r=i-1;
			}
		}
		mp[pre]=i;
	}
	cout<<l<<" "<<r<<" "<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}