BZOJ 3544 [ONTAK2010]Creative Accounting

题目大意

给你一个数列，求一个区间[L,R]使得$\sum\limits_{i=l}^{r} a_i (\mod M)$最大。

---

这道题直接思考模运算的性质：由于没有修改当然要使用前缀和维护，之后考虑对于每一个前缀和有两种情况：

1. 维持现状，使用这个前缀和。本来应该是这个前缀和减去之前最小的前缀和的，但是发现最小的前缀和是0 = =
2. 让他溢出。就是让他减去一个比它大的数从而溢出回一个很大的值。要减去的数当然是它之前所有数的upper_bound(a[i])啦

之后就是重点：如何维护？ 权值线段树！当然不用那么搞。因为只是简单找后继，所以就够了。

注意set的常数虽然不大但是也比权值线段树高到不知道哪里去了。预计进行最大插入-查询个数为500000,本题需要次数200000,问题不大。

常用函数

• begin(),end() => 返回一个iterator指针，指向头(min)/尾(max)。
• count() => 返回这个数出现的次数（在set中只会有1/0）
• upper_bound()/lower_bound() => 返回比这个数大/小的第一个数的指针
• insert() => 插入一个数
• erase() => 删除一个数
• clear() => 清空set

直接s.xxx()就可以了qwq

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