敲代码做网站多少钱/百度极速版下载安装

传送门

这个题刚第一眼一看就是使用莫队算法，但是老觉得这应该是个签到题啊，怎么会用莫队这么牛的算法呢？还是个菜菜，觉得签到题用个贪心就碉堡了。

最后还是用莫队给A了，这个题使用莫队顺序得调整好，不然像我这样WA了25发都有可能。

还有这个分块的大小毒的不行，先用的是sqrt(n)，最后找出在1000附近，可能莫队还是学的不精。

附上代码：

#include<bits/stdc++.h>using namespace std;const int N=1e5+50;int n,m,unit,col[N],book[N];
int ans;struct Mo{int l,r,ID;int ans;
};
Mo q[N];inline int cmp(Mo a,Mo b){return a.l/unit!=b.l/unit?a.l/unit<b.l/unit:a.r<b.r;
}inline int CMP(Mo a,Mo b)
{return a.ID<b.ID;
}inline void revise(int x,int add)
{if(add==-1){if(book[col[x]]==1){ans+=add;}book[col[x]]--;}else{if(book[col[x]]==0){ans+=add;}book[col[x]]++;}
}int main()
{while(~scanf("%d%d",&n,&m)){memset(book,0,sizeof(book));ans=0;unit=900;for(int i=1;i<=n;i++){scanf("%d",&col[i]);if(!book[col[i]]){ans++;}book[col[i]]++;}int temp=ans;for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].ID=i;}sort(q+1,q+m+1,cmp);int l=1,r=2;for(int i=1;i<=m;i++){//注意顺序if(q[i].l==q[i].r){q[i].ans=temp;continue;}while(r<q[i].r){revise(r,-1);r++;}while(l<q[i].l){revise(l+1,1);l++;}while(l>q[i].l){revise(l,-1);l--;}while(r>q[i].r){revise(r-1,1);r--;}q[i].ans=ans;}sort(q+1,q+m+1,CMP);for(int i=1;i<=m;i++){printf("%d\n",q[i].ans);}}return 0;
}