​​​​​​​[蓝桥杯

十四想用暴力解决问题他想枚举每个节点每个节点代表一棵树他想只要建立一个桶数组把每次出现的颜色放在桶里每次遍历完一个节点和它的所有子节点后就统计这个桶数组里的所有非零颜色是否相同如果相同的话这就是一棵颜色平衡树如果不相同的话这就不是一棵颜色平衡树。

时间之神乌露提亚说她用尽了所有的魔力和生命也只能让这个世界回退一分钟所以你必须在一秒之内解决这个问题十四看了看CCF老爷机每秒只能计算10^8次然而使用暴力的话时间复杂度怎么着也来到了O(n^2)的级别所以愚蠢的十四只能求助题解题解说要用树上莫队但是愚蠢的十四并不会用树上莫队所以让我们和十四一起愉快地学习树上莫队吧

十四是要成为火影的男人所以他并不会把前置知识列出来然后让看题解小伙伴们自己去找资料学习这些内容所以让我们和十四一起愉快地学习分块吧

分块算法

https://www.acwing.com/problem/content/description/244/

屏幕前的大佬一眼就看出来了这是一道线断树的板子题但是愚蠢的十四并不会写线断树所以十四本能地想用暴力解决问题

十四每次在修改指令的时候从左到右枚举把数列中的数字一个一个加上指定的值然后在询问的时候也从做到右一个一个把数列上的数字加起来得到结果每次操作预期进行n次运算要进行m次这样的操作那么时间复杂度就来到了O(nm)但是N和M的最大值是10^5如果有10^5个数和10^5次操作的话一秒内就有10^5*10^510^10次操作但是可怜的CCF老爷机一秒只能进行10^8次运算所以十四决定对这个暴力的办法进行一些优化

十四想要把N个数的序列从头到尾分成长度相等的很多很多部分每次C操作的时候如果操作的序列[l,r]能覆盖很多区间的话就会有以下情况

我们假设5个数字为一部分一块于是1115、1620、2125、2530将这个序列分成了四块此时我们想进行这样的操作C

数列下标1112131415161718192021222324252627282930数值11451419198101145141

我们用黄色和绿色表示分隔开来的分块用紫色表示需要修改的区间那么显然我们看见紫色的区域完整地覆盖住了1620、2125这两块十四想到能不能建立一个块标记数组这个数组存的是完整的块中的每个数字需要加上的数字例如这里就要把1620和2125这两个完整的块中每个数字都要加上3于是我们引入块标记数组

数列下标1112131415161718192021222324252627282930数值11451419198101145141

十四发现只要这次对块进行标记只进行了2次标记就操作了2*510个数字非常节省时间但是这时候就出现了另外一个问题完整的块之外的数字怎么进行操作

我们发现1315和2627这两部分还没有进行操作如果改动1115和2630这两个块的块标记的话就会牵连到无辜的1112和2830所以十四决定一个一个地把13、14、15、26、27的数加上3:

数列下标1112131415161718192021222324252627282930数值11784419198101178141

3的操作但是屏幕前的你提出了异议一斤鸭梨如果对所有没有被完整覆盖的块里需要修改的元素一个一个地修改的话不是仍然有和暴力一样的复杂度吗这样的话和直接暴力有什么很大的区别吗

但是通过观察我们发现每次操作的过程中没有被覆盖的块最多两个,也就是说我们需要一个一个操作的块最多是两个。

那么我们假设每块里面有a个元素这样的话序列中的n个元素就被我们分成了(n/a)块对于我们每次的操作我们最多要对(n/a)块进行块标记并且对没有覆盖的2块内最多有2*a2a个元素一个一个进行修改所以对于每次操作我们有(n/a)2a次操作要进行要把这个次数降到最少我们不妨把a定为

这样我们就发现(n/a)和2a的操作次数在同一个数量级于是我们得出结论在这一题的分块中我们把每块的元素个数定为可以使得操作的次数降到最低那么对m次操作我们题的时间复杂度也就算出来了O(m)怎么样是不是比之前的O(nm)要优化了一些呢

机遇这样的时间复杂度我们这题的所有数据也能在一秒之内算出来了。

r我们要怎么操作呢

类似于修改的操作我们把每块的和计为sum在输入的时候对每块进行预处理在修改的时候加上块内修改元素的个数乘以修改的值这样我们就能轻松维护块内所有值的和对于被询问区间完全覆盖的块我们直接加上这块的和值对于没有被完全覆盖的块同样也是最多两个这样的块我们直接暴力加起来就好啦

对于所有在块内的询问和操作区间我们全部暴力就好啦反正块内的元素最多个暴力同样不会增加时间复杂度

#includecstdio

LPdevi[u],RPdevi[v];if(LPRP){for(int

iu;iv;i)a[i]k;blk[LP].sumk*(v-u1);}else{for(int

iu;iblk[LP].r;i)a[i]k;blk[LP].sumk*(blk[LP].r-u1);for(int

iblk[RP].l;iv;i)a[i]k;blk[RP].sumk*(v-blk[RP].l1);for(int

iLP1;iRP;i){blk[i].tagk;blk[i].sumk*(blk[i].r-blk[i].l1);}}return

long

iu;iv;i)ansa[i]blk[LP].tag;return

