带有？的莫队

带有？的莫队

写莫队如同吸毒，易上头（误

莫队是一种用来统计（注意不是维护）区间各种东西的数据结构，由于其短小精悍，拓展性强而让人欲罢不能

常用的莫队有四种，其中树上莫队有个前置芝士要点，这里只会简单提一下

列表

1. 普通莫队
2. 带修莫队
3. 回滚莫队
4. 树上莫队

一个一个来讲

普通莫队

本质思想是继承前面的状态

A：举个栗子？

Q：假设我们已经处理好了区间[l , r]，
特殊化的，对于下一个区间[l , r’]，我们只需要统计[r + 1 , r’]即可
推广到一般，对于下一个区间[l’ , r’]，我们处理[l , l’]以及[r , r’]即可

具体实现维护两个指针l , r即可

莫队的基操就是这个，不过我们改一下询问的处理顺序。
具体的，我们将左端点按块进行排序，同块按右端点排序，这样就能时间复杂度从O(n ²) 降到 O(n^3/2).

例题以后再补

带修莫队

看起来很高大山，但说白了就是加多一个时间维，把两个指针(l , r)变成(l , r , t)，且优先维护t

结合例题：P1903 [国家集训队]数颜色

我们将修改和查询分成两个数组，跑莫队时优先处理时间维t，然后再处理l和r

具体实现有个小trick，详见树上带修莫队的例题

回滚莫队

在脑子里想象下沙滩，那个潮是不是上来之后又会回去？

把这一块的l想象成潮就好了

具体的只继承r的答案，l贡献的答案扔掉

变相省掉了一个删除的操作

结合例题：AT1219 歴史の研究

这里贴一下代码

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 200010;
typedef long long ll;
struct query
{int l , r;int id;
} b[N];
int n , m , len;
int bnum , bl[N] , br[N] , bel[N] , LEN;
ll ans[N] , a[N] , num[N];
ll cnt[N] , cnt2[N] , typ[N];
int find(ll x)
{int l = 1 , r = len , mid , best = len;while(l <= r){mid = (l + r) >> 1;if(num[mid] >= x) best = mid , r = mid - 1;else l = mid + 1; } return best;
}
bool cmp(query a , query b)
{return (bel[a.l] ^ bel[b.l]) ? bel[a.l] < bel[b.l] : a.r < b.r;
}
int main()
{scanf("%d%d" , &n , &m);LEN = sqrt(n) , bnum = ceil((double)n / LEN);for(int i = 1 ; i <= bnum ; i++){bl[i] = (i - 1) * LEN + 1;br[i] = i * LEN;for(int j = bl[i] ; j <= br[i] ; j++) bel[j] = i;}for(int i = 1 ; i <= n ; i++) scanf("%lld" , &a[i]) , num[i] = a[i];sort(num + 1 , num + n + 1) ; len = unique(num + 1 , num + n + 1) - num - 1;for(int i = 1 ; i <= n ; i++) typ[i] = find(a[i]);for(int i = 1 ; i <= m ; i++) scanf("%d%d" , &b[i].l , &b[i].r) , b[i].id = i;sort(b + 1 , b + m + 1 , cmp);int i = 1;for(int k = 0 ; k <= bnum ; k++){int l = br[k] + 1 , r = br[k];ll now = 0;memset(cnt , 0 , sizeof cnt);for(; bel[b[i].l] == k ; i++){int ql = b[i].l , qr = b[i].r;ll tmp;if(bel[ql] == bel[qr]){	tmp = 0;for(int j = ql ; j <= qr ; j++) cnt2[typ[j]] = 0;for(int j = ql ; j <= qr ; j++){++cnt2[typ[j]] ; tmp = max(tmp , 1ll * cnt2[typ[j]] * a[j]);}ans[b[i].id] = tmp;continue;}while(r < qr){++r ; cnt[typ[r]]++; now = max(now , 1ll * cnt[typ[r]] * a[r]);}tmp = now;while(l > ql){l-- ; cnt[typ[l]]++; now = max(now , 1ll * cnt[typ[l]] * a[l]);}ans[b[i].id] = now;while(l < br[k] + 1){--cnt[typ[l]] ; l++;} now = tmp;}}for(int i = 1 ; i <= m ; i++) printf("%lldn" , ans[i]);return 0;
}

