差分训练题

P10903 [蓝桥杯 2024 省 C] 商品库存管理

题目描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，对于每个操作，如果不执行该操作而执行其它操作，库存量为 0 的商品的种类数。

输入格式

输入的第一行包含两个整数 n 和 m，分别表示商品的种类数和操作的个数。

接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作涉及的商品区间。

输出格式

输出 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

输入输出样例

输入 #1复制

5 3
1 2
2 4
3 5

输出 #1复制

1
0
1

说明/提示

【样例说明】

考虑不执行每个操作时，其余操作对商品库存的综合影响：

• 不执行操作 1：剩余的操作是操作 2（影响区间 [2,4]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [0,1,2,2,1]。在这种情况下，只有编号为 1 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。
• 不执行操作 2：剩余的操作是操作 1（影响区间 [1,2]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [1,1,1,1,1]。在这种情况下，所有商品的库存量都不为 0。因此，库存量为 0 的商品种类数为 0。
• 不执行操作 3：剩余的操作是操作 1（影响区间 [1,2]）和操作 2（影响区间 [2,4]）。执行这两个操作后，商品库存序列变为 [1,2,1,1,0]。在这种情况下，只有编号为 5 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。

【评测用例规模与约定】

对于 20% 的评测用例，1≤n,m≤5×103，1≤L≤R≤n。 对于所有评测用例，1≤n,m≤3×105，1≤L≤R≤n。

思路都在代码里了

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+20; 
int n,m;
int a[N],l[N],r[N],zero[N],one[N];
//a[N]是原数组,l[N]是左边界的数组记录所有l，r[N]是右边界的数组记录所以r
//zero[N]是记录没有被增加库存的数组
//one[N]是记录只被增加到库存为1的数组 
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i];
		a[l[i]]++,a[r[i]+1]--;
	}
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+a[i];//对原数组进行前缀和处理
		
		if(a[i]==0) zero[i]++;//求出没有被增加1的商品编号 
		if(a[i]==1) one[i]++;//求出库存只增加到1的商品编号
		//分别对这两个数组进行前缀和 
		zero[i]+=zero[i-1];
		one[i]+=one[i-1]; 
	}
	for(int i=1;i<=m;i++){
		cout<<zero[l[i]-1]+(zero[n]-zero[r[i]])+one[r[i]]-one[l[i]-1]<<endl; 
	}
	return 0;
}

P12716 [Algo Beat Contest 002 C] Counting Square Numbers

题目描述

wtr1 和 wqh 是一对好朋友。

wqh 给了 wtr1 一个长度为 n 的数组 A。对于 i=1,2,…,n，需要 wtr1 给出包含了位置 i 且区间和为完全平方数的子数组个数。由于最近 wtr1 很忙，请聪明的你帮帮他吧！

若一个数是一个整数的平方，则称这个数是完全平方数。

原数组中某段下标连续的元素按原顺序构成的数组称为子数组。

输入格式

第一行输入一个正整数 n，表示数组 A 的长度。

第二行输入 n 个整数 A1​,…,An​，表示 A 中的元素。

输出格式

输出 n 行，每行包含一个非负整数，表示符合条件的区间数。

输入输出样例

输入 #1复制

5
1 2 3 4 5

输出 #1复制

1
1
1
3
1

说明/提示

【样例解释 #1】

包含位置 2 的区间和为完全平方数是 2+3+4=9，只有 1 个。

包含位置 4 的区间和为完全平方数是 2+3+4=9，4+5=9 以及 4 本身，共 3 个。

【数据范围】

• 1≤n≤5×103。
• 0≤ai​≤109。

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
long long a[N],sum[N],b[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//求数组a的前缀和 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			long long s=sum[i]-sum[j-1];//枚举所有区间和
			long long root=sqrt(s);
			//该区间满足的话，就对这个区间进行差分 
			if(root*root==s){
				b[i+1]--,b[j]++;
			} 
		}
	}
	for(int i=1;i<=n;i++){
		b[i]=b[i-1]+b[i];
		cout<<b[i]<<endl;
	}
	return 0;
	
}

P7404 [JOI 2021 Final] 有趣的家庭菜园 4 / Growing Vegetables is Fun 4

题目描述

给定一个长为 N 的序列 A，你可以进行若干次操作：

• 选定一个区间 [L,R]，让这个区间里的数加 1。

设经过这若干次操作后的序列为 B，那么你需要让 B 满足下面这个要求：

• 存在一个整数 k∈[1,N]，满足对于子序列 A1​={B1​,B2​,⋯,Bk​} 为严格递增序列，对于子序列 A2​={Bk​,Bk+1​,⋯,BN​} 为严格递减序列。

你想知道最少需要多少次操作才能满足上面这个要求。

输入格式

第一行一个整数 N 代表序列长度。

第二行 N 个整数，代表序列 A。

输出格式

一行一个整数代表最小操作次数。

输入输出样例

输入 #1复制

5
3 2 2 3 1

输出 #1复制

3

输入 #2复制

5
9 7 5 3 1

输出 #2复制

0

输入 #3复制

2
2021 2021

输出 #3复制

1

输入 #4复制

8
12 2 34 85 4 91 29 85

输出 #4复制

93

说明/提示

样例 1 解释

• 对 [2,5] 进行操作，序列变为 {3,3,3,4,2}。
• 对 [2,3] 进行操作，序列变为 {3,4,4,4,2}。
• 对 [3,3] 进行操作，序列变为 {3,4,5,4,2}。

样例 2 解释

序列已经满足要求，不需要操作。

样例 3 解释

对区间 [1,1] 或 [2,2] 进行操作都可。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（40 pts）：N≤2000。
• Subtask 2（60 pts）：无特殊限制。

对于 100% 的数据，1≤N≤2×105，1≤Ai​≤109。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long a[N],b[N];
long long up[N],down[N];
int main(){
    int n; 
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    //注意一个是i一个是j 
    for(int i=2,j=n;i<=n;i++,j--){
    	
        up[i]=(b[i]<=0?up[i-1]-(b[i]-1):up[i-1]);
        
        down[j]=(b[j]>=0?down[j+1]+(b[j]+1):down[j+1]);
    }
    
    long long ans=0x3f3f3f3f3f3f3f3f; 
    for(int i=1;i<=n;i++){
		  ans=min(ans,max(up[i],down[i+1]));
	}
      
    cout<<ans;
    
    return 0;
}