基础
暴力！！
啥叫莫队
莫队是前国家队队长莫涛想出的算法。用于处理一些可离线的区间问题。可以将本来是(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
",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
*/
树上莫队
留坑待填....