题解 | 关于d的公式

关于d的公式

由于没看懂公式的变换所以决定自己推一遍（第一次写题解）

例子1 2 3 4 5 求包含3的区间和

//(1 3)(2 3)(3 3)

//(1 4)(2 4)(3 4)

//(1 5)(2 5)(3 5)

对于(l,r)求x的区间和，左端点的取值范围是[l,x]，右端点范围是[x,r]先固定右端点

所求即为：

sum(l, x) + sum(l + 1, x) + ... + sum(x, x)//以x结尾
sum(l, x + 1) + sum(l + 1, x + 1) + ... + sum(x, x + 1)//以x+1结尾
...

sum(l, r) + sum(l + 1, r) + ...sum(x, r)//以r结尾

转化为前缀和的形式

= (pre[x] - pre[l - 1]) + (pre[x] - pre[l]) + ...(pre[x] - pre[x - 1])//这行有x-l+1项，

(pre[x + 1] - pre[l - 1]) + (pre[x + 1] - pre[l]) + ...(pre[x + 1] - pre[x - 1])

...

(pre[r] - pre[l - 1]) + (pre[r] - pre[l]) + ...(pre[r] - pre[x - 1])

共r-x+1列，把正数负数合并

= (pre[x] + pre[x + 1] + ...pre[r]) * (x - l + 1) - (pre[l - 1] + pre[l] + ...pre[x - 1]) * (r - x + 1)

设pree为pre的前缀和

= (pree[r] - pree[x - 1]) * (x - l + 1) - (pree[x - 1] - pree[l - 2]) * (r - x + 1);

特殊对于有相同元素如 3 2 1 2 4 求最大值的贡献时

若左右端点均取>=a[i]

第一个2求得区间为（3，（2），1，2）（开区间）

第二个2求得区间为（2，1，（2），4）（开区间）

（2，1，2）区间合法但未计算

若同取>a[i]则会出现重复计算

应采取左闭右开/左开右闭

附代码如下

using namespace std;
const int q=998244353;
int a[2000006],l[2000005],r[2000005],n;
long long s[2000005],c[2000006];
long long f(){
    // 3 1 2 1 2 1 3
    vector<int> ss;
    for(int i=1;i<=n;i++){
        while(ss.size()&&a[ss.back()]<a[i])ss.pop_back();
        l[i]=ss.size()?ss.back():0;
        ss.push_back(i);
    }
    ss.clear();
    for(int i=n;i>=1;i--){
        while(ss.size()&&a[ss.back()]<=a[i])ss.pop_back();
        r[i]=ss.size()?ss.back():n+1;
        ss.push_back(i);
    }
    long long res=0;
    for(int i=1;i<=n;i++){
        int ll=l[i]+1,rr=r[i]-1;
        res=(res+1ll*a[i]*(c[rr]-c[i-1]+q)%q*(i-ll+1)%q-1ll*a[i]*(c[i-1]-(ll-2>=0?c[ll-2]:0)+q)%q*(rr-i+1)%q+q)%q;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    long long res=0;
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=(s[i-1]+a[i]+q)%q,c[i]=(c[i-1]+s[i]+q)%q;
    res=f();
    for(int i=1;i<=n;i++)a[i]*=-1,s[i]=(s[i-1]+a[i]%q+q)%q,c[i]=(c[i-1]+s[i]+q)%q;
    res=(res-f()+q)%q;
    cout<<res<<endl;
}