学佳澳杯 F 区间计数

双指针、尺取

题目

样例及输出

4 2
1 3 2 4
3 2
2 4

5

思路

from 神秘的学长

双指针, 尺取

枚举每一个i可以到达的最远的j, 使得<i, j>内, 每一个人的敌人数量为0, 我们用 emy[] 记录

1、一段区间是合法的, 当且仅当区间内所有的人的所有敌人, 在此区间内出现次数为0 即 我们只要保证每次右端点加入的点, 自身的敌人不在区间内, 我们用emy记录i敌人的个数 while (j <= n && !emy[a[j]]) j ++ ;

2、每加入一个点a[j], 我们都要更新一下它的敌人A, 标记e[A] ++ , 表示A的敌人至少存在一个 for (auto it : h[a[j]]) emy[it] ++ ;

3、在移动先统计一下 ans, 因为j退出的时候是非法状态, 故合法长度为 [i, j-1], 即 ans += (j-1-i+1)

4、i每次都前进一步, 所以我们要用a[i]更新它的敌人, 使得数量减一

注意 1e6 不用考虑离散化, 这里时限卡掉 unordered_map

因为指针i、j一直往后移动, 所以时间复杂度为 O(n)

人畜无害的代码

#include <iostream>
#include <unordered_map>
#include <vector>
#define int long long

using namespace std;

const int N = 1e6 + 12;

int n, m;
int a[N];
int emy[N]; // emy[i] 动态维护区间内i的敌人数量 
vector<int> h[N];

signed main()
{
	cin.tie(0) -> sync_with_stdio(0);
	
	cin >> n >> m;
	for (int i=1;i <= n;i ++ ) cin >> a[i], emy[a[i]] = 0;
	for (int i=1;i <= m;i ++ )
	{
		int u, v; cin >> u >> v;
		h[u].push_back(v);
		h[v].push_back(u);	
	}
	
	int ans = 0;	
	for (int i=1, j=1;i <= n;i ++ )
	{
		while (j <= n && !emy[a[j]])
		{
			for (auto it:h[a[j]]) emy[it] ++ ;
			j ++ ;	
		}
		
		ans += j - i;
		
		for (auto it:h[a[i]]) emy[it] -- ;
	}
	
	cout << ans;
	
	return 0;
}