[莫队][学习笔记]

基础

暴力！！

啥叫莫队

莫队是前国家队队长莫涛想出的算法。用于处理一些可离线的区间问题。可以将本来是\(n^2\)的复杂度优化成n*根号级别。是基于分块的。

普通莫队

这类莫队用来处理一类可离线，无修改的区间问题，也是最基础的莫队。

先来看这样一道题:

给出一个长度为n的序列，然后有m次询问，每次询问从l到r这个区间内不同的数字的个数。\(1 \leq n ,m \leq 10^5\)

先考虑普通的暴力怎么打，那就是每次询问都扫一遍呗。

然后考虑有一些点，在很多次询问的时候都被扫到过。是不是可以把这里给优化一下。

是的。莫队的做法是给每个位置的点分块。然后把询问离线下来，排个序。排序的标准是这样的

bool cmp(node x,node y) {
    if(belong[x.l] != belong[y.l]) return x.l < y.l;
    else return x.r < y.r;
}

belong[i]表示i这个位置的点属于哪个块。也就是说，如果两次查询的左端点不在同一个块里，那就按照左端点排序，否则按照右端点排序。这样就可以达到每次询问根号的复杂度了。

然后需要两个指针l,r来表示当前统计的区间。然后每次不断的往想要的区间跳。

一道板子题

带修莫队

带修莫队其实就是在莫队的基础上加了个时间戳，排序的时候作为第三关键字，按从小到大排序。然后记录下每次修改修改前的样子和修改后的样子。给每次询问记录下一个时间戳，也就是之前有几次询问。排完序之后，每次都把当前的时间暴力修改成查询时的时间(没错，就是这么暴力)，然后按照普通莫队的查询方式查询就行了。

带修莫队当分的块的大小为\(n^{\frac{2}{3}}\)时，复杂度最优秀，为\(n^{\frac{5}{3}}\)

一道模板题

代码

/*
* @author: wxyww
* @date:   2018-12-17 14:32:03
* @last modified time: 2018-12-17 20:07:07
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<bitset>
using namespace std;
typedef long long ll;
const int n = 60010;
ll read() {
   ll x=0,f=1;char c=getchar();
   while(c<'0'||c>'9') {
      if(c=='-') f=-1;
      c=getchar();
   }
   while(c>='0'&&c<='9') {
      x=x*10+c-'0';
      c=getchar();
   }
   return x*f;
}
struct node {
   int pre,nex,x;//pre表示修改前的颜色，nex表示修改后的颜色，x表示修改的位置
}c[n];
struct node {
   int tim,l,r,id;//l,r表示询问的区间，tim表示询问前进行过多少次修改。
}q[n];
int col[n],cl[n];
int belong[n];
bool cmp(node x,node y) {
   if(belong[x.l] != belong[y.l]) return x.l < y.l;
   if(belong[x.r] != belong[y.r]) return x.r < y.r;
   return x.tim < y.tim;
}
int ch[n * 100],now,ans,l,r;
void lst() {//时光倒流
   col[c[now].x] = c[now].pre;
   if(c[now].x <= r && c[now].x >= l) {
      ch[c[now].nex]--;
      if(ch[c[now].nex] == 0) ans--;
      ch[c[now].pre]++;
      if(ch[c[now].pre] == 1) ans++;
   }
   now--;
}
void net() {
   now++;
   col[c[now].x] = c[now].nex;
   if(c[now].x <= r && c[now].x >= l) {
      ch[c[now].pre]--;
      if(ch[c[now].pre] == 0) ans--;
      ch[c[now].nex]++;
      if(ch[c[now].nex] == 1) ans++;
   }
}
void update(int color,int c) {
   ch[color] += c;
   if(c > 0 && ch[color] == 1) ans++;
   if(c < 0 && ch[color] == 0) ans--;
}
int anss[n];
int main() {
   int n = read(),m = read();
   int unit = pow(n,0.666666);
   for(int i = 1;i <= n;++i) cl[i] = col[i] = read(),belong[i] = (i-1) / unit + 1;
   char c;
   int time = 0,qjs = 0;
   for(int i = 1;i <= m;++i) {
      c = getchar();
      while(c != 'q' && c != 'r') c = getchar();
      if(c == 'q') {
         q[++qjs].tim = time;
         q[qjs].l = read();
         q[qjs].r = read();
         q[qjs].id = qjs;
      }
      else {
         ++time;
         int x = read(),col = read();
         c[time].pre = cl[x];
         c[time].nex = col;
         c[time].x = x;
         cl[x] = col;
      }
   }
   sort(q + 1,q + qjs + 1,cmp);
   for(int i = 1;i <= qjs;++i) {
      while(now < q[i].tim) net();
      while(now > q[i].tim) lst();
      while(l > q[i].l) update(col[--l],1);
      while(r < q[i].r) update(col[++r],1);
      while(l < q[i].l) update(col[l++],-1);
      while(r > q[i].r) update(col[r--],-1);
      anss[q[i].id] = ans;
   }
   for(int i = 1;i <= qjs;++i) printf("%d\n",anss[i]);
   return 0;
}
/*
6 5
1 2 3 4 5 5
q 1 4
q 2 6
r 1 2
q 1 4
q 2 6
*/

树上莫队

留坑待填....