ans;}else{for(int

iu;iblk[LP].r;i)ansa[i]blk[LP].tag;for(int

iblk[RP].l;iv;i)ansa[i]blk[RP].tag;for(int

iLP1;iRP;i)ansblk[i].sum;return

ans;}

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,m,n;long

lensqrt(n);for(i1;in;i){scanf(%lld,a[i]);devi[i](i-1)/len1;blk[devi[i]].suma[i];if(i%len0)

c[2];while(m--){int

u,v;scanf(%s,c);scanf(%d%d,u,v);if(uv){

int

}if(c[0]C){scanf(%lld,k);add(u,v,k);}else

printf(%lld\n,quest(u,v));}return

and

emmm我们先来看看逆序对是什么逆序对是对于给定的一段正整数序列存在序列中aiaj且ij的有序对。

百度百科就是好一下就帮我水了十几个字那么每次交换两个数a[u],a[v](uv)这两个数坐标之外的数自然不会被影响序列中在这两个数中间的数当且仅当数字满足min(a[u],a[v])a[q]max(a[u],[v])且uqv的时候如果a[u]a[v],a[q]就会和a[u]、a[v]a产生两个新的逆序对但如果a[u]a[v],a[q]则与a[u]、a[v]原先产生的逆序对就会消失我们针对这一点对整个序列分块之后每块内初始的元素都是从小到大的顺序陈列的我们每次交换之后只需维护每块内从小到大的顺序每次块外查询直接暴力分一个不排序的数组a记前后顺序块内直接二分查看有多少个数字在(a[u],a[v])范围之内这个操作用到二分当然就用有顺序的数组v啦

#includecstdio

f1,ans0;kfind(v[LP].begin(),v[LP].end(),xx)-v[LP].begin();v[LP][k]yy;

devi[yy]LP;sort(v[LP].begin(),v[LP].end());kfind(v[RP].begin(),v[RP].end(),yy)-v[RP].begin();v[RP][k]xx;

devi[xx]RP;sort(v[RP].begin(),v[RP].end());if(xxyy){f-1;int

txx;

iLP1;iRP;i)anslower_bound(v[i].begin(),v[i].end(),yy)-upper_bound(v[i].begin(),v[i].end(),xx);}int

(ans*21)*f;

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,n,q,tot0;scanf(%d%d,n,q);int

devi[i]0;a[i]0;

}for(i1;in;i){a[i]i;devi[i](i-1)/len1;v[devi[i]].push_back(i);if((i-1)%len0)

blk[tot].ri;}long

}anssolve(l,r);printf(%lld\n,ans);}return

十四的内心逐渐膨胀了起来觉得紫题不过如此于是决定再切一道分块紫题作诗

