jzoj 4804 - [NOIP 2016 향상 A 팀 시 뮬 레이 션 9.28] 성적 조사 연구 [지침, 시 뮬 레이 션]

본론
제목 의 대의
한 서열 에 몇 개의 구간 이 k k k 를 만족 시 키 는 지 구 하 는 개 수 는 l r ∼ r k lr\sim r_k lr ∼ rk 사이
문제 풀이 의 사고 방향.
우선, 고정된 오른쪽 단점 r r r r 에 일치 하 는 왼쪽 지침 은 반드시 하나의 구간 [L 2.. L 1 - 1] [L 2. L 1 - 1] [L2.. L1 - 1] 임 이 분명 하 다.
즉, [L 2.. L 1 - 1] [L 2. L 1 - 1] [L2.. L1 - 1] 왼쪽 끝 점 으로 r r r 를 오른쪽 끝 점 으로 매 칭 하 는 것 은 아무 거나 가능 하 다.
그러면 우 리 는 지금 오른쪽 점 r r r 를 매 거 진 후에 이 범 위 를 구 할 수 있다.
그리고 분명히 이 범 위 는 단조 로 움 을 만족 시 키 는 것 이다. 즉, 오른쪽 점 에서 오른쪽으로 이동 한 후에 L 1, L 2 L 이다.1,L_2 L1, 2 는 작 아 지지 않 는 다.
그럼 지금부터 L 1 과 L 2 L 을 생각해 보도 록 하 겠 습 니 다.1 과 L2L1 과 L2 의 성질.
L 2 L 에 대해2 L2 는 [L 2.. r] ∼ r [L 2. r] \ \ sim r [L2. r] ∼ r 이 구간 에서 각 k k k 의 개 수 는 ≤ r k \ \ leq rk ≤ rk, 오른쪽 포인터 오른쪽 이동 숫자의 개 수 는 줄 어 들 수 밖 에 없 기 때 문 입 니 다.그래서 우 리 는 매번 오른쪽으로 이동 한 후에 하나의 수 를 넣 고 L 2 L 을2. L2 를 오른쪽으로 옮 겨 서 조건 을 만족 시 키 면 됩 니 다.
L 1 L 에 대해1 L1 은 L 1 ∼ r L1 \ sim r L1 ∼ r 이 구간 에는 최소 k k k 개수 < l i < li < li, 증명 방법 이 동일 합 니 다.그러면 우 리 는 변 수 를 설정 할 수 있 습 니 다.1 \ sim r L1 ∼ r 이 구간 에 몇 개의 k k k k 가 있 는 지 의 개 수 는 < l i < li < li 의, 오른쪽으로 이동 할 때마다 k k k 를 감소 시 킬 수 있 습 니 다. k k k 가 0 이면 L 1 L1. L1 오른쪽 에서 조건 을 만족 시 키 는 위치 로 옮 기 면 됩 니 다.
그리고 매번 L 1 - L 2 L 이 쌓 여요.1-L_2 L1 − L2 의 답
시간 복잡 도 O (n) O (n) O (n)
c o d e code code

#include
#include
#define ll long long
using namespace std;
const ll N=200100;
ll n,k,w[N],l[N],r[N],v1[N],v2[N],l1,l2,ans;
int main()
{
	freopen("survey.in","r",stdin);
	freopen("survey.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=n;i++)
		scanf("%lld",&w[i]);
	for(ll i=1,zk=k;i<=zk;i++){
		scanf("%lld%lld",&l[i],&r[i]);
		if(l[i]==0) k--;
	}
	l1=l2=1;
	for(ll i=1;i<=n;i++){
		v1[w[i]]++;v2[w[i]]++;
		if(v2[w[i]]==l[w[i]]) k--;
		while(v1[w[i]]>r[w[i]])
		  v1[w[l2++]]--;
		while(!k&&l1<=i){
			v2[w[l1]]--;
			if(v2[w[l1]]==l[w[l1]]-1)
			  k++;
			l1++;
		}
		ans+=max(l1-l2,0ll);
		if(ans)
		  ans++,ans--;
	}
	printf("%lld",ans);
}