首页 > 其他分享 >二分答案&前缀和&差分&离散化(简记)

二分答案&前缀和&差分&离散化(简记)

时间:2024-03-12 22:25:02浏览次数:26  
标签:code 前缀 int sum mid 差分 简记 ans

二分答案

基本code

int Find(int l,int r)
{
	int ans,mid;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(Check(mid)) ans=mid,r=mid-1;//舍弃右半部分
		else l=mid+1;//舍弃左半部分
	}
	return ans;
}

前缀和

基本code

#inlcude<bits/stdc++.h>
using namespace std;
int sum[100],a[100];
int _n;//基本个数
int main()
{
	for(int i=1;i<=_n;i++)
		cin>>a[i],sum[i]=sum[i-1]+a[i];
	ask_sum(l,r)=sum[r]-sum[l-1];//ask
	//一维公式
	for(int i=1;i<=_n;i++)
		for(int j=1;j<=_n;j++)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//build
	for(int a0=1;a0<=_n;a0++)
        for(int b0=1;b0<=_n;b0++)
            for(int a1=a0;a1<=_n;a1++)
                for(int b1=b0;b1<=_n;b1++)
                {
                    ask_sum([a0,b0],[a1,b1])=sum[a1][b1]-sum[a0-1][b1]-sum[a1][b0-1]+sum[a0-1][b0-1];
                }//ask
	return 0;
}

差分

基本code

d[]=>差分数列
	for(int i=1;i<=_n;i++)
	{
		cin>>a[i];
		d[i]=a[i]-a[i-1];
	}
统治区域值(l,r)+d
	d[l]+d;
	d[r+1]-d;
	for(int i=1;i<=_n;i++)
		sum[i]=sum[i-1]+a[i];//还原

离散化

标签:code,前缀,int,sum,mid,差分,简记,ans
From: https://www.cnblogs.com/happy-salted-fish/p/18069485

相关文章

  • 复合索引和最左前缀原则
    复合索引复合索引是根据多个列创建的数据库索引。它们对于优化涉及这些列的查询性能非常有用。在创建复合索引时,这些列的顺序至关重要,因为它决定了数据库如何利用该索引。列的顺序确定复合索引中列的顺序时,应考虑以下因素:查询模式:考虑哪些列经常一起出现在WHERE子句中。选择......
  • Linux之ps -ef进程命令及netstat网络状态命令简记
    ps-ef释义:ps-ef表示查看全格式的全部进程。ps是linux下最常用的也是非常强大的进程查看命令,常配合管道命令|和查找命令grep同时执行来查看特定进程。参数含义:-e显示所有进程。-f全格式。-h不显示标题。-l长格式。-w宽输出。a显示终端上的所有进程,包括其他用户的......
  • Mysql如何给字符串添加索引(前缀索引)
    在日常开发中,我们经常给字符串添加索引,那么给字段添加索引有什么技巧吗,我们看看下面的例子,我们给一个邮箱添加索引,应该如何添加呢看看下面这条sqlselect*fromuserwhereemail='[email protected]'如果我们不添加索引,肯定是要进行全表扫描的,那么我们如何添加呢有两种方式a......
  • 蓝桥杯算法集训 - Week1:二分、前缀和、差分算法
    蓝桥杯算法集训-Week1本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、二分查找二分算法原理复习参考:二分查找-Hello算法Ⅰ、二分模板boolcheck(intx){/*...*/}//检查x是否满足某种性质//区间[l,r]被划分......
  • 多因素方差分析
    多因素方差分析SPSS统计分析:多因素方差分析-数学中国方差分析-F检验根据因变量的数目,分为:一元多因素方差分析;多元多因素方差分析;方差分析AnalysisOfVariance,ANOVA单因素方差分析说明$y_i=\sum_{j=1}^{n}y_{ij}$—第$i$个水平(处理)观测值总和;$\bar{y}{i.}=y......
  • abc284F 前缀+逆序+后缀
    题面:给一个长度为2n的字符串T,问是否存在长度为n的字符串S,满足:T=S的前缀+整串S逆序+S的后缀。范围:n<=1e6思路:字符串哈希,枚举S的起点逐一判断,如果前i个字符加后n-i个字符组成的长为n的字符串,正好和中间串的逆序相同,则为解。#include<bits/stdc++.h>usingnamespacestd;......
  • labuladong_一/二维数组前缀和
    一维数组前缀和核心思路是我们new一个新的数组 preSum 出来,preSum[i] 记录 nums[0..i-1] 的累加和。看这个 preSum 数组,如果我想求索引区间 [1,4] 内的所有元素之和,就可以通过 preSum[5]-preSum[1] 得出。一维数组前缀和 ......
  • 1.Prefix前缀和【模板】
    [[#题目描述|题目描述]][[#输入描述|输入描述]][[#输出描述|输出描述]][[#输入样例1|输入样例1]][[#输出样例1|输出样例1]][[#暴力穷举|暴力穷举]][[#前缀和数组|前缀和数组]]题目描述给定义一个数组a,有q次询问,对于每次询问:给定两个整数l,r,求出${a_l}$$+$${a_{l+1}}$......
  • 2.diff差分【模板】
    [[#差分数组|差分数组]][[#差分数组#三个数组的关系|三个数组的关系]][[#题目描述|题目描述]][[#输入描述|输入描述]][[#输出描述|输出描述]][[#输入样例1|输入样例1]][[#输出样例1|输出样例1]]差分数组如下叫做差分数组\[d_{i}=a_{i}-a_{i-1}\]又有\[\su......
  • 前缀和
    记录10:072024-3-4目录1.前缀和1.一维前缀和2.二维前缀和1.前缀和1.一维前缀和数组A[x](下标从1开始)前缀和S[0]=0S[i]=S[i-1]+A[i]2.二维前缀和数组A[x][y](下标从1开始)前缀和S[i][j]表示以(i,j)为右下角的矩形中所有元素的和S[i][0]=S[0][j]=0S[i][......