I started coding square root decomposition myself and submitted my code for Little Elephant And Array(http://mirror.codeforces.com/contest/220/problem/B); however, I am getting compilation error. Is there some error in my code? How can I make it more optimal?
struct x{
int ct[size1]; int mini, maxi;
};
x block[size1];
void cons(int n, int a[]){
int p=floor(sqrt(n));
for(int i=0;i<n;i++){block[i/p+1].ct[a[i]]++; block[i/p+1].mini=min(block[i/p+1].mini,a[i]); block[i/p+1].maxi=max(block[i/p+1].maxi,a[i]);}
}
void query(int l,int r,int n, int a[], int &ans){
int p=floor(sqrt(n));
int b1=(l-1)/p+1;
int b2=(r-1)/p+1;
//int ans=0;
if(b1==b2){
map<int,int> v;
for(int i=(l-1);i<=(r-1);i++)v[a[i]]++;
map<int,int>::iterator it=v.begin();
for(;it!=v.end();it++)if(it->second==it->first)ans++;
}
else if(b1!=b2){
map<int,int> v;
for(int i=l;i<b1*p;i++)v[a[i]]++;
for(int i=b1;i<b2;i++)for(int j=block[i].mini;j<=block[j].maxi;j++)v[j]+=block[i].ct[j];
for(int i=b2*p;i<=r;i++)v[a[i]]++;
map<int,int>::iterator it=v.begin();
for(;it!=v.end();it++)if(it->second==it->first)ans++;
}
}
int main(){
int n,m; cin>>n>>m;
int a[n]; for(int i=0;i<n;i++)cin>>a[i];
cons(n,a);
while(m--){
int x,b; cin>>x>>b;
int ans=0;
query(x,b,n,a,ans); cout<<ans<<endl;
}
return 0;
}
Any help is appreciated. Thank you