网站开发 深圳,做网站都可以做什么,群晖怎样做网站,做网站找模板去哪好文章目录问题引入介绍莫队算法及其实现过程时间复杂度莫队算法适用范围莫队奇偶优化普通莫队#xff1a;小B的询问树上莫队#xff1a;SP10707 COT2 - Count on a tree II回滚莫队#xff1a;[PA2011]Kangaroosupd#xff1a;2021-08-11#xff1a;重新对博客进行了外观美…
文章目录问题引入介绍莫队算法及其实现过程时间复杂度莫队算法适用范围莫队奇偶优化普通莫队小B的询问树上莫队SP10707 COT2 - Count on a tree II回滚莫队[PA2011]Kangaroosupd2021-08-11重新对博客进行了外观美化修正以及新增树上莫队 upd2021-08-19新增回滚莫队
问题引入
给定一个大小为NNN的数组数组中所有元素的大小≤N\le N≤N。你需要回答MMM个查询。 每个查询的形式是L,RL,RL,R。你需要回答在范围[L,R][L,R][L,R]中至少重复222次的数字的个数 如果按照以往的想法就会是O(n2)O(n^2)O(n2)的暴力枚举
for ( int i 1;i Q;i ) {scanf ( %d %d, l, r );for ( int j l;j r;j ) {count[a[j]] ;if ( count[a[j]] 3 )result ;}}就算加一些优化用l,rl,rl,r采取指针转移但总归上还是在[1,n][1,n][1,n]区间内进行移动
最坏多半也是逼近于O(n2)O(n^2)O(n2)
void add ( int x ) {count[a[x]] ;if ( count[a[x]] 3 )result ;
}
void removed ( int x ) {count[a[x]] --;if ( count[a[x]] 2 )result --;
}
for ( int i 1;i m;i ) {scanf ( %d %d, l, r );while ( curl l )removed ( curl );while ( curl l )add ( -- curl );while ( curr r )removed ( curr -- );while ( curr r )add ( curr );printf ( %d\n, result );
}add 添加该位置的元素到当前集合内并且更新答案
remove 从当前集合内删除该位置的元素并更新答案 那么这个时候莫队算法就重磅登场了 为什么叫做莫队算法呢
据说算法是由之前的国家队队长莫涛发明的他的队友平日里称他为莫队所以称之为莫队算法 介绍莫队算法及其实现过程
莫队算法就是一个离线算法仅仅调整了处理查询的顺序
实现过程如下 将给定的输入数组分为n\sqrt{n}n块。每一块的大小为 nn\frac{n}{\sqrt{n}}nn 每个LLL落入其中的一块每个RRR也落入其中的一块 如果某查询的LLL落在第iii块中则该查询属于第iii块 所有的询问首先按照所在块的编号升序排列所在块的编号是指询问的L属于的块 如果编号相同则按R值升序排列 莫队算法将依次处理第111块中的查询然后处理第222块.........直到最后一块 有很多的查询属于同一块
e.g.
假设我们有333个大小为333的块(0−2,3−5,6−8)(0-2,3-5,6-8)(0−2,3−5,6−8) {0,3}{1,7}{2,8}{7,8}{4,8}{4,4}{1,2}\{0,3\} \{1, 7\} \{2, 8\} \{7, 8\} \{4, 8\} \{4, 4\} \{1, 2\}{0,3}{1,7}{2,8}{7,8}{4,8}{4,4}{1,2}
先根据所在块的编号重新排列它们
第111块{0,3}{1,7}{2,8}{1,2}\{0, 3\} \{1, 7\} \{2, 8\} \{1, 2\}{0,3}{1,7}{2,8}{1,2}第222块{4,8}{4,4}\{4, 8\} \{4, 4\}{4,8}{4,4}第333块{7,8}\{7, 8\}{7,8}
接下来按照R的值重新排列
第一块{1,2}{0,3}{1,7}{2,8}\{1, 2\} \{0, 3\} \{1, 7\} \{2, 8\}{1,2}{0,3}{1,7}{2,8}第二块{4,4}{4,8}\{4, 4\} \{4, 8\}{4,4}{4,8}第三块 {7,8}\{7, 8\}{7,8}
上述过程只是重新排列了查询的顺序 时间复杂度
我们说了这么多选用莫队算法无非就是想把时间复杂度给降下来
接下来我们来看看真正莫队的时间复杂度是多少其实我看了很多博客也是有点懵逼
上面的代码就是起一个铺垫作用所有查询的复杂性是由444个while循环决定的
前222个while循环可以理解为左指针curl的移动总量
后222个 while循环可以理解为右指针curr的移动总量
这两者的和将是总复杂性 先算右指针
对于每个块查询是递增的顺序排序所以右指针curr按照递增的顺序移动
在下一个块的开始时指针可能在最右端将移动到下一个块中的最小的RRR处
又可以从本块最左端移动到最右端
这意味着对于一个给定的块右指针移动的量是O(n)O(n)O(n)curr可以从111跑到最后的nnn
我们有O(n)O(\sqrt{n})O(n)块所以总共是O(nn)O(n\sqrt{n})O(nn) 接下来看看左指针怎样移动
对于每个块所有查询的左指针落在同一个块中从一个查询移动到下一个查询左指针会移动
但由于前一个LLL与下一个LLL在同一块中此移动是O(n)O(\sqrt{n})O(n)块的大小
在每一块中左指针的移动总量是O(Qn)O(Q\sqrt{n})O(Qn)(QQQ是落在那个块的查询的数量)
对于所有的块总的复杂度为O(m∗n)O(m∗\sqrt{n})O(m∗n) 综上总复杂度为O((nm)∗n)O(n∗n)O((nm)∗\sqrt{n})O(n∗\sqrt n)O((nm)∗n)O(n∗n)
实在无法理解就跳过吧如果有通俗易懂的解释欢迎评论)
莫队算法适用范围
首先莫队算法是一个离线算法所以如果问题是在线操作带修或者强制特殊的顺序
莫队就失去了它的效应 其次一个重要的限制性add和remove的操作
当有些题目的add和remove耗时很大O(N)O(\sqrt N)O(N)时就应该思考能否卡过
因为莫队本身就是一种优美的暴力而已
但是还是有很大一部分区间查询的题可以由莫队进行完成
莫队奇偶优化
sqt sqrt( n )
bool cmp( node x, node y ) {return ( x.l / sqt y.l / sqt ) ? ( ( ( x.l / sqt ) 1 ) ? x.r y.r : x.r y.r ) : x.l y.l;
}普通莫队小B的询问
小B有一个序列包含N个1~K之间的整数。他一共有M个询问 每个询问给定一个区间[L…R]求Sigma(c(i)^2)的值, 其中i的值从1到K其中c(i)表示数字i在[L…R]中的重复次数。 小B请你帮助他回答询问。
输入格式 第一行三个整数N、M、K。 第二行N个整数表示小B的序列。 接下来的M行每行两个整数L、R。 输出格式 M行每行一个整数其中第i行的整数表示第i个询问的答案。
输入输出样例 输入 6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 输出 6 9 5 2 说明/提示 对于全部的数据1N、M、K50000
简单题解
说了是算法模板入门题肯定不会把你拒之门外还是要让你摸摸门的
这个题就是要简单处理一下∑ci2∑c_i^2∑ci2当ci±1c_i±1ci±1时答案会发生怎样的转化
完全平方公式大家都会吧
(c[i]−1)2c[i]2−2∗c[i]1(c[i]-1)^2c[i]^2-2*c[i]1(c[i]−1)2c[i]2−2∗c[i]1
(c[i]1)2c[i]22∗c[i]1(c[i]1)^2c[i]^22*c[i]1(c[i]1)2c[i]22∗c[i]1
#include cmath
#include cstdio
#include algorithm
using namespace std;
#define LL l;ong long
#define MAXN 50005
struct node {int l, r, num;
}G[MAXN];
int n, m, k, apart, curl 1, curr;
int a[MAXN], cnt[MAXN];
LL result;
LL ans[MAXN];bool cmp ( node x, node y ) {return ( x.l / apart y.l / apart ) ? x.r y.r : x.l y.l;
}void add ( int x ) {result ( cnt[a[x]] 1 ) 1;cnt[a[x]] ;
}
void removed ( int x ) {result - ( cnt[a[x]] 1 ) - 1;cnt[a[x]] --;
}int main() {scanf ( %d %d %d, n, m, k );for ( int i 1;i n;i )scanf ( %d, a[i] );apart sqrt ( n );for ( int i 1;i m;i ) {scanf ( %d %d, G[i].l, G[i].r );G[i].num i;}sort ( G 1, G m 1, cmp );for ( int i 1;i m;i ) {int l G[i].l, r G[i].r;while ( curl l ) {removed ( curl );}while ( curl l ) {add ( -- curl );}while ( curr r ) {removed ( curr -- );}while ( curr r ) {add ( curr );}ans[G[i].num] result;}for ( int i 1;i m;i )printf ( %lld\n, ans[i] );return 0;
}树上莫队SP10707 COT2 - Count on a tree II
顾名思义就是把序列莫队搬到树上实现
分块的大小以及移动的操作与序列莫队无差别
唯一的区别就在于询问的l,r
在树上莫队询问的l,rl,rl,r要用欧拉序进行重新编号
e.g. 原图的欧拉序为1,2,4,6,6,7,7,5,5,4,2,3,3,1对于点iiili:l_i:li: 第一次访问iiiri:r_i:ri: 最后一次访问iii
树上莫队就是用欧拉序的li,ril_i,r_ili,ri代替访问的iii
对于查询的(u,v)有两种情况 是直系祖先关系假设uuu是vvv的祖先 e.g. : u2,v7u2,v7u2,v7拿出[lu,lv][l_u,l_v][lu,lv]代替u,vu,vu,v 欧拉序为2,4,6,6,7 不隶属同一棵子树假设lulvl_ul_vlulv e.g : u7,v3u7,v3u7,v3拿出[ru,lv][r_u,l_v][ru,lv] 欧拉序为7,5,5,4,2,3
不在路径上的点经过了恰好两次真正在路径上的点都恰好只出现一次对于不同子树的两点需要额外加上lca
source
#include cmath
#include cstdio
#include vector
#include algorithm
using namespace std;
#define maxn 40005
#define maxm 100005
vector int G[maxn];
int n, Q, B, cnt, ans;
bool vis[maxn];
int c[maxn], MS[maxn], tot[maxn], ret[maxm];
int dep[maxn], l[maxn], r[maxn], id[maxn 1];
int f[maxn][20];
struct node {int l, r, id, lca;
}q[maxm];void dfs( int u, int fa ) {dep[u] dep[fa] 1, l[u] cnt, id[cnt] u;for( int i 1;i 16;i )f[u][i] f[f[u][i - 1]][i - 1];for( auto v : G[u] ) {if( v fa ) continue;else f[v][0] u, dfs( v, u );}r[u] cnt, id[cnt] u;
}int get_lca( int u, int v ) {if( dep[u] dep[v] ) swap( u, v );for( int i 16;~ i;i -- )if( dep[f[u][i]] dep[v] ) u f[u][i];if( u v ) return u;for( int i 16;~ i;i -- )if( f[u][i] ! f[v][i] ) u f[u][i], v f[v][i];return f[u][0];
}void Delete( int x ) { if( -- tot[c[x]] 0 ) ans --; }void Insert( int x ) { if( tot[c[x]] 1 ) ans ; }void modify( int x ) { vis[x] ? Delete( x ) : Insert( x ); vis[x] ^ 1; }int main() {scanf( %d %d, n, Q );for( int i 1;i n;i )scanf( %d, c[i] ), MS[i] c[i];sort( MS 1, MS n 1 );int m unique( MS 1, MS n 1 ) - MS - 1;for( int i 1;i n;i )c[i] lower_bound( MS 1, MS m 1, c[i] ) - MS;B sqrt( n );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}dfs( 1, 0 );for( int i 1, u, v;i Q;i ) {scanf( %d %d, u, v );q[i].id i;if( l[u] l[v] ) swap( u, v );int lca get_lca( u, v );if( u lca ) q[i].l l[u], q[i].r l[v], q[i].lca 0;else q[i].l r[u], q[i].r l[v], q[i].lca lca;}sort( q 1, q Q 1, []( node x, node y ) { return ( x.l / B y.l / B ) ? ( x.r y.r ) : ( x.l y.l ); } );int curl 1, curr 0;for( int i 1;i Q;i ) {while( curl q[i].l ) modify( id[curl ] );while( q[i].l curl ) modify( id[-- curl] );while( curr q[i].r ) modify( id[ curr] );while( q[i].r curr ) modify( id[curr --] );if( q[i].lca ) modify( q[i].lca );ret[q[i].id] ans;if( q[i].lca ) modify( q[i].lca );}for( int i 1;i Q;i )printf( %d\n, ret[i] );
}回滚莫队[PA2011]Kangaroos
普通莫队是能做到快速增添和删减操作的
但有些题目在区间转移时可能会出现增加或者删除无法实现的问题
在只有增加不可实现或者只有删除不可实现的时候就可以使用回滚莫队
同样在O(nn)O(n\sqrt n)O(nn)的时间内解决问题
回滚莫队的核心思想就是既然只能实现一个操作那么就只使用一个操作剩下的交给回滚解决
回滚莫队分为只使用增加操作的回滚莫队和只使用删除操作的回滚莫队
以只使用添加操作的回滚莫队为例
首先仍是按照区间左端点分块排序然后右端点为第二关键字枚举区间左端点的块 对于询问的左右端点都在同一区间的直接暴力做将左端点都在该块的按右端点升序排序每次都是右端点右移加入答案左端点每次都回滚到这个块的末尾然后暴力的往前移到本次询问的左端点处记录这一路上的答案但是不像右端点一样是永久的 再回退到块末尾这样的时间复杂度mmm个询问每次询问左端点最多暴力移整个区间n\sqrt nn还是根号级别的复杂度 到下一块的时候l,rl,rl,r一起遍历了整个区间扔掉所有的标记那些然后手动重置为初始局面
只支持删除的话我想应该就是右端点rrr递减不断前移然后还是左端点lll在块中反复移动清空
可以看一下这道题→\rightarrow→ 回滚莫队的例题——历史研究
Kangaroos比较难一点
区间过大实际上区间相交只关系左右端点的大小关系所以先离散化区间的端点最多只有2n2n2n个
然后按询问左端点分块将询问挂到块上
接下来就是回滚莫队问题了
这道题主要是要维护最大连续区间
每次将新增区间的下标扔进去的时候更新
可以用线段树维护最大连续区间但是实际上可以用l[],r[]\rm l[],r[]l[],r[]数组来维护左右端点省去log\rm loglog
这只是简单口胡看不懂可以看代码代码里有详细注释
#include cmath
#include cstdio
#include vector
#include algorithm
using namespace std;
#define maxn 200005
#define maxB 320
struct node {int l, r, id;node(){}node( int L, int R, int ID ) {l L, r R, id ID;}
}t[maxn];
struct Node {int val, id;Node(){}Node( int Val, int ID ) {val Val, id ID;}
}x[maxn];
vector node q[maxB];
int n, m, ans, top;
int block[maxn], L[maxB], R[maxB], l[maxn], r[maxn], ret[maxn];bool operator ( Node s, Node t ) {return s.val t.val ? s.id t.id : s.val t.val;
}struct opt {//记录操作前的相关信息 方便回滚 //flag 0:左 1:右 记录被更改的是哪边 int flag, pos, lst, ans;opt(){}opt( int Flag, int Pos, int Lst, int Ans ) {flag Flag, pos Pos, lst Lst, ans Ans;}
}s[maxn 4];
//l[i]:在当前已加入区间中i区间所能连的最左边区间下标 - [l(i),i]的所有区间都与当前查询区间有交
//r[i]:在当前已加入区间中i区间所能连的最右边区间下标 - [i,r(i)]的所有区间都与当前查询区间有交
void add( int i ) {if( l[i] || r[i] ) return;//已经算过了i的贡献 if( ! l[i - 1] and ! r[i 1] ) {//左右的区间都还没有被加进来//只能自己这一个区间 长度为1 s[ top] opt( 0, i, l[i], ans );s[ top] opt( 1, i, r[i], ans );l[i] r[i] i, ans max( ans, 1 );}else if( ! l[i - 1] ) {//i1的区间被加入了 可以往左延伸和i接上 s[ top] opt( 0, r[i 1], l[r[i 1]], ans );s[ top] opt( 1, i, r[i], ans );r[i] r[i 1], l[r[i 1]] i;ans max( ans, r[i] - i 1 );}else if( ! r[i 1] ) {//i-1的区间被加入了 可以往右延伸和i接上 s[ top] opt( 1, l[i - 1], r[l[i - 1]], ans );s[ top] opt( 0, i, l[i], ans );l[i] l[i - 1], r[l[i - 1]] i;ans max( ans, i - l[i] 1 );}else {//i-1 i1都被加入 直接左右连接拼起来 s[ top] opt( 0, r[i 1], l[r[i 1]], ans );s[ top] opt( 1, l[i - 1], r[l[i - 1]], ans );s[ top] opt( 0, i, l[i], ans );s[ top] opt( 1, i, r[i], ans );//都连起来了 也没有i什么事了 所以随便记录i的一边l/r有值 下次就可以在第一个if语句直接return l[r[i 1]] l[i - 1], r[l[i - 1]] r[i 1], l[i] r[i] i;ans max( ans, r[i 1] - l[i - 1] 1 ); }
}void remove( int lst ) {while( top lst ) {if( ! s[top].flag ) l[s[top].pos] s[top].lst;else r[s[top].pos] s[top].lst;ans s[top --].ans; }
}void solve( int id ) {remove( 0 );//移动到新块 莫队里的东西清空 for( int i 1;i n;i ) if( t[i].l L[id] R[id] t[i].r )//完全覆盖该块且不在块内的区间一定会对块内所挂询问产生贡献 add( t[i].id );sort( q[id].begin(), q[id].end(), []( node x, node y ) { return x.r y.r; } );//将块内询问按照右端点排序 只增加的回滚莫队 int lst top;for( node now : q[id] ) //计算整个区间都在块内的询问的答案if( now.r R[id] ) continue;else {for( int i L[id];i R[id];i )if( now.l t[x[i].id].r t[x[i].id].l now.r )//与查询区间有交 可能会为答案贡献的区间 add( x[i].id );ret[now.id] ans;remove( lst ); }remove( 0 );int cur R[id];//处理r在其他块递增的询问 先把指针拨到块的最后for( int i 1;i n;i )if( t[i].l R[id] R[id] t[i].r )//一定会与后面的查询有交点 R[id]add( t[i].id );for( node now : q[id] )if( now.r R[id] ) continue;else {while( cur now.r ) add( x[ cur].id );lst top;for( int i R[id];i now.l;i -- )//回滚莫队 滚到当前询问的左端 add( x[i].id );ret[now.id] ans;remove( lst );//返回 回滚 抵消 }
}int main() {scanf( %d %d, n, m );for( int i 1, l, r;i n;i ) {scanf( %d %d, l, r );x[i] Node( l, i );x[i n] Node( r, i );t[i] node( l, r, i );}//为了块的大小能开出来 1e9首先要离散化 sort( x 1, x ( n 1 ) 1 );for( int i 1;i n;i ) {t[i].l lower_bound( x 1, x ( n 1 | 1 ), Node( t[i].l, 0 ) ) - x;t[i].r upper_bound( x 1, x ( n 1 | 1 ), Node( t[i].r, 1e9 ) ) - x - 1;}int N n 1;int B sqrt( N );for( int i 1;i N;i )block[i] ( i - 1 ) / B 1;//L,R 记录块的左右端点 for( int i N;i;i -- ) L[block[i]] i;for( int i 1;i N;i ) R[block[i]] i;for( int i 1, l, r;i m;i ) {scanf( %d %d, l, r );l lower_bound( x 1, x ( n 1 | 1 ), Node( l, 0 ) ) - x;r upper_bound( x 1, x ( n 1 | 1 ), Node( r, 1e9 ) ) - x - 1;q[block[l]].push_back( node( l, r, i ) );}for( int i 1;i block[N];i )if( ! q[i].empty() )solve( i );for( int i 1;i m;i )printf( %d\n, ret[i] );return 0;
}
