probelm
题意
给定一个序列和一个mod值，定义[l,r]合法当l到r的全部元素和减去当中的最大值的结果能够整除mod。问共同拥有多少区间合法。
思路
一開始想的分治。
对于一个[l,r]我们能够把这之中最大的求出来，然后以这个数作为分界，把这个区间分成两部分，对于分布在两个区间中的答案，我们能够通过lowerbound和upperbunder在O(log(n))的时间下求出，然后递归求解。
然而对于这题，这样的做法的下界会达到O(n2)。所以这样做不行。
。
看了题解，题讲解能够直接枚举那个最大值，然后把满足的区间找出来然后求出来。豁然开朗。这样我们仅仅须要把原数组进行排序，并记录每一个数的左右界。
从最小的開始。在计算答案的同一时候去更新这个左右界。
这样能够在O(nlog(n))的复杂度下求出答案。
一道不错的题。希望以后能够坚持把每次做的比赛的题目补完。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
using namespace std;
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;
}
转载于:https://www.cnblogs.com/bhlsheji/p/5314202.html
相关资源：数据结构—成绩单生成器
