CF220B Little Elephant and Array

CF220B Little Elephant and Array
小小莫队
题目描述 小象喜欢和数组玩。现在有一个数组a，含有n个正整数，记第i个数为ai 现在有m个询问，每个询问包含两个正整数lj和rj(1<=lj<=rj<=n)，小象想知道在Alj到Arj之中有多少个数x，其出现次数也为x 输入格式 第一行n和m，n表示数组大小，m表示询问个数，下一行为数组的值，再下m行，每行两个数lj和rj，描述如题面 输出格式 共m行，每行一个数，表示答案
easy or not?
其实很简单
对于add操作，如果原本它是符合的，那么ans–；如果现在符合了，那么ans++
对于del操作，如果原本它是符合的，那么ans–；如果现在符合了，那么ans++
然后就是普通的莫队

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{
    int l,r;
    int Rk;
}s[N];
int n,m;
int col[N];
int happen[N];
int b[N];
int l,r;
int u;
int ans=0;
int anw[N];
bool cmp(node x,node y){
    if(b[x.l]==b[y.l]) return x.r<y.r;
    return x.l<y.l;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(anw,0,sizeof(anw));
        memset(happen,0,sizeof(happen));
        ans=0;
        u=sqrt(n);
        for(int i=1;i<=n;i++) b[i]=(i/u)+1;
        for(int i=1;i<=n;i++){
            scanf("%d",&col[i]);
            if(col[i]>n) col[i]=-1;//如果大于n了就肯定不能成为答案 
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&s[i].l,&s[i].r);
            s[i].Rk=i;
        }
        sort(s+1,s+m+1,cmp);
        for(int i=1;i<=m;i++){
            if(i==1){
                for(int j=s[i].l;j<=s[i].r;j++){
                    happen[col[j]]++;
                    if(happen[col[j]]==col[j]) ans++;
                    if(happen[col[j]]==col[j]+1) ans--;
                }
                l=s[i].l;
                r=s[i].r;
            }
            else{
                while(l<s[i].l){
                    l++;
                    happen[col[l-1]]--;
                    if(happen[col[l-1]]==col[l-1]) ans++;
                    if(happen[col[l-1]]==col[l-1]-1) ans--;
                }
                while(l>s[i].l){
                    l--;
                    happen[col[l]]++;
                    if(happen[col[l]]==col[l]) ans++;
                    if(happen[col[l]]==col[l]+1) ans--;
                }
                while(r<s[i].r){
                    r++;
                    happen[col[r]]++;
                    if(happen[col[r]]==col[r]) ans++;
                    if(happen[col[r]]==col[r]+1) ans--;
                }
                while(r>s[i].r){
                    r--;
                    happen[col[r+1]]--;
                    if(happen[col[r+1]]==col[r+1]) ans++;
                    if(happen[col[r+1]]==col[r+1]-1) ans--;
                }
            }
            anw[s[i].Rk]=ans;
        }
        for(int i=1;i<=m;i++){
            printf("%dn",anw[i]);
        }
    }
    return 0;
} 

最后

以上就是清新发夹为你收集整理的CF220B Little Elephant and Array的全部内容，希望文章能够帮你解决CF220B Little Elephant and Array所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。