题解：P4231 三步必杀

wjr_jok · 2024-05-10 17:32:12 · 题解

题意

给你一个长度为 n 的数列，要对它进行 m 次操作，每次将 l \sim r 的区间加上一个首项为 s，末项为 e 的等差数列，最后要你输出这个数列每个数的值。

思路

差分，不同的是只用差分一次，用到一个结构体数组 cf，成员 x 记录首项，成员 y 记录公差，对于每一次操作 x y s e，将 cf_{x_x} 加上 s，cf_{x_y} 加上 e，cf_{y+1_x} 减去 s，cf_{y_y} 减去 e。

对一个区间加上一个等差数列，所做的贡献从 l 开始依次是 s，s + e，s + e \times 2 \dots 所以对于求解前缀和的过程我们只需单独考虑首项带来的初始贡献，然后在这个等差数列所影响的范围内每次再将答案加上公差 e 即可求出实际值，正确性显然。

遍历数组时用到两个变量 cnt，jl，分别记录总值和公差（每次加上的数），当遍历到 i 时，将 cnt 加上 cf_{i_x}+jl，jl 加上 cf_{i_y}，此时 cnt 即时数列第 i 位的值。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
void write(int n){
    if(n<0) putchar('-'),n*=-1;
    if(n>9) write(n/10);
    putchar(n % 10 + '0');
}
struct jgt{
    int x;
    int y;
} cf[10000001];
int n,m,x,y,s,e,cnt,jl,ans,maxx;
int xl[10000001];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        x=read(),y=read(),s=read(),e=read();
        e=(e-s)/(y-x);//通过首项，末项求出公差
        cf[x].x+=s;
        cf[x].y+=e;
      //从x开始加上首项，公差
        cf[y+1].x-=s+e*(y-x);
        cf[y].y-=e;
      //从y开始减去首项，公差
    }
    for(int i=1;i<=n;i++){
        cnt+=cf[i].x+jl;//相当于是加上从这里开始的等差数列的首项以及前面数组所产生的贡献
        ans^=xl[i]+cnt;
        maxx=max(maxx,xl[i]+cnt);
        jl+=cf[i].y;//更新公差所带来的贡献
    }
    cout<<ans<<" "<<maxx;
    return 0;
}