[CSP-S模拟测试]:计划（前缀和）

题目传送门（内部题32）

输入格式

第一行，三个正整数$n,m,q$。
第二行，$n$个正整数$a_i$，保证$1\leqslant a_i\leqslant n$。
接下来$q$行，每行两个正整数$k,l$，保证$k<l$。

输出格式

输出$q$行，表示每个旅行计划询问的答案。

样例

样例输入：

7 2 7
6 1 3 6 4 6 5
1 2
4 6
2 7
6 7
1 2
1 4
2 6

样例输出：

1
4
35
1
1
10
20

数据范围与提示

对于$20\%$的数据，$2\leqslant n,q\leqslant 100$。
对于$40\%$的数据，$2\leqslant n,q\leqslant 1,000$。
对于$80\%$的数据，$2\leqslant n,q\leqslant 10,000$。
对于$100\%$的数据，$2\leqslant n,q\leqslant 100,000,1\leqslant m\leqslant n,1\leqslant a_i\leqslant n,1\leqslant k < l\leqslant n$。

题解

我们可以$\Theta(n^2)$的时间内求出对于每个左端点，最靠左的不乏味点的位置。

维护四个前缀和。

对于每一次询问，二分求出右端点，然后$\Theta(1)$前缀和就好了。

时间复杂度：$\Theta(n^2+q\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m,q;

int a[100001],sum,vis[100001];

long long cnt[100001];

pair<pair<long long,long long>,pair<long long,long long> > pos[100001];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

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

	{

		scanf("%d",&a[i]);

		cnt[i]=n+1;

	}

	vis[0]=sum=1;

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

	{

		vis[a[i-1]]--;

		if(vis[a[i-1]]){cnt[i]=cnt[i-1];continue;}

		sum--;

		for(int j=cnt[i-1]+1;j<=n;j++)

		{

			if(!vis[a[j]])sum++;

			vis[a[j]]++;

			if(sum>=m)

			{

				cnt[i]=j;

				break;

			}

		}

	}

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

	{

		pos[i].first.first=pos[i-1].first.first+i;

		pos[i].second.first=pos[i-1].second.first+i*cnt[i];

		pos[i].first.second=pos[i-1].first.second+cnt[i];

		pos[i].second.second=pos[i-1].second.second+cnt[i]*cnt[i];

	}

	while(q--)

	{

		long long l,r;

		scanf("%lld%lld",&l,&r);

		long long mid=upper_bound(cnt+l,cnt+r+1,r)-cnt-1;

		printf("%lld\n",((r*r+r)*(mid-l+1)-((r+1)*(pos[mid].first.first-pos[l-1].first.first)<<1)+pos[mid].first.second-pos[l-1].first.second+((pos[mid].second.first-pos[l-1].second.first)<<1)-pos[mid].second.second+pos[l-1].second.second)>>1);

	}

	return 0;

}

rp++

巴特西