Problem - 220B - Codeforces
题目大意：给定长度为n的数组，m次查询,求每次查询的区间中, a i a_i ai= n u m [ a i ] num[a_i] num[ai]的个数.
解题思路:n的范围是1e5.基本确定这是莫队的问题. 莫队通过将长度作为离线问题来处理离线问题 n n n数组分块成 n \sqrt{n} n 块进行处理，处理前进行排序，对于起点，用块决定顺序，对于相同块，用n决定顺序. 复杂性的证明：对于右指针的每一块，它必须单调地移动，所以复杂性是 O ( n ) O(n) O(n),总共有 n \sqrt{n} n 块,所以右指针的复杂度为 O ( n n ) O(n\sqrt{n}) O(nn ),对于左指针,在同一块内的移动次数最多是 n \sqrt{n} n ,而总共有m次询问,那么左指针的复杂度就是 O ( m n ) O(m\sqrt{n}) O(mn ).合起来的复杂度就是近似于 O ( n n ) O(n\sqrt{n}) O(nn ).
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 1e5+5;
int BLOCK, n, m, answer;
int a[N], cnt[N];
struct node{
int l, r, id, ans;
}b[N];
bool cmp1(const node&a, const node&b){
if (a.l/BLOCK==b.l/BLOCK){
return a.r < b.r;
}
return a.l/BLOCK < b.l/BLOCK;
}
bool cmp2(const node&a, const node&b){
return a.id < b.id;
}
void add(int position){
if (a[position]>n)return;
cnt[a[position]]++;
if (cnt[a[position]]==a[position]){
answer++;
}else if (cnt[a[position]]==a[position]+1){
answer--;
}
}
void remove(int position){
if (a[position]>n)return;
cnt[a[position]]--;
if (cnt[a[position]]==a[position])answer++;
else if (cnt[a[position]]==a[position]-1)answer--;
}
int main(){
syncfalse
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
cin>>n>>m;
BLOCK=sqrt(n);
for (int i = 1; i <= n; ++i)cin>>a[i];
for (int i = 1; i <= m; ++i){
cin>>b[i].l>>b[i].r;b[i].id=i;}
sort(b+1, b+1+m, cmp1);
int nl=0, nr=1;
for (int i = 1; i <= m; ++i){
int l = b[i].l, r = b[i].r;
while(nl+1<l){
remove(nl+1);
nl++;
}
while(nl>=l){
add(nl);
nl--;
}
while(nr<=r){
add(nr);
nr++;
}
while(nr>r+1){
remove(nr-1);
nr--;
}
b[i].ans=answer;
}
sort(b+1,b+1+m, cmp2);
for (int i = 1; i <= m; ++i){
cout << b[i].ans << "\n";
}
return 0;
}