同一块内出现的偶数元素当然是固定的但是在一段区间内有其他的块也有一些不完整的块内元素所以对于不完整的块内元素每次固然是暴力统计然而对于完整的块我们可以提前预处理出完整的块相连中偶数次出现的元素个数f同时用cnt记录从每块的头开始记录每个元素出现到整个数列结尾的次数这样通过相减可以便捷地统计出每个元素在连接的完整的块间的出现次数这样可以和两边暴力统计出来的元素个数相加得出新的对偶元素同时也可以去掉由于完整的块间是偶数次出现次数而加上边缘暴力统计之后沦落为奇数次出现的元素。

#includecstdio

LPdevi[l],RPdevi[r];if(LPRP){int

sum0,top0;for(int

il;ir;i){num[a[i]];lst[top]a[i];}while(top){if(num[lst[top]]%20

num[lst[top]]!0)sum;num[lst[top]]0;top--;}return

sum;}else{int

il;iblk[LP].r;i){num[a[i]];lst[top]a[i];}for(int

iblk[RP].l;ir;i){num[a[i]];lst[top]a[i];}while(top){int

t!0){int

ucnt[LP1][t]-cnt[RP][t];if(u%21

num[t]%21)

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,tot0;scanf(%d%d%d,n,c,m);int

lensqrt(n);for(i0;ilen1;i)for(j0;jlen1;j)f[i][j]0;for(i0;ilen1;i)for(j0;jc;j)cnt[i][j]0;for(i0;in;i){

lst[i]0;num[i]0;

}for(i1;in;i){scanf(%d,a[i]);devi[i](i-1)/len1;if((i-1)%len0)

blk[tot].ri;}blk[tot].rn;for(i1;in;ilen){int

didevi[i],sum0;for(ji;jn;j){cnt[di][a[j]];if(cnt[di][a[j]]%2!0

if(cnt[di][a[j]]%20)

l,r;scanf(%d%d,l,r);l((llans)%n)1;r((rlans)%n)1;if(lr){

int

anssolve(l,r);printf(%d\n,ans);lansans;}return

蒲公英

我们可以申请n个vector数组储存每种元素出现的坐标这样我们就可以在之后方便地统计元素的出现次数同样分块统计连接的块之间最大的出现次数和加上块外的部分最大出现次数的元素

那么我们就愉快地和十四一起AC掉这道题吧

upper_bound(v[k].begin(),v[k].end(),r)-lower_bound(v[k].begin(),v[k].end(),l);

int

LPdevi[l],RPdevi[r];if(LPRP){int

ans0,maxsum0;for(int

a[i]ans)){ansa[i];maxsumt;}}return

c[ans];}else{int

ans0,maxsum0;if(RPLP1){ansf[LP1][RP-1];maxsumget_num(l,r,ans);}for(int

il;iblk[LP].r;i){int

a[i]ans)){ansa[i];maxsumt;}}for(int

iblk[RP].l;ir;i){int

a[i]ans)){ansa[i];maxsumt;}}return

c[ans];}

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,n,tot0;scanf(%d%d,n,m);int

