记录编号	599546	评测结果	AAAAATTTTTTTTTTTTTTT
题目名称	[USACO21Feb Platinum]No Time to Dry	最终得分	25
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	30.674 s
提交时间	2025-03-21 19:15:31	内存使用	14.19 MiB

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 10;

int n, q;
int a[MAXN];
int st[MAXN][18];
int len[MAXN];
int lastappear[MAXN];

int main() {
	freopen("dry.in", "r", stdin);
	freopen("dry.out", "w", stdout);
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; ++i) {
		len[i] = log2(i);
		scanf("%d", &a[i]);
		st[i][0] = a[i];
	}
	
	for (int i = 1; i <= 17; ++i) {
		for (int j = 1; j + (1 << (i - 1)) <= n; ++j) {
			st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
		}
	}
	
//	for (int i = 1; i <= n; ++i) {
//		printf("%d%c", len[i], " \n"[i == n]);
//	}
//	for (int i = 0; i <= 3; ++i) {
//		for (int j = 1; j <= n; ++j) {
//			printf("%d%c", st[j][i], " \n"[j == n]);
//		}
//	}
	
	while (q--) {
		memset(lastappear, 0, sizeof lastappear);
		int l, r, ans = 0;
		scanf("%d %d", &l, &r);
		for (int i = l; i <= r; ++i) {
//			printf("Dealing a[%d]=%d, ", i, a[i]);
			int p = lastappear[a[i]];
			if (p) {
				int k = len[i - p + 1];
//				printf("k=%d cmp(st[%d][%d],st[%d][%d]) ", k, p, k, i - (1 << k) + 1, k);
				if (min(st[p][k], st[i - (1 << k) + 1][k]) < a[i]) {
					ans++;
//					printf("ans++ ");
				}
			} else {
				ans++;
//				printf("ans++");
			}
			lastappear[a[i]] = i;
//			printf("\n");
		}
		printf("%d\n", ans);
	}
	return 0;
}