树上莫队

所有的莫队都是基于一维序列的

因此单纯树上的不好搞

既然树上不好搞，那我们就把它搞成序列

我们用一个叫欧拉序(前面提到的前置芝士)的东西来把这棵树拍扁

具体实现就是跑dfs序的时候，每个节点搜到跟退出的时候都记录到序列里

容易发现每个节点出现两次，而且每个相同节点中间的点就是以这个点为根的子树

代码的实现以及细节详见这篇博客

SP10707 COT2 - Count on a tree II

code:（记得处理lca）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Orz c = getchar()
#define sto c < '0' || c > '9'
#define StmAKioi c >= '0' && c <= '9'
#define yzhyyds return ret
using namespace std;
const int N = 200010 , M = 300010 , K = 20;
int h[N] , to[M] , nxt[M] , tot = 1;
int a[N] , n , m , bel[N] , LEN , gg[N];
int fir[N] , las[N] , idx;
int dep[N] , dp[N][K] , dfn[N];
int col[N] , cnt , vis[N];
int num[N] , len , ans[N];
struct query
{int l , r;int Lca , id;
} b[M];void dfs(int x , int lst)
{for(int k = 1 ; k < K ; k++)dp[x][k] = dp[dp[x][k - 1]][k - 1];fir[x] = ++idx; dfn[idx] = x;for(int i = h[x] , v ; v = to[i] , i ; i = nxt[i]){if(v == lst) continue;dep[v] = dep[x] + 1;dp[v][0] = x;dfs(v , x);}las[x] = ++idx; dfn[idx] = x;
}
//inline int read()
//{
//	char Orz; int ret = 0;
//	while(sto) Orz;
//	while(StmAKioi)
//	{
//		ret = ret * 10 + c - '0';
//		Orz;
//	}
//	yzhyyds;
//}
inline int read()
{char c = getchar() ; int ret = 0;while(c < '0' || c > '9') c = getchar();while(c >= '0' && c <= '9'){ret = ret * 10 + c - '0';c = getchar();}return ret;
}
inline void add(int a , int b)
{to[++tot] = b ; nxt[tot] = h[a] ; h[a] = tot;
}
inline int lca(int x , int y)
{if(dep[x] < dep[y]) swap(x , y);for(int k = K - 1 ; k >= 0 ; k--)if(dep[dp[x][k]] >= dep[y]) x = dp[x][k];if(x == y) return x;for(int k = K - 1 ; k >= 0 ; k--){if(dp[x][k] == dp[y][k]) continue;x = dp[x][k] , y = dp[y][k];}return dp[x][0];
}
inline int find(int x)
{int l = 1 , r = len , mid , best;while(l <= r){mid = (l + r) >> 1;if(num[mid] >= x) best = mid , r = mid - 1;else l = mid + 1; }return best;
}
inline bool cmp(query a , query b)
{return bel[a.l] ^ bel[b.l] ? bel[a.l] < bel[b.l] : ((bel[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
inline void Add(int x)
{if(!col[a[x]]) cnt++;col[a[x]]++;
}
inline void Del(int x)
{if(col[a[x]] == 1) cnt--;col[a[x]]--;
}
inline void work(int x)
{vis[dfn[x]] ^= 1;if(vis[dfn[x]]) Add(x);else Del(x);
}
int main()
{n = read() ; m = read() ; LEN = sqrt(2 * n);for(int i = 1 ; i <= n ; i++) gg[i] = read() , num[i] = gg[i];sort(num + 1 , num + n + 1); len = unique(num + 1 , num + n + 1) - num - 1;for(int i = 1 ; i <= n ; i++) gg[i] = find(gg[i]);for(int i = 1 ; i <= 2 * n ; i++) bel[i] = (i - 1) / LEN;for(int i = 1 , a , b ; i < n ; i++){a = read() ; b = read();add(a , b) , add(b , a);}dep[1] = 1;dfs(1 , 1);for(int i = 1 ; i <= n ; i++) a[fir[i]] = a[las[i]] = gg[i];for(int i = 1 ; i <= m ; i++){b[i].l = read() ; b[i].r = read() ; if(fir[b[i].l] > fir[b[i].r]) swap(b[i].l , b[i].r);b[i].Lca = lca(b[i].l , b[i].r); b[i].id = i;if(b[i].Lca == b[i].l) b[i].l = fir[b[i].l] , b[i].r = fir[b[i].r];else b[i].l = las[b[i].l] , b[i].r = fir[b[i].r];}sort(b + 1 , b + m + 1 , cmp);int l = 1 , r = 0;for(int i = 1 ; i <= m ; i++){int ql = b[i].l , qr = b[i].r , LCA = b[i].Lca;if(dfn[ql] == dfn[qr]){ans[b[i].id] = 1;continue;}while(l < ql) work(l++);while(r < qr) work(++r);while(r > qr) work(r--);while(l > ql) work(--l);if(LCA == dfn[ql])ans[b[i].id] = cnt;elseans[b[i].id] = cnt + (!col[gg[LCA]] ? 1 : 0); }for(int i = 1 ; i <= m ; i++) printf("%dn" , ans[i]);return 0;
}

外送一道练习题P1997 faebdc 的烦恼

拓展：树上带修莫队

水一道黑题喔 （bushi

跟上面的没什么区别，改一改就能交

P4074 [WC2013]糖果公园

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long using namespace std;
const int N = 300010 , M = 600010 , K = 23;
int h[N] , to[M] , nxt[M] , tot = 1;
int a[N] , n , mx , len1 , len2;
int fir[N] , las[N] , dfn[N] , idx , ttim;
int cnt[N] , m , LEN;
int dp[N][K] , dep[N] , bel[N] , vis[N];
int l = 1 , r = 0 , tt;
ll w[N] , v[N] , ans[N] , now;
struct query
{int l , r , t , id;int Lca;
} b[N];
struct work
{int x , val , t;
} c[N];inline void add(int a , int b)
{to[++tot] = b ; nxt[tot] = h[a] ; h[a] = tot;
}
bool cmp(query a , query b)
{return (bel[a.l] ^ bel[b.l]) ? bel[a.l] < bel[b.l] : ((bel[a.r] ^ bel[b.r]) ? bel[a.r] < bel[b.r] : a.t < b.t); 
}
void dfs(int x , int lst)
{for(int k = 1 ; k < K ; k++) dp[x][k] = dp[dp[x][k - 1]][k - 1];fir[x] = ++idx ; dfn[idx] = x;for(int i = h[x] , v ; v = to[i] , i ; i = nxt[i]){if(v == lst) continue;dep[v] = dep[x] + 1 ; dp[v][0] = x;dfs(v , x);}las[x] = ++idx ; dfn[idx] = x;
}
inline int lca(int x , int y)
{if(dep[x] < dep[y]) swap(x , y);for(int k = K - 1 ; k >= 0 ; k--) if(dep[dp[x][k]] >= dep[y]) x = dp[x][k];if(x == y) return x;for(int k = K - 1 ; k >= 0 ; k--) if(dp[x][k] != dp[y][k]) x = dp[x][k] , y = dp[y][k];return dp[x][0];
}
inline void work(int x)
{vis[x] = 1 - vis[x];if(vis[x]){cnt[a[x]]++ ; now += v[a[x]] * w[cnt[a[x]]];}else{now -= v[a[x]] * w[cnt[a[x]]];cnt[a[x]]--;}
}
inline void twork(int kk)
{int gg = c[kk].x;if(l <= fir[gg] && fir[gg] <= r) work(gg);if(l <= las[gg] && las[gg] <= r) work(gg);swap(c[kk].val , a[gg]);if(l <= fir[gg] && fir[gg] <= r) work(gg);if(l <= las[gg] && las[gg] <= r) work(gg);
}
inline ll read()
{char c = getchar() ; ll ret = 0;while(c < '0' || c > '9') c = getchar();while(c >= '0' && c <= '9'){ret = ret * 10 + c - '0';c = getchar();}return ret;
}
int main()
{n = read() ; mx = read() ; m = read();LEN = sqrt(2 * n);for(int i = 1 ; i <= mx ; i++) v[i] = read();for(int i = 1 ; i <= n ; i++) w[i] = read();for(int i = 1 ; i <= 2 * n ; i++) bel[i] = (i - 1) / LEN + 1;for(int i = 1 ; i < n ; i++){ll a , b;a = read() ; b = read();add(a , b) ; add(b , a); }dep[1] = 1;dfs(1 , 1);for(int i = 1 ; i <= n ; i++) a[i] = read();for(int i = 1 ; i <= m ; i++){ll opt , x , y;opt = read() ; x = read() ; y = read();if(opt == 0){ttim++;c[ttim].t = ttim; c[ttim].x = x , c[ttim].val = y;}else{b[++len1].t = ttim;b[len1].id = len1;if(fir[x] > fir[y]) swap(x , y);int LCA = lca(x , y);if(LCA == x) b[len1].l = fir[x] , b[len1].r = fir[y] , b[len1].Lca = 0;else b[len1].l = las[x] , b[len1].r = fir[y] , b[len1].Lca = LCA;}}sort(b + 1 , b + len1 + 1 , cmp);for(int i = 1 ; i <= len1 ; i++){int ql = b[i].l , qr = b[i].r , qt = b[i].t , LCA = b[i].Lca;while(tt < qt) twork(++tt);while(tt > qt) twork(tt--);while(l < ql) work(dfn[l++]);while(l > ql) work(dfn[--l]);while(r < qr) work(dfn[++r]);while(r > qr) work(dfn[r--]);if(LCA) work(LCA);ans[b[i].id] = now;if(LCA) work(LCA);}for(int i = 1 ; i <= len1 ; i++) printf("%lldn" , ans[i]);return 0;
}

第十四分块（前体

莫队二次离线

基于差分思想，将本来时间复杂度挺大的转移拆掉

具体的…慢慢理解

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<tuple>
#define ll long long
using namespace std;const int N = 200010;
int bel[N] , a[N];
int LEN , n , m , k;ll t[N] , pref[N];
ll ans[N];struct query
{int l , r , id ;ll ans;
} b[N];vector<tuple<int , int , int> > v[N];
vector<int> buc;inline bool cmp(query a , query b)
{return (bel[a.l] == bel[b.l]) ? a.r < b.r : bel[a.l] < bel[b.l];
}inline int check(int x)
{int ret = 0;while(x){ret++ ; x -= (x & (-x));}return ret;
}int main()
{scanf("%d%d%d" , &n , &m , &k);if(k > 14){for(int i = 1 ; i <= m ; i++) printf("0n");return 0;}for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]);for(int i = 1 ; i <= m ; i++) scanf("%d%d" , &b[i].l , &b[i].r) , b[i].id = i , b[i].ans = 0;LEN = sqrt(n);for(int i = 1 ; i <= n ; i++) bel[i] = (i - 1) / LEN + 1;sort(b + 1 , b + m + 1 , cmp);for(int i = 0 , inf = (1 << 14) ; i < inf ; i++)if(check(i) == k) buc.push_back(i);for(int i = 1 ; i <= n ; i++){for(auto x : buc) ++t[a[i] ^ x];pref[i] = t[a[i + 1]];}memset(t , 0 , sizeof t);int l = 1 , r = 0;for(int i = 1 ; i <= m ; i++){int ql = b[i].l , qr = b[i].r;if(l < ql) v[r].emplace_back(l , ql - 1 , -i);while(l < ql) b[i].ans += pref[l - 1] , l++;if(l > ql) v[r].emplace_back(ql , l - 1 , i);while(l > ql) b[i].ans -= pref[l - 2] , l--;if(r < qr) v[l - 1].emplace_back(r + 1 , qr , -i);while(r < qr) b[i].ans += pref[r] , ++r;if(r > qr) v[l - 1].emplace_back(qr + 1 , r , i);while(r > qr) b[i].ans -= pref[r - 1] , r--;}for(int i = 1 , id , l , r ; i <= n ; i++){for(auto x : buc) ++t[a[i] ^ x];for(const auto& x : v[i]){tie(l , r , id) = x;for(int j = l , tmp = 0 ; j <= r ; j++){tmp = t[a[j]];if(j <= i && k == 0) --tmp;if(id < 0) b[-id].ans -= tmp;else b[id].ans += tmp;}}}for(int i = 1 ; i <= m ; i++) b[i].ans += b[i - 1].ans;for(int i = 1 ; i <= m ; i++) ans[b[i].id] = b[i].ans;for(int i = 1 ; i <= m ; i++) printf("%lldn" , ans[i]);return 0;
}