제출 #1211628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211628		Dan4Life	Poklon (COCI17_poklon)	C++20	140 / 140	266 ms	28776 KiB

poklon

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int mxN = (int)5e5+2;

int n, q, tot;
int p[mxN], ans[mxN], fen[mxN];
vector<array<int,2>> Q[mxN];
unordered_map<int,int> M;

void upd(int x, int v){ for(++x; x<mxN; x+=x&-x) fen[x]+=v; }
int sum(int x){ int s = 0; for(++x; x>0; x-=x&-x) s+=fen[x]; return s; }

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q; int l, r;
	for(int i = 1; i <= n; i++)
		cin >> r, p[i] = M[r], M[r]=i;
	for(int i = 0; i < q; i++)
		cin >> l >> r, Q[r].pb({l,i});
	for(int r = 1; r <= n; r++){
		upd(p[r],1), upd(p[p[r]],-2), upd(p[p[p[r]]],1);
		for(auto [l,i] : Q[r]) ans[i] = sum(r)-sum(l-1);
	}
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

• Subtask 1: 140 / 140