lensqrt(n);for(i1;in;i){scanf(%d,a[i]);devi[i](i-1)/len1;if((i-1)%len0)

blk[tot].ri;c[i]a[i];}blk[tot].rn;sort(c1,cn1);for(i1;in;i){a[i]lower_bound(c1,cn1,a[i])-c;v[a[i]].push_back(i);}for(i1;in;ilen){int

didevi[i];int

maxn0;memset(cnt,0,sizeof(cnt));for(ji;jn;j){cnt[a[j]];if(cnt[a[j]]cnt[maxn]

(cnt[a[j]]cnt[maxn]

u,v;scanf(%d%d,u,v);u((ulans-1)%n)1;v((vlans-1)%n)1;if(uv){

int

anssolve(u,v);printf(%d\n,ans);lansans;}return

莫队算法

通过上面的例题你已经熟练地掌握了分块那么我们就来看看莫队算法吧

不知道屏幕前的小伙伴们在做题的时候有没有发现上面有很多题里面提到了“在线”这一概念其实在线的意思就是通过各种办法强行让你按照题目所给出的询问顺序来进行查询操作具体能强制你在线的方法大概有每一次询问区间由上一次询问的结果加密得到或者是在询问的区间内加上一些修改的操作那么出题人为什么对在线这么重视呢这当然是因为“离线”即不按照题给的顺序进行查询能对时间的要求降低很多。

莫队就是这样一种针对离线查询的算法我们将众多的询问按照以下规则进行排序1.区间左边所在的块下标靠前的排在前面2.区间左边在同一个块内的话按照区间右边从小到大排序。

电视机前的小伙伴们于是就有了疑问对于区间的右边我们按元素从小到大排序那我们为什么不对区间左边边按元素从小到大排序呢这样不是更佳精准吗

我们先来看一道题目

我们首先按照上述规则对询问区间进行排序然后设置左指针lz1和右指针rz0对区间按顺序进行如下操作

while(lzl)

那么我们如何让时间复杂度尽量低呢自然是减少指针的移动次数回到上面提出的疑问如果我们对区间的左边进行严格排序而不是按照分块排序的话区间右边自然不能愉快地从小到大排序所以右指针在这一排序规则下移动次数会大很多而对于莫队算法的排序左指针的移动次数仅仅限制在一个区间范围之内而右指针在左区间相同的条件下也只有一个移动方向这自然最大程度地避免了指针来回移动同时能将时间复杂度降到最低。

通过上述思考我们知道了莫队是基于对离线的询问进行排序然后用指针进行暴力移动在此基础上尽量减少指针的移动次数的算法。

#includecstdio

LPdevi[a.l],RPdevi[b.l];if(LP!RP)

return

lensqrt(n);for(i1;in;i){scanf(%d,a[i]);devi[i](i-1)/len1;cnt[a[i]]0;}scanf(%d,m);for(i1;im;i){q[i].idi;scanf(%d%d,q[i].l,q[i].r);}sort(q1,qm1,cmp);int

lq[k].l,rq[k].r,idq[k].id;while(lzl)

del(a[rz--],sum);ans[id]sum;}for(i1;im;i)

修改莫队

通过上述的了解我们知道了莫队是对于在线非常敏感的算法但是对于一些修改类的强制在线我们是可以用一些神奇的膜法绕过去的我们来看这道题[国家集训队]

数颜色

u,v;scanf(%s%d%d,op,u,v);if(*opQ){mq;

q[mq].idmq;q[mq].lu;q[mq].rv;q[mq].tmc;}else

那么对于所有的询问来说有哪些可以被影响到呢我们通过思考可以想到对于这样的区间当切仅当满足以下条件1.这个询问的时间戳在修改区间的时间之后2.这个询问的区间和修改的区间范围有交集

如果不满足以上两点我们自然可以愉快地按照莫队算法进行计算那么如果这个区间被影响了要怎么办呢这里涉及到一个小技巧我们可以把所有的修改操作存在一个数组里当修改进行时只需要将当前的数和修改数组里的数进行交换即可那么在改回来的时候再次交换就又换回了原来的数。

#includecstdio

devi[N],a[N],mc,mq,cnt[N],ans[N];

struct

bldevi[b.l],brdevi[b.r];if(al!bl)

return

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,n;scanf(%d%d,n,m);for(i1;in;i)scanf(%d,a[i]);mc0;mq0;for(i1;im;i){char

op[2];int

u,v;scanf(%s%d%d,op,u,v);if(*opQ){mq;

q[mq].idmq;q[mq].lu;q[mq].rv;q[mq].tmc;}else

if(*opR){c[mc].qu;c[mc].cv;}}int

lencbrt((double)n

max(1,mc))1;for(i1;imax(n,m);i)

devi[i]i/len;c[0].q0;sort(q1,qmq1,cmp);int

lz1,rz0,sum0,tz0;memset(cnt,0,sizeof(cnt));for(i1;imq;i){int

lq[i].l,rq[i].r,tq[i].t,idq[i].id;while(rzr)

add(a[--lz],sum);while(tzt){tz;int

cgec[tz].q;if(lcge

cger){add(c[tz].c,sum);del(a[cge],sum);}swap(a[cge],c[tz].c);}while(tzt){int

cgec[tz].q;if(lcge

cger){add(c[tz].c,sum);del(a[cge],sum);}swap(a[cge],c[tz].c);tz--;}ans[id]sum;}for(i1;imq;i)

✳️回滚莫队/不删除莫队

我们来看这样一道题目给你一个长度为n的数组A和m个询问区间每次询问区间【LR】内重要度最大的数字要求输出其重要度这里i的重要度的定义是i*i在区间内出现的次数

对于区间内出现的次数增加我们自然是很好操作的那么对于删除呢我们即便可以将左指针向右推我们也不能对与区间最大的重要度去除对于删除元素的影响那么我们可以进行如下操作

对于所有左区间在一个块内的询问区间我们将指针移动分为两拨我们设置一个rightblk[LP].r,我们把左指针lzright1右指rzright。

我们先移动又指针到q[x].r,由于询问区间已经按照规则排序的缘故在计算之后的区间时右指针只有向右移动这一个方向。

移动好之后我们先用一个临时变量记录一下这时候最重要的状态。

接下来我们向左边移动左指针移动到q[x].l时候更新最重要的状态并且在这时候记录到ans数组里面。

记录完之后我们将最重要的状态赋值为之前用临时变量记录的状态这一步的操作就叫做回滚这样我们就回到了不被左边影响的状态。

当所有区间左边在一个块内的询问处理好之后我们把一切记录状态的数组和变量清零进行下一个询问区间的操作。

✳️树上莫队

我们引入一个新的概念欧拉数列即在dfs遍历的时候最开始的时候记录一下结束的时候记录一下

void

father){ora[oranum]x;fst[x]oranum;for(int

continue;bjdfs(y,x);}ora[oranum]x;lst[x]oranum;return

我们同时可以顺手记录下每个元素出现的位置fst[i]和结束时出现的位置lst[i]我们通过观察可以发现对于两个元素u,v的路径上出现的元素只会在lst[u]道fst[v]上出现一次并且路径上两节点的最近公共祖先lca则不会出现所以对于每条路径我们只要记录欧拉序列中出现一次的元素和lca即可记得要考虑好u是u和v的lca这样的情况。

#includecstdio

fst[N],lst[N],a[N],len,tot,pre[N],ans[N];

int

ora[N],cnt[N],oranum,depth[N],vis[N],dp[N][20];

int

LPget_devi(a.l),RPget_devi(b.l);if(LP!RP)

return

v){edge[tot].nextpre[u];edge[tot].tov;

pre[u]tot;return

father){ora[oranum]x;fst[x]oranum;for(int

continue;bjdfs(y,x);}ora[oranum]x;lst[x]oranum;return

void

i1;(ii)depth[x];i)dp[x][i]dp[dp[x][i-1]][i-1];for(int

continue;vis[y]1;dp[y][0]x;depth[y]depth[x]1;lcadfs(y);}return

void

sum){appt[x]^1;if(appt[x]){if(!cnt[a[x]])

sum;cnt[a[x]];}else{cnt[a[x]]--;if(!cnt[a[x]])

sum--;}return

klog2(depth[u]-depth[v]);for(int

ik;i0;i--)if(depth[dp[u][i]]depth[v])udp[u][i];if(uv)

return

ik;i0;i--){if(dp[u][i]dp[v][i])

continue;udp[u][i];vdp[v][i];}return

dp[u][0];

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,n;scanf(%d%d,n,m);for(i1;in;i){scanf(%d,a[i]);px.push_back(a[i]);}sort(px.begin(),px.end());px.erase(unique(px.begin(),px.end()),px.end());for(i1;in;i)

a[i]lower_bound(px.begin(),px.end(),a[i])-px.begin();for(i1;in;i){int

u,v;scanf(%d%d,u,v);addedge(u,v);addedge(v,u);}bjdfs(1,-1);lensqrt(oranum);memset(depth,0,sizeof(depth));memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));depth[1]1;vis[1]1;lcadfs(1);for(i1;im;i){int

u,v;scanf(%d%d,u,v);if(fst[u]fst[v])

swap(u,v);int

plca(u,v);if(pu){q[i].idi;q[i].lfst[u];q[i].rfst[v];}else{q[i].idi;q[i].llst[u];q[i].rfst[v];q[i].pp;}}sort(q1,qm1,cmp);int

