probelm
题意
给定一个序列和一个mod值，定义[l,r]合法当l到r的所有元素和减去其中的最大值的结果能够整除mod。问共有多少区间合法。
思路
一开始想的分治。对于一个[l,r]我们可以把这之中最大的求出来，然后以这个数作为分界，把这个区间分成两部分，对于分布在两个区间中的答案，我们可以通过lowerbound和upperbunder在。所以这样做不行。。
看了题解，题解说可以直接枚举那个最大值，然后把满足的区间找出来然后求出来。豁然开朗。这样我们只需要把原数组进行排序，，并记录每个数的左右界。从最小的开始，在计算答案的同时去更新这个左右界。这样可以在的复杂度下求出答案。
一道不错的题。希望以后能够坚持把每次做的比赛的题目补完。
AC代码/*************************************************************************> File Name: pf.cpp> Author: znl1087> Mail: loveCJNforever@gmail.com> Created Time: 四 6/11 16:36:14 2015 ************************************************************************/;int n,k;LL s[300005];vector<int> f[1000005];LL num[300005];int pre[300005],nxt[300005];LL ask(int l,int r,LL in){return upper_bound(f[in].begin(),f[in].end(),r)-lower_bound(f[in].begin(),f[in].end(),l);}LL cal(int m){int l = pre[m]+1,r = nxt[m]-1;LL maxn = num[m];LL ans = 0;if( r – m < m – l){for(int i=m+1;i<=r;i++)ans+=(ask(l-1,m-1,(s[i]-maxn%k+k)%k));ans+=(ask(l-1,m-2,(s[m]-maxn%k+k)%k));}else{for(int i=l;i<m;i++)ans+=(ask(m,r,(s[i-1]+maxn)%k));ans+=(ask(m+1,r,(s[m-1]+maxn)%k));}pre[nxt[m]] = pre[m];nxt[pre[m]] = nxt[m];return ans;}int ord[300005];int cmp(int a,int b){return num[a]<num[b];}int main(){cin>>n>>k;s[0] = 0;for(int i=1;i<=n;i++){cin>>num[i],s[i] = (s[i-1]+num[i])%k,ord[i] = i;pre[i] = i-1;nxt[i] = i+1;}nxt[0] = 1;nxt[n] = n+1;pre[n+1] = n;for(int i=0;i<=n;i++)f[s[i]].push_back(i);sort(ord+1,ord+n+1,cmp);LL ans = 0;for(int i=1;i<=n;i++){int pos = ord[i];ans+=cal(pos);}cout<<ans<<endl;return 0;}
看看花儿冲破北疆漫漫寒冬，妖娆绽放;
