本文共 1687 字，大约阅读时间需要 5 分钟。
由于今天在模拟赛上遇到一道树上莫队，我爆零了，所以我特地来学习了莫队算法
我觉得莫队算法就是那四个循环，update实现O(1)转移来保证复杂度
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)14 #define re(i,l,r) for(int i=(l);i<=(r);i++)15 #define Clear(a,b) memset(a,b,sizeof(a))16 #define inout(x) printf("%d",(x))17 #define douin(x) scanf("%lf",&x)18 #define strin(x) scanf("%s",(x))19 #define LLin(x) scanf("%lld",&x)20 #define op operator21 #define CSC main22 typedef unsigned long long ULL;23 typedef const int cint;24 typedef long long LL;25 using namespace std;26 void inin(int &ret)27 {28 ret=0;int f=0;char ch=getchar();29 while(ch<'0'||ch>'9'){ if(ch=='-')f=1;ch=getchar();}30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();31 ret=f?-ret:ret;32 }33 int n,m,c[50050],wei[50050];34 struct question35 {36 int l,r,id;37 LL a,b;38 void in(int i){inin(l),inin(r),id=i;}39 bool op < (const question &rhs)const { return wei[l]==wei[rhs.l]?r q[i].r)update(r--,-1);65 while(l q[i].l)update(--l,1);67 if(q[i].l==q[i].r){q[i].a=0,q[i].b=1;continue;}68 q[i].a=ans-(q[i].r-q[i].l+1);69 q[i].b=(LL)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);70 LL k=gcd(q[i].a,q[i].b);71 q[i].a/=k,q[i].b/=k;72 }73 }74 int CSC()75 {76 inin(n),inin(m);77 re(i,1,n)inin(c[i]);78 int block=sqrt(n);79 re(i,1,n)wei[i]=(i-1)/block+1;80 re(i,1,m)q[i].in(i);81 sort(q+1,q+m+1);82 solve();83 sort(q+1,q+m+1,com);84 re(i,1,m)printf("%lld/%lld\n",q[i].a,q[i].b);85 return 0;86 }
转载于:https://www.cnblogs.com/HugeGun/p/5207605.html