lz1,rz0,sum0;memset(cnt,0,sizeof(cnt));memset(appt,0,sizeof(appt));for(int

i1;im;i){int

lq[i].l,rq[i].r,pq[i].p,idq[i].id;while(rzr)

add(p,sum);}for(int

i1;im;i)printf(%d\n,ans[i]);return

最后我们来看看颜色平衡树这道题

十四经过上面的联系十四不由自主地想出了这样一个解法对于欧拉数列从fst[i]到lst[i]即可表达一颗完整的子树而通过枚举n个节点统计其对应的所有fst[i]lst[i]中的颜色数量即可可以先自己制造问题所有的fst[i]lst[i]然后基于欧拉数列的分块进行排序这些询问区间然后用莫队的算法通过移动指针得到每个区间的颜色数量。

问题来了既然维护的是颜色出现的次数每次要进行判断我们自然不肯能枚举每个元素然后挨个挨个查非零的元素是否出现了同样的次数那我们对于删除元素的处理自然非常麻烦于是我们想到了用回滚莫队的方法维护last数组

#includecstdio

len,ora[N],oranum,tot,fst[N],lst[N];

int

cnt[N],last[N],color[N],top,pre[N];

struct

LPget_devi(a.l),RPget_devi(b.l);if(LP!RP)

