列表

详情

NC236497. Easy String Problem

描述

You are given a string with length , and the size of the alphabet also is .

There are  queries. For a query, you are given two integers  and you need to answer the number of different strings (which can be empty) that can be obtained by removing a substring containing .

输入描述

The first line contains one integer  (), denoting the length of the string .
The second line contains  integers  ().
The third line contains one integer  (), denoting the number of queries.
For the -th to -th lines, each line contains two integers  (), denoting a query.

输出描述

For each query, output a number in a line indicating the answer.

示例1

输入: 

4
1 2 3 1
6
1 1
3 3
2 3
2 4
1 3
1 4

输出: 

4
5
3
2
2
1

说明:

The string in the sample is equal to 'abca'.

For the first query :

'bca' can be obtained by removing substring .
'ca' can be obtained by removing substring .
'a' can be obtained by removing substring .
Empty string can be obtained by removing substring .
So the answer is .

For the third query :

'aa' can be obtained by removing substring .
'a' can be obtained by removing substring  or .
Empty string can be obtained by removing substring .

So the answer is .

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 160ms, 内存消耗: 6684K, 提交时间: 2022-11-09 14:32:00 

#include<bits/stdc++.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
#define fi   first
#define se   second
using namespace std;
int n,q,a[100005],cl[100005],cr[100005];
ll ans,b[100005];
pair<pair<int,int>,pair<int,int>> p[100005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",a+i);
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		int l,r;
		scanf("%d%d",&l,&r);
		--l,++r;
		p[i]=mp(mp(l/300,r),mp(l,i));
	}
	sort(p+1,p+q+1);
	int l=p[1].se.fi,r=p[1].fi.se;
	for(int i=1;i<=l;++i)++cl[a[i]];
	for(int i=r;i<=n;++i)++cr[a[i]];
	for(int i=1;i<=n;++i)ans+=cl[i]*1ll*cr[i];
	for(int i=1;i<=q;++i){
		int L=p[i].se.fi,R=p[i].fi.se;
		while(l>L)ans-=cr[a[l]],--cl[a[l]],--l;
		while(r<R)ans-=cl[a[r]],--cr[a[r]],++r;
		while(l<L)++l,ans+=cr[a[l]],++cl[a[l]];
		while(r>R)--r,ans+=cl[a[r]],++cr[a[r]];
		b[p[i].se.se]=(L+1ll)*(n-R+2ll)-ans;
	}
	for(int i=1;i<=q;++i)printf("%lld\n",b[i]);
    return 0;
}

C++ 解法, 执行用时: 92ms, 内存消耗: 4612K, 提交时间: 2022-04-17 12:12:48 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,B=320;
int n,a[N],q,l,r,i,cl[N],cr[N];
ll ans[N],tot;
struct query{
	int i,l,r;
	bool operator<(const query&rhs)const{
		return l/B==rhs.l/B?(l/B%2==1?r<rhs.r:r>rhs.r):l<rhs.l;
	}
}qu[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;for(i=1;i<=n;++i)cin>>a[i];
	cin>>q;
	for(i=1;i<=q;++i)cin>>qu[i].l>>qu[i].r,qu[i].i=i;
	sort(qu+1,qu+q+1);l=0;r=n+1;
	for(i=1;i<=q;++i){
		for(;l>=qu[i].l;)--cl[a[l]],tot-=cr[a[l]],--l;
		for(;r<=qu[i].r;)--cr[a[r]],tot-=cl[a[r]],++r;
		for(;l<qu[i].l-1;)++l,++cl[a[l]],tot+=cr[a[l]];
		for(;r>qu[i].r+1;)--r,++cr[a[r]],tot+=cl[a[r]];
		ans[qu[i].i]=1ll*(l+1)*(n+1-r+1)-tot;
	}
	for(i=1;i<=q;++i)cout<<ans[i]<<'\n';
	return 0;
}

上一题

© 2024 nowcoder.com