# #include<codesonic>

using namespace 绿一色;

### 莫队算法初探

posted on 2018-08-15 19:31:30 | under 学习笔记 |

### 普通莫队

inline void add(int x){
cnt[x]++;
if(cnt[x]==1)ans++;
}

inline void del(int x){
cnt[x]--;
if(cnt[x]==0)ans--;
}

//在获取答案时：
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);

（如何证明我也不清楚）

bool cmp(query a,query b){
return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

bool cmp(node a,node b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
}

#include <bits/stdc++.h>

using namespace std;

{
char x;
while((x = getchar()) > '9' || x < '0') ;
int u = x - '0';
while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
return u;
}
int buf[105];
inline void write(int i) {
int p = 0;
if(i == 0) p++;
else while(i) {
buf[p++] = i % 10;
i /= 10;
}
for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);
}

#define il inline
#define re register

int block,ans=0,cnt[1000001];
int n,m,a[500010],Ans[500010];

struct node {
int l,r,id;
}q[500010];

il bool cmp(node a,node b){
return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

if(!cnt[a[x]])ans++;
cnt[a[x]]++;
}

il void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]])ans--;
}
int i;

int main(){
block=n/sqrt(m*2/3);
for(i=1;i<=m;++i){
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=0,r=0;
for(i=1;i<=m;++i){
int ql=q[i].l,qr=q[i].r;
while(l<ql)del(l++);
while(r>qr)del(r--);
Ans[q[i].id]=ans;
}
for(i=1;i<=m;++i)write(Ans[i]),printf("\n");
return 0;
}

ans+=2*cnt[x]+1

ans-=2*cnt[x]-1

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=50005;
long long int c[maxn];
long long int sum[maxn];

struct node{
long long int l,r,num;
}q[maxn];

long long anss[maxn];

long long int block;
long long int ans=0;

bool cmp(node a,node b){
return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

inline void del(int x){
sum[c[x]]--;
ans-=2*sum[c[x]]+1;
}

sum[c[x]]++;
ans+=2*sum[c[x]]-1;
}

int main()
{
long long int n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
block=sqrt(n);
for(long long int i=1;i<=n;i++){
scanf("%lld",&c[i]);
}
for(long long int i=1;i<=m;i++){
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].num=i;
}
sort(q+1,q+1+m,cmp);
int l=1,r=0;
for(long long int i=1;i<=m;i++){
long long int ql=q[i].l,qr=q[i].r;
while(l<ql){
del(l);
l++;
}
while(l>ql){
l--;
}
while(r<qr){
r++;
}
while(r>qr){
del(r);
r--;
}
anss[q[i].num]=ans;
}
for(long long int i=1;i<=m;i++){
printf("%lld\n",anss[i]);
}
return 0;
}

### 带修改莫队

• $[l-1,r,time]$
• $[l+1,r,time]$
• $[l,r-1,time]$
• $[l,r+1,time]$
• $[l,r,time-1]$
• $[l,r,time+1]$

• 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是$O(n)$

• 若左右端点所在块改变，时间一次最多会移动n个格子，时间复杂度$O(n)$

• 左端点所在块一共有$n^{\frac{1}{3}}$中，右端点也是$n^{\frac{1}{3}}$种，一共${n^{\frac{1}{3}}}\times{n^{\frac{1}{3}}}=n^{\frac{2}{3}}$种，每种乘上移动的复杂度$O(n)$，总复杂度$O(n^{\frac{5}{3}})$

### 树上莫队

dfs一棵树，然后如果dfs到x点，就push_back(x),dfs完x点，就直接push_back(-x)，然后我们在挪动指针的时候

• 新加入的值是-x ---> del(x)
• 新删除的值是x ---> del(x)

$\sum_{c}val_c\sum_{i=1}^{cnt_c}w_i$

val表示该颜色的价值

cnt表示颜色出现的次数

w表示该颜色出现i次后的价值

code：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>

#define DEBUG printf("line:%d func:%s\n",__LINE__,__FUNCTION__);

using namespace std;

const int maxn=200010;

int block,index,n,m,q;
int pos[maxn],col[maxn],app[maxn];
bool vis[maxn];
long long ans[maxn],cur;

struct edge {
int to,nxt;
} e[maxn];
int cnt1=0,cnt2=0;//时间戳

struct query {
int l,r,t,id;
bool operator <(const query &b)const {
return (pos[l]<pos[b.l])||(pos[l]==pos[b.l]&&pos[r]<pos[b.r])||(pos[l]==pos[b.l]&&pos[r]==pos[b.r]&&t<b.t);
}
} a[maxn],b[maxn];

inline void addedge(int x, int y) {
e[++cnt]=(edge) {
};
}

void dfs(int x) {
id[f[x]=++index]=x;
if(e[i].to!=fa[x][0]) {
fa[e[i].to][0]=x;
dep[e[i].to]=dep[x]+1;
dfs(e[i].to);
}
}
id[g[x]=++index]=x;//括号序
}

inline void swap(int &x,int &y) {
int t;
t=x;
x=y;
y=t;
}

inline int lca(int x,int y) {
if(dep[x]<dep[y])
swap(x,y);
if(dep[x]!=dep[y]) {
int dis=dep[x]-dep[y];
for(int i=20; i>=0; i--)
if(dis>=(1<<i))
dis-=1<<i,x=fa[x][i];
}//爬到同一高度
if(x==y) return x;
for(int i=20; i>=0; i--) {
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}

if(vis[x])
cur-=(long long )v[col[x]]*w[app[col[x]]--];
else
cur+=(long long )v[col[x]]*w[++app[col[x]]];
vis[x]^=1;
}

inline void modify(int x,int t) {
if(vis[x]) {
col[x]=t;
} else col[x]=t;
}//在时间维上移动

int main() {
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=m; i++)
scanf("%d",&v[i]);
for(int i=1; i<=n; i++)
scanf("%d",&w[i]);
for(int i=1; i<n; i++) {
int x,y;
scanf("%d%d",&x,&y);
}
for(int i=1; i<=n; i++) {
scanf("%d",&last[i]);
col[i]=last[i];
}
dfs(1);
for(int j=1; j<=20; j++)
for(int i=1; i<=n; i++)
fa[i][j]=fa[fa[i][j-1]][j-1];//预处理祖先
int block=pow(index,2.0/3);
for(int i=1; i<=index; i++) {
pos[i]=(i-1)/block;
}
while(q--) {
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt==0) {
b[++cnt2].l=x;
b[cnt2].r=last[x];
last[x]=b[cnt2].t=y;
} else {
if(f[x]>f[y])
swap(x,y);
a[++cnt1]=(query) {
lca(x,y)==x?f[x]:g[x],f[y],cnt2,cnt1
};
}
}
sort(a+1,a+cnt1+1);
int L,R,T;//指针坐标
L=R=0;
T=1;
for(int i=1; i<=cnt1; i++) {
while(T<=a[i].t) {
modify(b[T].l,b[T].t);
T++;
}
while(T>a[i].t) {
modify(b[T].l,b[T].r);
T--;
}
while(L>a[i].l) {
L--;
}
while(L<a[i].l) {
L++;
}
while(R>a[i].r) {
R--;
}
while(R<a[i].r) {
R++;
}
int x=id[L],y=id[R];
int llca=lca(x,y);
if(x!=llca&&y!=llca) {
}