我只是想找个treap的练习题……
每回找到lower_bound 就好啦
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
int n,m,a[200500],sum[200500],jy,ans,root,size;
struct Treap{int ch[2],v,cnt,sz,rnd;}tr[300500];
void Upd(int k){tr[k].sz=tr[tr[k].ch[0]].sz+tr[tr[k].ch[1]].sz+tr[k].cnt;}
void rot(int &k,bool f){int t=tr[k].ch[f];tr[k].ch[f]=tr[t].ch[!f],tr[t].ch[!f]=k,Upd(k),Upd(t),k=t;}
void insert(int &k,int num){
if(!k){k=++size,tr[k].cnt=tr[k].sz=1,tr[k].rnd=rand(),tr[k].v=num;return;}
tr[k].sz++;
if(tr[k].v==num){tr[k].cnt++;return;}
bool f=num>tr[k].v;
insert(tr[k].ch[f],num);
if(tr[k].rnd>tr[tr[k].ch[f]].rnd)rot(k,f);
}
void find(int k,int num){
if(!k)return;
if(tr[k].v<num)find(tr[k].ch[1],num);
else if(tr[k].v>num)jy=tr[k].v,find(tr[k].ch[0],num);
else find(tr[k].ch[0],num);
}
int bgn(int k){
if(tr[k].ch[0])return bgn(tr[k].ch[0]);
else return tr[k].v;
}
signed main(){
insert(root,0);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]=(a[i]%m+m)%m,sum[i]=(sum[i-1]+a[i])%m;
for(int i=1;i<=n;i++){
jy=-1,find(root,sum[i]);
if(~jy)ans=max(ans,(sum[i]-jy+m)%m);
else ans=max(ans,sum[i]-bgn(root));
insert(root,sum[i]);
}
printf("%lld
",ans);
}//By SiriusRen
#include <set>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
int n,m,a[200500],sum[200500],ans,jy;
set<int>s;
signed main(){
s.insert(0);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]=(a[i]%m+m)%m,sum[i]=(sum[i-1]+a[i])%m;
for(int i=1;i<=n;i++){
if(s.lower_bound(sum[i])!=s.end())ans=max(ans,(sum[i]-*s.lower_bound(sum[i])+m)%m);
else ans=max(ans,sum[i]-*s.begin());
s.insert(sum[i]);
}
printf("%lld
",ans);
}