http://www.lydsy.com/JudgeOnline/PRoblem.php?id=2038 这个莫队， %%%%%%%%%%%%%； 据说这个是区间神器； 他的思想就是继承上一次询问； 比如上一次我问了1~10 这一次我问1~9 那我们是不是只要把10删掉就好了； 但是如果你问的区间位置每次都相差很大，那样时间复杂度就萎了； 但是假如是离线的话，我们可以先把问题的区间先拍个序 让相邻的两个区间近一点； 然后我们再搞，是不是会很好； 那我们怎么排序呢； 先左端点再右端点？ 这样要被卡 1~100 2~2 2~100 3~3 3~100 …. 这样，是不是被卡成n^2了； 所以我们要分块排； 一个区间[l,r] 我们先排序l/sqrt(n) 再排序r/sqrt(n); 这样的话，n被分成sqrt(n)段； 比如上面的数据，排序后： 2~2 3~3 …… 1~100 2~100 3~100 这样再搞，是跟好了呢？ 当然我没发现 先排序l/sqrt(n) 再排序r/sqrt(n);
先排序l/sqrt(n) 再排序r; 基本一样； 这样一来，时间复杂度大概在n^1.5 但是这个时间刚好卡一卡，不可以在莫队里面搞一个n的循环什么的，不然时间爆；
#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define Ll unsigned long longusing namespace std;struct kkk{ Ll x,y,num,z;}c[50001];Ll a[50001],b[50001];Ll ans[50001][2];Ll n,m,x,y,z,l,r,A;bool cmp(kkk x,kkk y){if(x.z!=y.z)return x.z<y.z;else return x.y<y.y;}Ll gcd(Ll x,Ll y){ if(!y)return x;return gcd(y,x%y);}void outit(Ll len,Ll now){ Ll M=len*(len-1)/2; Ll N=A;//本来我这里放了一个循环，时间炸了；先在改成动态； Ll K=gcd(N,M); ans[now][0]=N/K; ans[now][1]=M/K;}void change(Ll x,Ll y,Ll z){ for(int i=x;i<=y;i++){ A-=b[a[i]]*(b[a[i]]-1)/2; b[a[i]]+=z; A+=b[a[i]]*(b[a[i]]-1)/2; }}void MD(Ll x,Ll y,Ll num){//莫队 if(x>l)change(l,x-1,-1); if(x<l)change(x,l-1,1); if(y>r)change(r+1,y,1); if(y<r)change(y+1,r,-1); l=x;r=y;//不要忘了 outit(y-x+1,c[num].num);}int main(){ scanf("%lld%lld",&n,&m);Ll K=sqrt(n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=m;i++){ scanf("%lld%lld",&x,&y); c[i].x=x; c[i].y=y; c[i].num=i; c[i].z=x/K; } sort(c+1,c+m+1,cmp); l=c[1].x; r=c[1].y;//我们先手动算出第一个区间 for(int i=l;i<=r;i++)b[a[i]]++; for(int i=1;i<=n;i++)if(b[i])A+=b[i]*(b[i]-1)/2; outit(r-l+1,c[1].num); for(int i=2;i<=m;i++)MD(c[i].x,c[i].y,i); for(int i=1;i<=m;i++)printf("%lld/%lld/n",ans[i][0],ans[i][1]);}新闻热点
疑难解答
