牛客小白月赛5 -- 区间 (interval)(暴力？差分？)

题目链接：https://www.nowcoder.com/acm/contest/135/I

题目描述

Apojacsleam喜欢数组。

他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：

操作一：将a[L]-a[R]内的元素都加上P

操作二：将a[L]-a[R]内的元素都减去P

最后询问a[l]-a[r]内的元素之和？

请认真看题干及输入描述。

输入描述:

输入共M+3行：

第一行两个数，n，M，意义如“题目描述”

第二行n个数，描述数组。

第3-M+2行，共M行，每行四个数，q，L，R，P，若q为1则表示执行操作2，否则为执行操作1

第4行，两个正整数l，r

输出描述:

一个正整数，为a[l]-a[r]内的元素之和

示例1

输入

复制

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5 5
1 2 3 6
0 2 5 5 
0 2 5 8
1 4 9 6
2 7

输出

复制

说明

思路1：只把需要求的那个区间里的数进行加减操作，例如该样例是求2 ~ 7 之间的和，先把2 ~ 7 之间的a[i]求和sum，再根据询问的那些区间里找重合的部分乘以 p 加上sum即可

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000+7;
int  a[maxn];
struct node
{
	int q,l,r,p;
}s[maxn];
int main()
{
	int n , m , l , r , p , q , L , R;
	long long int sum = 0;
	scanf("%d %d" , &n , &m);
	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d" , &a[i]);
	 } 
	for(int i = 1 ; i <= m ; i++)
	 {
	 	scanf("%d %d %d %d" , &s[i].q , &s[i].l , &s[i].r , &s[i].p);
	 	if(s[i].q == 1)s[i].p = -s[i].p;
	 }
	 
	scanf("%d %d" , &L , &R);
//	printf("0000000\n");
	for(int i = L ; i <= R ; i++)
	{
		sum += a[i];
	 } 
//	 printf("sum = %lld\n" , sum);
	 for(int i = 1 ; i <= m ; i++)
	 {
	 	if(s[i].l >= L && s[i].r <= R)
	 	{
	 		sum += (s[i].r-s[i].l+1)*s[i].p;
		 }
		 if(s[i].l >= L && s[i].r > R)
		 {
		 	sum +=(R - s[i].l+1)*s[i].p;
		 }
		 if(s[i].l < L && s[i].r <= R)
		 {
		 	sum += (s[i].r-L+1)*s[i].p;
		 }
		 if(s[i].l < L && s[i].r > R)
		 {
		 	sum += (R - L+1) * s[i].p;
		 }
	 }
	 cout << sum << endl;
	return 0;
}
/*
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5 5
1 2 3 6
0 2 5 5 
0 2 5 8
1 4 9 6
2 7
*/

思路2：

可以手推一下这样一个样例

求这个点的上包含的线数，比如：a[1] = 1 ; a[2] = 2 ; a[3] = 2 ; a[4] = 2 ; a[5] = 1;a[6] = 1 ; a[7] = 1 ; a[8] = 1;

1 ~ 5 , 2 ~ 4 , 6 ~ 8;

a[1] += 1; a[5+1] = a[6] -= 1

a[2] += 1 a[4 + 1] = a[5] -= 1

a[6] += 1 a[8+1] = a[9] -= 1

这样操作以后， a[1] = 1 -----bingo

a[2] = a[2] + a[1] = 1 + 1 = 2 ------bingo

a[3] = a[3] + a[2] = 0 + 2 = 2-----binggo

a[4] = a[4] + a[3] = 0 + 2 = 2 ----bingo

a[5] = a[5] + a[4] = -1 + 2 = 1-----bingo

....................................

那如果有加p的话就把那个加 1 改成加 p 就好啦。

#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn = 1000000+6;
long long int add[maxn] , a[maxn];
int main()
{
	int n , m , l , r , q , p , L , R;
	while(~scanf("%d %d" , &n , &m))
	{
		for(int i = 1 ; i <= n ; i++)
		{
			scanf("%d" , &a[i]);
		}
		while(m--)
		{
			scanf("%d %d %d %d" , &q , &l ,&r , &p);
			if(q == 1) p = -p;
			add[l] += p;
			add[r+1] -= p;
		}
		scanf("%d %d" , &L , &R);
		for(int i = 1 ; i <= n ; i++)
		{
			add[i] += add[i-1];
			a[i] = a[i]+a[i-1]+add[i];
		}
		printf("%lld\n" , a[R] - a[L-1]);
	}
	return 0;
}