题解 P4231 【三步必杀】

· · 题解

Luogu P4231 题解

我们可以把这道题的差分看成一个两个数组,分别是 c[i]与d[i],c[i]表示加多少,d[i]表示等差序列加多少. 等差序列每次加(e-s)/(r-l)

我们来用样例模拟一下:

5 2
1 5 2 10
2 4 1 1

输入完第2行后的数组:

d数组:0 (10-2)/(5-1) 0 0 0 (-2)
c数组:2 0 0 0 0 (-10)

输入完第3行后的数组:

d数组:0 2 0 0 0 (-2)
c数组:2 0 1 0 -1 (-10)

我们进行从1—n的循环.

用一个sum表示此时的柱子受到的伤害,用g表示下一个数 因 等差序列加g.

就推出了 g=g+d[i]; sum=sum+g+c[i];

然后,这道题就做完了...

放上ac代码:

#include <iostream>

using namespace std;

long long n,m,c[10000005],d[10000005];

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int l,r,s,e;
    scanf("%d%d%d%d",&l,&r,&s,&e);
    int dc=(e-s)/(r-l);
    d[l+1]=d[l+1]+dc;
    d[r+1]=d[r+1]-dc;
    c[l]=c[l]+s;
    c[r+1]=c[r+1]-e;
  }
  long long g=0,sum=0;
  long long ansa=0,ansb=0;
  for(int i=1;i<=n;i++)
  {
    g=g+d[i];
    sum=sum+g+c[i];
    ansb=max(ansb,sum);
    ansa=ansa^sum;
  }
  cout<<ansa<<" "<<ansb;
  return 0;
}