题解 | #E#

题目

输入

输出

思路

题目要求最大的子段和，可以先将数组求前缀和，转换为求最大的sum[r]-sum[l-1]。

同时由于要对p进行取模，所以前缀和的数据并非递增的，sum[r]-sum[l-1]就可能为负数，进而结果就要加p，保证取模结果是正数。

对r进行遍历，要使子段和最大l有两者情况。

l为sum[0]~sum[r]中比sum[r]大一点的元素，或者l为sum[0]~sum[r]最小的元素。

可以证明如果存在比sum[r]的元素，那么它比最小元素更优。

同时为了快速查找比sum[r]大一点的元素，可以用map存储r之前的元素和它的下标，使用upper_bound()二分查找map。

注意0<=l<=r<n-1,最后要对r,l位置进行更新。

完整代码

```#include<bits/stdc++.h>
using namespace std;
typedef int long long;
signed main(){
    int n,p;
    cin>>n>>p;
    vector<int> v1(n+5);
    vector<int> he(n+5);
    for(int i=0;i<n;i++){
        cin>>v1[i];
        he[i+1]=(he[i]+v1[i])%p;
    }
    map<int,int> f;
    int l=0,r=0,ans=0;
    for(int i=0;i<=n;i++){
        if(i){
            auto it=f.upper_bound(he[i]);
            if(it==f.end()){
                it=f.begin(); 
            }
            int v=(he[i]-it->first+p)%p;
            if(v>ans){
               ans=v;
                r=i-1;
                l=it->second;
            }
            
        }
        f[he[i]]=i;
    }
    cout<<l<<" "<<r<<" "<<ans;
    return 0;
}