欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Looksery Cup 2015 F. Yura and Developers(单调栈+二分+分治)(难*)

程序员文章站 2022-06-04 17:38:37
...

题目链接
Looksery Cup 2015 F. Yura and Developers(单调栈+二分+分治)(难*)
Looksery Cup 2015 F. Yura and Developers(单调栈+二分+分治)(难*)
题意:给定一个数组,问有多少区间满足:去掉最大值之后,和是k的倍数。
思路:日后补。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+2;
stack<int>s;
ll ans,sum[maxn],l[maxn],r[maxn];
vector<int>v[maxn];
int a[maxn];
int query(ll x,int l,int r)
{
	return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);
}
void slove()
{
	int n,k; 
	scanf("%d %d",&n,&k);
	v[0].push_back(0);
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
		sum[i]=(sum[i-1]+a[i])%k;
		v[sum[i]].push_back(i);
	}
	a[n+1]=1e9+7;
	s.push(0);
	for(int i=1;i<=n;++i)
	{
		while(s.size()>1&&a[s.top()]<a[i]) s.pop();
		l[i]=s.top();
		s.push(i);
	}
	while(!s.empty()) s.pop();
	s.push(n+1);
	for(int i=n;i>=1;--i)
	{
		while(s.size()>1&&a[s.top()]<=a[i]) s.pop();
		r[i]=s.top();
		s.push(i);
	}
	for(int i=1;i<=n;++i) a[i]%=k;
	for(int i=1;i<=n;++i)
	if(i-l[i]<r[i]-i)
	for(int j=l[i]+1;j<=i;++j) ans+=query((sum[j-1]+a[i])%k,i,r[i]-1);
	else for(int j=i;j<r[i];++j) ans+=query((sum[j]-a[i]+k)%k,l[i],i-1);
	printf("%lld\n",ans-n);
}
int main()
{
	slove();
}
相关标签: 单调栈/单调队列