Prefix sum is an important preprocessing tool in the algorithm.

Okay, I can't make it up anymore, it seems I don't have any [doge]

Differential operations, which can be said to be the inverse of the sum of prefixes, are often used together with the prefix to solve some interval problems.

Recently, I also encountered a lot of difference problems, so I am ready to summarize one article. Here, we will focus on the prefixes and differences between one and two dimensions. Say nothing more.

Prefix and;

In one dimension, there's nothing to say.

Let's look at two dimensions:

Let's first look at the prefix and requirements for a point [2,3]:

As you can see, if we want to, we'll add the sum of all the points from [1,1] to [2,3];

The point is how we add it;

When we calculate the sum of [2,3] prefixes, [2,2] and [1,3] must have been calculated;

So what we can see is that the prefix sums of [2,2] and [1,3] are contained within [2,3] and contain [1,2] repeatedly

So: (s: prefix and array, a: original array)

Okay, I'm sure you've learned it.

Let's see how prefixes and intervals are needed. (For example, let's calculate the interval prefix of the Red Square and [6,4], [4,3])

We find the same, so cut off the extra chops;

But we found that the extra part [3,2] was cut twice during the cutting process, so we have to add this part in the end.

So

;

Okay, then we can do the whole thing;

 Territory Selection - Lo Valley

You don't have to explain this [doge]

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
typedef long long LL; 
int n,m,c;

int a[N][N];

LL s[N][N];
int main()
{
	
	cin>>n>>m>>c;
	for(int i =1 ;i <= n;i ++)
		for(int j =1 ;j <=m ;j ++)
			cin>>a[i][j];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			s[i][j] = s[i-1][j] + s[i][j-1]- s[i-1][j-1] + a[i][j];
	
	LL res = -1e8;
	int x,y;
	for(int i =1 ;i <= n -c + 1 ;i ++)
		for(int j = 1 ;j <= m -c + 1 ;j ++)
		{
			int x1,y1,x2,y2;
			x1= i;
			y1 = j;
			x2 = i + c -1;
			y2 = j + c -1;
			
			LL mx = s[x2][y2]- s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
			if(mx > res)
			{
				res = mx;
				x = i,y = j;
			}
		}
	cout<<x<<" "<<y<<endl; 
	return 0;
}

Difference;

Reverse the process; a[i] -= a[i-1];

So if we want to get the original array, we just need a[i] += a[i-1] (prefix and);

As mentioned above, the most common use of difference is to maintain an interval so that each operation contributes the same amount to that interval.

The saying is: add a value to the number in this area;

Look directly at the picture;

How do we want to add 1 to [3,5]?

If we consider the values of prefix and, prefix and the first number in the middle, we will make a contribution to all subsequent numbers. Then we add 1 to 3, which will make a contribution to all subsequent numbers 1, but I just want to add 5, that is, we don't want to add the contribution to 6, so we can subtract 1 from 6. This contribution does not contribute to subsequent numbers from 6 onwards.

 

We do the same;

We want to add 1 to [4,3]-- [4,6];

Adding 1 to [4,3] will contribute to all points in the lower right corner of that point;

So we subtract contributions from other parts;

We add -1 to [4,5] so that the gray box is not contributed by [4,3] plus 1; The addition of -1 to [7,3] results in the dark red box not being contributed by [4,3] plus 1;

However, there is overlap, and we subtract a little more, so we add one on [7,5] to add the extra subtraction back;

Let's talk about the whole difference.

Submarine High-Speed Rail-Lough Valley

#include<bits/stdc++.h>
using namespace std;

const int N  = 100010;
typedef long long LL;


LL n,m;
queue<int> p;

LL a[N],b[N],c[N];

LL s[N];
LL res;
int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i =1;i <= m;i ++)
	{
		int c;
		scanf("%d",&c);
		p.push(c);
	} 
	
	for(int i =1;i <= n - 1 ;i ++)	scanf("%d%d%d",&a[i],&b[i],&c[i]);
		
	int st,ed;
	st = p.front(),p.pop();
	while(!p.empty())
	{
		ed = p.front(), p.pop();
		
		if(st > ed)
		{
			s[ed] ++;
			s[st] --;	
		} 
		else 
		{
			s[st] ++;
			s[ed] --;
		}
		st = ed;
	}
	
	for(int i =1 ;i <= n - 1 ;i ++) s[i] += s[i - 1];
	
	
	for(int i =1 ;i <= n-1 ; i ++)
	{
		if(s[i] * a[i] > s[i]* b[i] + c[i]) res += s[i]* b[i] + c[i];
		else res += s[i] * a[i];
	}
	
	printf("%lld\n",res);
	return 0;
} 

Close your work;