本文共 1892 字，大约阅读时间需要 6 分钟。

题目描述

输入格式

输出格式

输入输出样例

4 21 2 3 21 32 4

输出 #1

YesNo

说明/提示

题意：给出许多区间查询，判断区间中所有的数是否互不相同，是则输入 Yes ，否则输出 No 。

思路：基础莫队题。

代码如下：

#include 
   
    using namespace std;const int maxn = 1e5 + 5;int a[maxn];int pos[maxn];bool ans[maxn];		//第几个询问的区间中是否每个数都互不相同 int cnt[maxn];		//记录区间[l,r]中的每个数的出现次数 struct Q {
   	int l, r, i;} q[maxn];//题目询问的是区间[l,r]中的所有数是否互不相同,转换为//[l,r]中互不相同的数的个数是否等于区间大小r-l+1,等于则互不相同,否则存在相同的数 int res = 0;		//[l,r]中互不相同的数的个数void Add(int n) {
    ++cnt[a[n]]; if (cnt[a[n]] == 1) ++res; } //出现了一个不同的数,res++ void Sub(int n) {
    --cnt[a[n]]; if (cnt[a[n]] == 0) --res; } //失去了一个不同的数,res-- int main() {
   	int n, m;	scanf("%d%d", &n, &m);	int size = sqrt(n);	for (int i = 1; i <= n; ++i) {
   		scanf("%d", &a[i]);		pos[i] = i / size;	}	for (int i = 0; i < m; ++i) {
   		scanf("%d%d", &q[i].l, &q[i].r);		q[i].i = i;	}	sort(q, q + m, [](const Q &a, const Q &b) {
   		return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];	});	int l = 1, r = 0;	for (int i = 0; i < m; ++i) {
   		while (q[i].l < l) Add(--l);		while (q[i].r > r) Add(++r);		while (q[i].l > l) Sub(l++);		while (q[i].r < r) Sub(r--);		//第几个询问的答案是区间[l,r]中互不相同的数的个数 		//等于区间大小r-l+1则互不相同,否则存在相同的数  		ans[q[i].i] = (res == r - l + 1) ? true : false; 	}	for (int i = 0; i < m; ++i) 		printf("%s\n", ans[i] ? "Yes" : "No");     return 0;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108219059 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！