暑假完善莫队算法学习！！！！

莫队算法解决的问题

　　1.查询区间[L,R]上不同种类元素的数量，时间复杂度O(n*sqrt(n));

　　2.单点更新+查询

分类

　　1.带修莫队算法

　　2.普通莫队算法

　　3.树形莫队算法

步骤

　　1.记录所有查询(离线操作）

　　2.对于所有查询进行分块，然后在每个unit内排序

　　3.用l，r表示指针，进行对于指针所指的区域进行答案的记录

　　(如果存在单点更新，则为"带修莫队"，引入第三个指针TIM)

　　4.按照查询给出的顺序将答案排序，输出

模板

　　

#include
     
      #define fo(i,a,b) for(int i=a;i<=b;i++)#define ll long long using namespace std;const int N=50003;struct Mo{
   int l,r,ID;ll A,B;}q[N];//A,B分别表示分子和分母ll S(ll x){
   return x*x;}//我们规定sum函数得到的是ll GCD(ll a,ll b){
   while(b^=a^=b^=a%=b);return a;}int n,m,col[N],unit,Be[N];ll sum[N],ans;bool cmp(Mo a,Mo b){
   return Be[a.l]==Be[b.l]?a.r
      
       
        q[i].l)revise(l-1,1),l--;//        while(r
        
         q[i].r)revise(r,-1),r--;//         if(q[i].l==q[i].r){q[i].A=0;q[i].B=1;continue;}//该区间内只有一只袜子，则出现一双的概率为0        q[i].A = ans - (q[i].r - q[i].l + 1);          //(组合数的那个公式，可以推出来，就是这个，x1*x1+x2*x2+x3*x3-(x1+x2+x3);x1+x2+x3就是区间的长度        q[i].B=1LL*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);//组合数(已经同时约掉了2)        ll gcd=GCD(q[i].A,q[i].B);q[i].A/=gcd;q[i].B/=gcd;//分数化简    }    sort(q+1,q+m+1,CMP);//按照原来的id进行排序    fo(i,1,m)printf("%lld/%lld\n",q[i].A,q[i].B);    return 0;}/*6 41 2 3 3 3 22 61 33 51 6*/
        
       
      
     

 

 

 

题目

　　1. （带修莫队）

　　2. （莫队算法）

 

补完LCA了

发现还是不会树上莫队

carry on！！