首页 > 其他分享 >CF1514D Cut and Stick 题解

CF1514D Cut and Stick 题解

时间:2024-08-23 20:38:07浏览次数:11  
标签:cnt Cut CF1514D int 题解 sum long 众数 define

题目传送门

前置知识

可持久化线段树

解法

若区间内不存在绝对众数,直接保持这一段即可。

若存在绝对众数,贪心地想肯定要尽可能地把其分开还要限制出其他数使其不成为绝对众数。容易发现设绝对众数出现次数为 \(cnt\),取 \(cnt-1\) 个其他数和绝对众数配对最优。但可能其他数不够 \(cnt\) 个,就只能让多余的绝对众数各成一组了。最终答案即为 \(2cnt-(r-l+1)\)。

主席树求下是否存在绝对众数及其出现次数即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
int a[300010];
struct PDS_SMT
{
	int root[300010],rt_sum;
	struct SegmentTree
	{
		int ls,rs,sum;
	}tree[300010<<5];
	#define lson(rt) tree[rt].ls
	#define rson(rt) tree[rt].rs
	int build_rt()
	{
		rt_sum++;
		return rt_sum;
	}
	void build_tree(int &rt,int l,int r)
	{
		rt=build_rt();
		if(l==r)
		{
			return;
		}		
		int mid=(l+r)/2;
		build_tree(lson(rt),l,mid);
		build_tree(rson(rt),mid+1,r);
	}
	void update(int pre,int &rt,int l,int r,int pos)
	{
		rt=build_rt();
		tree[rt]=tree[pre];
		tree[rt].sum++;
		if(l==r)
		{
			return;
		}
		int mid=(l+r)/2;
		if(pos<=mid)
		{
			update(lson(pre),lson(rt),l,mid,pos);
		}
		else
		{
			update(rson(pre),rson(rt),mid+1,r,pos);
		}
	}
	int query(int rt1,int rt2,int l,int r,int k)
	{
		if(l==r)
		{
			return tree[rt2].sum-tree[rt1].sum;
		}
		int mid=(l+r)/2;
		if(tree[lson(rt2)].sum-tree[lson(rt1)].sum>k)
		{
			return query(lson(rt1),lson(rt2),l,mid,k);
		}
		if(tree[rson(rt2)].sum-tree[rson(rt1)].sum>k)
		{
			return query(rson(rt1),rson(rt2),mid+1,r,k);
		}
		return 0;
	}
}T;
int main()
{
	int n,m,l,r,cnt,i;
	scanf("%d%d",&n,&m);
	T.build_tree(T.root[0],1,n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		T.update(T.root[i-1],T.root[i],1,n,a[i]);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		cnt=T.query(T.root[l-1],T.root[r],1,n,(r-l+1)/2.0);
		if(cnt==0)
		{
			printf("1\n");
		}
		else
		{
			printf("%d\n",2*cnt-(r-l+1));
		}
	}
	return 0;
}

标签:cnt,Cut,CF1514D,int,题解,sum,long,众数,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18377052

相关文章

  • 题解:P10906 [蓝桥杯 2024 国 B] 合法密码
    本来以为字符串多大,结果就这点,直接暴力。枚举起始点,对于每个起始点枚举后面\(8\sim16\)位有没有能用的即可。最后答案为\(400\)。附:计算代码枚举代码如下:for(inti=0;i<n;++i){for(intlength=8;length<=16;++length){if(i......
  • 题解:P10903 [蓝桥杯 2024 省 C] 商品库存管理
    题目大意有一个初始化为\(0\)的长度为\(n\)的序列,现有\(m\)个操作,每次将区间\([L,R]\)中的数量加\(1\),求如果不做某个操作将会有多少个数量为\(0\)的量。解题思路当看见这句话时就想到了差分,这题我们可以使用差分先处理将所有的操作执行后的数组,然后在算出如果减......
  • P10404 「XSOI-R1」原神数 题解
    一篇题解需要一张头图。容易发现超过十位的数都不是原神数,因为只有十个数字,不可能保证十一个位置互不相同。同时恰好十位的数也不可能是原神数,因为数位互不相同的十位数的数位和为\(45\),被\(3\)整除,一定是\(3\)的倍数。于是把原神数的范围缩小到\([1,10^9)\)。显然不......
  • P10528 [XJTUPC2024] 崩坏:星穹铁道 题解
    求方案数,分多种情况,不难想到DP。设\(dp_{i,j}\)表示已经行动\(i\)次,剩余战技点个数为\(j\)的方案数,容易得到以下转移方程。\(a_i=1\)时,有\[dp_{i,j}=\begin{cases}0,&j=0,\\dp_{i-1,j-1},&1\leqslantj\leqslant4,\\dp_{i-1,j-1}+dp_{i......
  • LGP10702 [SNCPC2024] 下棋题解
    P10702[SNCPC2024]下棋本蒟蒻的第一篇题解定位博弈论(nim)+进制转换相关知识OIWIKI博弈论NIM进制转换正题读题所有k进制下所有数位的乘积为自身因子的数。他称之为LNC数。给出x枚棋子,然后LNC选定一个整数k(k≥2)。随后他们交替取走若干枚棋子,要求取走的棋......
  • dracut
    Dracut是一个用于生成Linuxinitramfs(初始内存文件系统)镜像的工具。Initramfs是在引导过程中加载的一个小型临时文件系统,用于启动Linux内核并准备实际的根文件系统。Dracut的作用生成initramfs:Dracut可以根据系统的实际需要生成一个精简的initramfs。与早期的mkini......
  • 【题解】Solution Set - NOIP2024集训Day14 CDQ分治
    【题解】SolutionSet-NOIP2024集训Day14CDQ分治https://www.becoder.com.cn/contest/5482「CF364E」EmptyRectangles*3000摆烂了。「SDOI2011」拦截导弹CDQ的例题,之前做过(现在试图自己再做出来。第二问只用在第一问里面记录每一次是从哪个\(j\)​转移过来的,以及......
  • P10559 [ICPC2024 Xi'an I] The Last Cumulonimbus Cloud 题解
    这种题有一个常见的根号分治做法:设\(d\)为度数,显然有\(O(1)\)修改单点,\(O(d)\)查询邻域和\(O(d)\)修改邻域,\(O(1)\)查询单点两种暴力。对度数大于\(\sqrtn\)的点使用前者,度数小于等于\(\sqrtn\)的点使用后者,可以做到\(O(m\sqrtn)\)的时间复杂度。这种做法的本......
  • CF1575G GCD Festival 题解
    考虑欧拉反演\[\sum\limits_{d\midn}\varphi(d)=n\]则原式可以化为\[\begin{align*}&\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(a_i,a_j)\cdot\gcd(i,j)\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(a_i,a_j)\sum\li......
  • CF163E e-Government 题解
    题目传送门前置知识AC自动机|树状数组解法一次性将所有模式串加入AC自动机,然后处理加入和删除,考虑单次操作对答案的贡献。因为模式串\(T\)在文本串\(S\)中出现的次数之和等价于\(T\)在\(S\)的所有前缀中作为后缀出现的次数之和。这就很和\(fail\)树上跳到根节......