●CodeForces 549F Yura and Developers

题链：

http://codeforces.com/problemset/problem/549/F
题解：

分治，链表。
考虑对于一个区间[L,R],其最大值在p位置，
那么答案的贡献就可以分为3部分：
1.[L,p-1]中合法的区间
2.[p+1,R]中合法的区间
3.[L,R]中经过p的合法区间。
前两个因为是相同子问题，可以递归解决。
考虑如何求出3.的答案。
令S[i]表示$\sum_{k=1}^{i}A[i]$(即前缀和)
显然对于一组(l,r)表示的区间[l,r]，
当且仅当满足L<=l<=p且p<r<=R(或L<=l<p且p<=r<=R)，
并且 S[r]-S[l-1]-A[p]≡0 (mod K)时，才是合法区间。

但是如果直接递归实现，复杂度高达O(N^2)
所以预处理出每个元素在哪个包含它的最大区间里是最大值。
可以用单调栈O(N)维护出。
然后对于每个元素以及刚刚得出来的区间去计算贡献。
同时在计算贡献时，采用的方法是：
枚举一边的元素，然后用形如Query(ql,qr,qv)的方式去询问另一边S[*]==qv的个数
至于枚举哪一边，就是哪边短就枚举哪一边，这样可以保证询问次数为nlogn次的。
然后考虑如何询问。
如果采用主席树，则需要把复杂度再乘上一个log的询问代价，总的复杂度为O(N logN logN)
或者把询问离线成差分形式，插入链表，最后扫描链表O(N logN)得出答案(链表元素有N logN个)，总的复杂度为O(N logN)
比如说对于询问Query(l,r,v)拆成两个(v,sign)的形式,我们在链表l-1中加入(v,-1)，在链表r中加入(v,1)
最后从i=0到N扫描一遍，首先cnt[S[i]]++,(cnt[x]表示前缀i中x这个值出现了多少次)
然后再扫描i的询问链表，把ans+=cnt[v]*sign即可。
最后的ans既是答案。

代码：

#include<bits/stdc++.h>

#define MAXN 300050

#define INF 0x3f3f3f3f

using namespace std;

int N,K,more;

int A[MAXN],S[MAXN],L[MAXN],R[MAXN];

struct LINK{

	int lnt;

	int nxt[MAXN*20],val[MAXN*20],sign[MAXN*20],head[MAXN];

	LINK(){lnt=2;}

	void Add(int u,int v,int s){

		if(u<0) return;

		val[lnt]=v; sign[lnt]=s; nxt[lnt]=head[u]; head[u]=lnt++;

	}

	void Query(int l,int r,int v){

		Add(l-1,v,-1); Add(r,v,1);

	}

	long long Getans(){

		long long ret=0;

		static int cnt[1000050];

		for(int i=0;i<=N;i++){

			cnt[S[i]]++;

			for(int j=head[i];j;j=nxt[j])

				ret+=sign[j]*cnt[val[j]];

		}

		return ret;

	}

}Q;

void prework(){

	static int stk[MAXN],top;

	A[0]=A[N+1]=INF;

	stk[top=1]=0;

	for(int i=1;i<=N;i++){

		while(A[stk[top]]<=A[i]) top--;

		L[i]=stk[top]+1; stk[++top]=i;

	}

	stk[top=1]=N+1;

	for(int i=N;i>=1;i--){

		while(A[stk[top]]<A[i]) top--;

		R[i]=stk[top]-1; stk[++top]=i;

	}

	for(int i=1;i<=N;i++)

		S[i]=(S[i-1]+A[i])%K;

}

void solve(){

	int al,ar,qv,ql,qr,sign;

	for(int i=1;i<=N;i++){

		if(L[i]==R[i]) continue;

		more++;

		if(i-L[i]+1<=R[i]-i+1) al=L[i]-1,ar=i-1,ql=i,qr=R[i],sign=1;

		else al=i,ar=R[i],ql=L[i]-1,qr=i-1,sign=-1;

		for(int j=al;j<=ar;j++){

			qv=(1ll*S[j]+sign*A[i]%K+K)%K;

			Q.Query(ql,qr,qv);

		}

	}

}

int main(){

	scanf("%d%d",&N,&K);

	for(int i=1;i<=N;i++) scanf("%d",&A[i]);

	prework();

	solve();

	long long ans=Q.Getans();

	printf("%lld\n",ans-more);

	return 0;

}

巴特西

●CodeForces 549F Yura and Developers

最新文章

热门文章