return

v){edge[tot].nextpre[u];pre[u]tot;edge[tot].tov;return

void

x){ora[oranum]x;fst[x]oranum;for(int

yedge[i].to;bjdfs(y);}ora[oranum]x;lst[x]oranum;return

void

main(){//freopen(test.in,r,stdin);//freopen(test.out,w,stdout);int

i,j,k,m,n,s;scanf(%d,n);for(i1;in;i){int

u,v;scanf(%d%d,u,v);color[i]u;if(v0){

si;

}addedge(v,i);}bjdfs(s);lensqrt(oranum);int

blktot0;for(i1;ioranum;i){if((i-1)%len0)

blk[blktot].ri;}blk[blktot].roranum;int

qsnum0;for(i1;in;i){q[qsnum].lfst[i];q[qsnum].rlst[i];}sort(q1,qn1,cmp);memset(cnt,0,sizeof(cnt));memset(last,0,sizeof(last));int

lz1,rz0;top0;int

get_devi(q[y].l)get_devi(q[x].l))

y;int

rightblk[get_devi(q[x].l)].r;while(xy

q[x].rright){int

lq[x].l,rq[x].r;for(jl;jr;j){add(color[ora[j]]);last[top]color[ora[j]];}int

flag1,asnumcnt[last[top]];top--;while(top0){if(cnt[last[top]]!asnum){flag0;break;}top--;}top0;if(flag1)ans;for(jl;jr;j)

lq[x].l,rq[x].r,sign;while(rzr){add(color[ora[rz]]);last[top]color[ora[rz]];}signtop;while(lzl){add(color[ora[--lz]]);last[top]color[ora[lz]];}int

ttoptop,asnumcnt[last[ttop]];ttop--;

int

flag1;while(ttop0){if(cnt[last[ttop]]!asnum){flag0;break;}ttop--;}if(flag1)

del(color[ora[lz]]);x;}top0;memset(cnt,0,sizeof(cnt));}printf(%d\n,ans);return