带修改的莫队、树上莫队
前言
莫队大法好！只是一卡离线就GG
由于莫队都是套路，因此几乎不会做解释
- 莫队算法
https://blog.sengxian.com/algorithms/mo-s-algorithm
https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html
数颜色 - HYSBZ 2120
思路
带修改莫队模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 10000 + 5;
const int M = 1e6 + 5;
struct QQuery{
int l, r, tim, idx;
};
struct QModify{
int pos, val, pre;
};
int BLOCK_SIZE;
int ans[N];
int cnt[M];
int a[N];
QQuery queq[N];
QModify queu[N];
bool cmp(const QQuery& a, const QQuery& b){
if(a.l/BLOCK_SIZE != b.l/BLOCK_SIZE) return a.l < b.l;
else if(a.r/BLOCK_SIZE != b.r/BLOCK_SIZE) return a.r < b.r;
return a.tim/BLOCK_SIZE < b.tim/BLOCK_SIZE;
}
void moveTimeForward(int tim, int l, int r, int& ans){
QModify& qcur = queu[tim];
qcur.pre = a[qcur.pos];
a[qcur.pos] = qcur.val;
if(l <= qcur.pos && qcur.pos <= r){
if((--cnt[qcur.pre]) == 0) ans--;
if((++cnt[qcur.val]) == 1) ans++;
}
}
void moveTimeBack(int tim, int l, int r, int& ans){
QModify& qcur = queu[tim];
a[qcur.pos] = qcur.pre;
if(l <= qcur.pos && qcur.pos <= r){
if((--cnt[qcur.val]) == 0) ans--;
if((++cnt[qcur.pre]) == 1) ans++;
}
}
void add(int pos, int& ans){
if((++cnt[a[pos]]) == 1) ans++;
}
void del(int pos, int& ans){
if((--cnt[a[pos]]) == 0) ans--;
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
memset(cnt, 0, sizeof(cnt));
BLOCK_SIZE = (int)pow(n, 2.0/3);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
int ppq = 0, ppu = 0;
while(q--){
char s[2];
int x, y;
scanf("%s%d%d", s, &x, &y);
if(s[0] == 'Q'){
queq[ppq] = QQuery{x, y, ppu, ppq};
ppq++;
}else{
queu[++ppu] = QModify{x, y, 0};
}
}
sort(queq, queq + ppq, cmp);
int r = -1, l = 0, tim = 0, curans = 0;
for(int i = 0; i < ppq; i++){
QQuery& q = queq[i];
while(tim < q.tim) moveTimeForward(++tim, l, r, curans);
while(tim > q.tim) moveTimeBack(tim--, l, r, curans);
while(l < q.l) del(l++, curans);
while(l > q.l) add(--l, curans);
while(r < q.r) add(++r, curans);
while(r > q.r) del(r--, curans);
ans[q.idx] = curans;
}
for(int i = 0; i < ppq; i++){
printf("%d\n", ans[i]);
}
}
}
Machine Learning - CodeForces - 940F
题意
给定n个整数与m个操作，操作有两种，第一种是查询[l,r]的mex{c(1),…,c(1e9)}，c(x)指x出现的次数，第二种是修改一个整数的值
思路
首先需要离散化，然后套莫队
注意cnt数组和mp数组越界的问题，因为修改的数值都是新数值，因此需要双倍空间
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
struct QQuery{
int l, r, tim, idx;
};
struct QModify{
int pos, val, pre;
};
int BLOCK_SIZE;
int ans[N];
int cnt[N << 1], used[N];
int a[N];
int mp[N << 1], pmp;
QQuery queq[N];
QModify queu[N];
bool cmp(const QQuery& a, const QQuery& b){
if(a.l/BLOCK_SIZE != b.l/BLOCK_SIZE) return a.l < b.l;
else if(a.r/BLOCK_SIZE != b.r/BLOCK_SIZE) return a.r < b.r;
return a.tim/BLOCK_SIZE < b.tim/BLOCK_SIZE;
}
void add(int val){
used[cnt[val]]--;
cnt[val]++;
used[cnt[val]]++;
}
void del(int val){
used[cnt[val]]--;
cnt[val]--;
used[cnt[val]]++;
}
void moveTimeForward(int tim, int l, int r){
QModify& qcur = queu[tim];
qcur.pre = a[qcur.pos];
a[qcur.pos] = qcur.val;
if(l <= qcur.pos && qcur.pos <= r){
del(qcur.pre);
add(qcur.val);
}
}
void moveTimeBack(int tim, int l, int r){
QModify& qcur = queu[tim];
a[qcur.pos] = qcur.pre;
if(l <= qcur.pos && qcur.pos <= r){
del(qcur.val);
add(qcur.pre);
}
}
int main(){
int n, q;
while(~scanf("%d%d", &n, &q)){
memset(cnt, 0, sizeof(cnt));
memset(used, 0, sizeof(used));
pmp = 0;
BLOCK_SIZE = (int)pow(n, 2.0/3);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
mp[++pmp] = a[i];
}
int ppq = 0, ppu = 0;
while(q--){
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1){
queq[ppq] = QQuery{x, y, ppu, ppq};
ppq++;
}else{
mp[++pmp] = y;
queu[++ppu] = QModify{x, y, 0};
}
}
sort(mp + 1, mp + 1 + pmp);
pmp = unique(mp + 1, mp + 1 + pmp) - mp - 1;
for(int i = 1; i <= ppu; i++){
queu[i].val = lower_bound(mp + 1, mp + 1 + pmp, queu[i].val) - mp;
}
for(int i = 1; i <= n; i++){
a[i] = lower_bound(mp + 1, mp + 1 + pmp, a[i]) - mp;
}
sort(queq, queq + ppq, cmp);
int r = 0, l = 1, tim = 0;
for(int i = 0; i < ppq; i++){
QQuery& q = queq[i];
while(tim < q.tim) moveTimeForward(++tim, l, r);
while(tim > q.tim) moveTimeBack(tim--, l, r);
while(r < q.r) add(a[++r]);
while(r > q.r) del(a[r--]);
while(l < q.l) del(a[l++]);
while(l > q.l) add(a[--l]);
int mex = 1;
while(used[mex]) mex++;
ans[q.idx] = mex;
}
for(int i = 0; i < ppq; i++){
printf("%d\n", ans[i]);
}
}
}
【WC2013】糖果公园 - uoj 58
思路
树上莫队模板题
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
struct squery{
int u, v, tim, idx;
};
struct supdate{
int u, val, preval;
};
struct edge{
int v, next;
};
squery query[N];
supdate update[N];
int w[N], v[N], c[N];
edge e[N << 1];
int head[N], tot;
int belong[N];
int stk[N], pstk;
int fa[N][18];
int dpt[N];
bool used[N];
int cnt[N];
ll ans[N];
int BLOCK_SIZE;
bool cmp(const squery& a, const squery& b){
if(belong[a.u] != belong[b.u]) return belong[a.u] < belong[b.u];
else if(belong[a.v] != belong[b.v]) return belong[a.v] < belong[b.v];
else return a.tim/BLOCK_SIZE < b.tim/BLOCK_SIZE;
}
inline void init(){
memset(head, -1, sizeof(head));
memset(fa, -1, sizeof(fa));
memset(cnt, 0, sizeof(cnt));
memset(used, 0, sizeof(used));
tot = 0;
}
inline void addEdge(int u, int v){
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
void dfs(int u, int pre, int depth){
int bottom = pstk;
dpt[u] = depth;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(v == pre) continue;
fa[v][0] = u;
dfs(v, u, depth + 1);
if(pstk - bottom >= BLOCK_SIZE){
while(pstk != bottom){
belong[stk[pstk--]] = u;
}
}
}
stk[++pstk] = u;
}
void initLCA(int n){
for(int j = 1; j <= 17; j++){
for(int u = 1; u <= n; u++){
if(fa[u][j - 1] == -1) continue;
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
}
}
void initBlockAndLCA(int n){
BLOCK_SIZE = (int)pow(n, 2.0/3);
pstk = 0;
dfs(1, -1, 0);
while(pstk >= 1){
belong[stk[pstk--]] = 1;
}
initLCA(n);
}
int getFa(int u, int v){
if(dpt[u] > dpt[v]) swap(u, v);
for(int j = 17; j >= 0; j--){
if(fa[v][j] == -1 || dpt[fa[v][j]] < dpt[u]) continue;
v = fa[v][j];
}
if(u == v) return u;
for(int j = 17; j >= 0; j--){
if(fa[v][j] == -1 || fa[u][j] == -1 || fa[u][j] == fa[v][j]) continue;
u = fa[u][j], v = fa[v][j];
}
return fa[u][0];
}
void reverse(int u, ll& ans){
if(used[u]){
ans -= (ll)v[c[u]] * w[cnt[c[u]]];
cnt[c[u]]--;
}else{
cnt[c[u]]++;
ans += (ll)v[c[u]] * w[cnt[c[u]]];
}
used[u] ^= 1;
}
void change(int u, int val, ll& ans){
if(used[u]){
reverse(u, ans);
c[u] = val;
reverse(u, ans);
}else{
c[u] = val;
}
}
void moveTimeForward(int tim, ll& ans){
int u = update[tim].u;
update[tim].preval = c[u];
change(u, update[tim].val, ans);
}
void moveTimeBack(int tim, ll& ans){
int u = update[tim].u;
change(u, update[tim].preval, ans);
}
void moveNode(int u, int v, ll& ans){
while(u != v){
if(dpt[u] < dpt[v]){
reverse(v, ans);
v = fa[v][0];
}else{
reverse(u, ans);
u = fa[u][0];
}
}
}
int main(){
int n, m, q;
while(~scanf("%d%d%d", &n, &m, &q)){
init();
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 - 1; i++){
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
initBlockAndLCA(n);
int pp = 0, pq = 0;
while(q--){
int type, x, y;
scanf("%d%d%d", &type, &x, &y);
if(type == 0){
update[++pq] = supdate{x, y, -1};
}else{
query[pp] = squery{x, y, pq, pp};
pp++;
}
}
sort(query, query + pp, cmp);
int u = query[0].u, v = query[0].v, tim = 0;
ll curans = 0;
while(tim < query[0].tim) moveTimeForward(++tim, curans);
moveNode(u, v, curans);
reverse(getFa(u, v), curans);
ans[query[0].idx] = curans;
reverse(getFa(u, v), curans);
for(int i = 1; i < pp; i++){
while(tim < query[i].tim) moveTimeForward(++tim, curans);
while(tim > query[i].tim) moveTimeBack(tim--, curans);
int nu = query[i].u, nv = query[i].v;
moveNode(u, nu, curans);
moveNode(v, nv, curans);
int lca = getFa(nu, nv);
reverse(lca, curans);
ans[query[i].idx] = curans;
reverse(lca, curans);
u = nu, v = nv;
}
for(int i = 0; i < pp; i++){
printf("%lld\n", ans[i]);
}
}
}
