1 solutions

  • 1
    @ 2025-9-9 20:04:31

    本人洛谷原题解:> https://www.luogu.com.cn/article/b463xc3v

    部分分:

    对于 Subtask 11:直接暴力即可。

    对于 Subtask 22an×sa_n \times s 即为答案。

    正解思路:

    本题频繁性对区间操作,很自然地我们会想到差分。

    不过这题用不用差分都差不多,只是用差分代码更简洁。

    由于最多有 2×1052 \times 10^5 天,所以计算每天的时间复杂度必须为 O(1)O(1)。我们可以想到:必须每次操作维护 ans\text{ans},而不是完全依赖于差分数组。

    对于每次操作的区间起点和终点:

    1. ans\text{ans} 减去风改变的值。
    2. 修改差分数组。
    3. ans\text{ans} 加上现在风改变的值。

    (如果终点小于 nn 可以不用处理终点)

    所以其实这里差分数组唯一作用就是用更简洁的语言代替 alal1a_l-a_{l-1}

    代码:

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int NR=200010;
    int a[NR];
    long long b[NR];
    int main()
    {
    	int n,q,s,t,i;
    	cin>>n>>q>>s>>t;
    	long long ans=0;
    	for(i=0;i<=n;i++)
    	{
    		cin>>a[i];
    		if(i!=0) b[i]=a[i]-a[i-1];
    		if(i!=0 && a[i]>a[i-1])	ans+=b[i]*(-s);
    		else if(i!=0 && a[i]<a[i-1]) ans+=-b[i]*t; 
    	}
    	while(q--)
    	{
    		int l,r,x;
    		cin>>l>>r>>x;
    		if(b[l]>0) ans-=b[l]*(-s);
    		else ans-=-b[l]*t;
    		b[l]+=x;
    		if(b[l]>0) ans+=b[l]*(-s);
    		else ans+=-b[l]*t;
    		if(r<n)
    		{
    			if(b[r+1]>0) ans-=b[r+1]*(-s);
    			else ans-=-b[r+1]*t;
    			b[r+1]-=x;
    			if(b[r+1]>0) ans+=b[r+1]*(-s);
    			else ans+=-b[r+1]*t;
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    

    注意事项:

    在这里:

    if(b[l]>0) ans-=b[l]*(-s);
    else ans-=-b[l]*t;
    b[l]+=x;
    

    b1b_1 可能一开始为正(即 al>al1a_l>a_{l-1}),但后面可能让 b1b_1 变为负,所以 ans\text{ans} 必须先减后加。

    • 1

    Information

    ID
    11621
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    4
    Tags
    # Submissions
    2
    Accepted
    1
    Uploaded By