题目描述

Description

给定一个长度为N的数组a和M，求一个区间[l,r]，使得() mod M的值最大，求出这个值，注意这里的mod是数学上的mod

Input

第一行两个整数N，M。
第二行N个整数a_i。

Output

输出一行，表示答案。

Sample Input

5 13
10 9 5 -5 7

Sample Output

11

HINT

【数据范围】
N<=200000，M,a_i<=10^18

题目分析

STL太强了
我们先预处理出每个位置的前缀%和
我们枚举到一个位置的时候 upperbound出和它最接近的前缀%和 因为两个前缀%和越接近 他们之间的和的模数一定越接近m
学习了一发set 的upper_bound

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long m;
set<long long> s;
long long sum[300100];
int main()
{   
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]=(sum[i]%m+sum[i-1]%m+(m<<1))%m;
    long long ans=0;
    s.insert(0);
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,sum[i]);
        ans=max(ans,(sum[i]-*s.upper_bound(sum[i])+m)%m);
        s.insert(sum[i]); 
    }
    printf("%lld",ans);
    return 0;
}