网站托管服务内容,泉州疾控中心发布最新消息,网页设计最重要的是什么,阿里巴巴国际站运营培训D. Cut and Stick
#xff08;赛后补题#xff09;借本题学习莫队算法以及区间众数的求法
题意#xff1a;对于整型数组#xff0c;每次询问[L,R][L,R][L,R]区间问最少分为多少个子序列#xff0c;使得每个子序列的众数xxx的个数cntxcnt_xcntx不大于 ⌈len2⌉\left \l…D. Cut and Stick
赛后补题借本题学习莫队算法以及区间众数的求法
题意对于整型数组每次询问[L,R][L,R][L,R]区间问最少分为多少个子序列使得每个子序列的众数xxx的个数cntxcnt_xcntx不大于 ⌈len2⌉\left \lceil \frac{len}{2} \right \rceil⌈2len⌉lenlenlen表示子序列的长度
思路对于每次询问只需知道询问区间内的众数xxx的个数即可最优解即为将其余的非众数尽可能与更多的xxx组合为一个子序列而剩下的xxx每个自为一个子序列 给一个不严格的证明图中有aaa个众数与bbb个非众数法①将全部的非众数放在同一个子序列中此时该子序列最多匹配b1b1b1个众数而剩余的众数则需单独出现法②将b个非众数分为两部分cdbcdbcdb两部分分别匹配c1c1c1和d1d1d1个众数c1d1cd2b2c1d1 cd2 b2c1d1cd2b2此时比法①多匹配了一个众数然而由于被分为两部分自然地也多产生了一个子序列因此两者是等效的可见只要将尽可能多的众数匹配给非众数无论非众数分为多少块其效果是等效的
因此问题便转化为求区间众数的个数问题。 数组长度nnn询问次数mmm 若采用暴力求解每次询问计算众数的个数的时间复杂度为O(n)O(n)O(n)总时间复杂度为O(m∗n)O(m*n)O(m∗n)会超时 采用莫队算法优化可将每次询问的平均时间复杂度降为O(n)O(\sqrt{n})O(n)
莫队步骤
将数组分为大小为n\sqrt{n}n的块将询问顺序按下面的规则排序 首先按照LLL所在的块号排序块号越小越靠前升序 若LLL所在的块号相同则按RRR所在的块号升序接着定义两个函数add()add()add()和del()del()del()分别用于添加和删除元素用于在上一个询问的区间基础上增删元素得到当前询问的区间每次调用增删函数的关键是动态地更新众数的状态
维护众数状态 采用mapmapmap映射存储每个数出现的次数采用数组aaa记录有多少个数出现了iii次当前的众数的个数即为数组a[i]0a[i]0a[i]0的最大的iii每次增删实时更新两者的数据即可
#includebits/stdc.h
#define debug1(x) cout#x:xendl
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N (int)3e5100;
const int RN sqrt(N)10;
const int MOD 10000;
using namespace std;
int a[N];
mapint,int mp[RN];
int n,m,block;
int cnt[N],sum[N],ans[N],max_cnt 0;
struct query
{int id;int l;int r;
}q[N];bool cmp(query a, query b)
{int al a.l / block, bl b.l / block;int ar a.r / block, br b.r / block;if(al ! bl) return al bl;return ar br;
}void add(int e)
{sum[cnt[e]]--;cnt[e];sum[cnt[e]];max_cnt max(max_cnt, cnt[e]);
}void del(int e)
{sum[cnt[e]]--;if(cnt[e] max_cnt sum[cnt[e]] 0) max_cnt--;cnt[e]--;sum[cnt[e]];
}int main()
{cinnm;block sqrt(n);for(int i 1; i n; i) scanf(%d,a[i]);int l, r;for(int i 0; i m; i){scanf(%d%d,l,r);q[i].id i;q[i].l l;q[i].r r;}sort(q, q m, cmp);int cl, cr, width;cl cr 0; add(a[0]);for(int i 0; i m; i){l q[i].l, r q[i].r;while(cr r) add(a[cr]);while(cl l) add(a[--cl]);while(cr r) del(a[cr--]);while(cl l) del(a[cl]);width r - l 1;ans[q[i].id] max(2 * max_cnt - width, 1);}for(int i 0; i m; i) printf(%d\n, ans[i]);return 0;
}
