提出 #66129299

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
using i64 = long long;
using ary = array<int, 2>;
template <typename T>
using vec = vector<T>;
constexpr int N = 2e5 + 5, mod = 998244353;
i64 n, a[N], lmx[N], rmx[N], l[N], r[N], len[N], stk[N], top;
struct node
{
    int l, r, len;
    i64 sum, add;
} t[N << 2];
void push_up(int p)
{
    t[p].sum = t[ls].sum + t[rs].sum;
}
void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r, t[p].len = r - l + 1;
    if (l == r)
    {
        return ;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(p);
}
void push_down(int p)
{
    if (t[p].add)
    {
        t[ls].add += t[p].add, t[rs].add += t[p].add;
        t[ls].sum += t[ls].len * t[p].add;
        t[rs].sum += t[rs].len * t[p].add;
        t[p].add = 0;
    }
}
void modify(int p, int l, int r, i64 k)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        t[p].add += k;
        t[p].sum += t[p].len * k;
        return ;
    }
    push_down(p);
    int mid = t[p].l + t[p].r >> 1;
    if (l <= mid) modify(ls, l, r, k);
    if (r > mid) modify(rs, l, r, k);
    push_up(p);
}
i64 query(int p, int l, int r)
{
    if (l <= t[p].l && t[p].r <= r) return t[p].sum;
    push_down(p);
    int mid = t[p].l + t[p].r >> 1;
    i64 res = 0;
    if (l <= mid) res += query(ls, l, r);
    if (r > mid) res += query(rs, l, r);
    return res;
}
void init()
{
    for (int i = 1; i <= n; i++) lmx[i] = 0, rmx[i] = n + 1;
    for (int i = 1; i <= n; i++) 
    {
        while (top && a[i] > a[stk[top]]) 
        {
            rmx[stk[top]] = i; 
            top--;
        }
        lmx[i] = stk[top];
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        l[i] = i - lmx[i], r[i] = rmx[i] - i;
        len[i] = rmx[i] - lmx[i] - 1;
        // cout << l[i] << " " << r[i] << " " << len[i] << "\n";   
    }
}
void update(int l, int r, i64 k, i64 d)
{
    if (l > r) return; 
    modify(1, l, l, k);
    if (l + 1 <= r)
        modify(1, l + 1, r, d);
    if (r < n)
        modify(1, r + 1, r + 1, -(k + d * (r - l))); 
}
void debug(int op, int l, int r, i64 k, i64 d)
{
    cout << "第 " << op << " 部分：\n";
    cout << l << " " << r << " " << k << " " << d << "\n";
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    init();
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        // 区间 [l, r] 首项为 k 公差为 D 的板子
       // 第一部分
       int L = 1, R = min(l[i], r[i]) - 1;
       i64 k = a[i], d = a[i];
       update(L, R, k, d);
    //    cout << "---------\n";
    //     debug(1, L, R, k, d);
       L = min(l[i], r[i]), R = len[i] - L + 1;
       k = min(l[i], r[i]) * a[i], d = 0;
        // debug(2, L, R, k, d);
       update(L, R, k, d);

       L = R + 1, R = len[i];
       k = (len[i] - L + 1) * a[i], d = -a[i];
        // debug(3, L, R, k, d);
       update(L, R, k, d);

    //    cout << "---------\n";
    }

    for (int i = 1; i <= n; i++) cout << query(1, 1, i) << "\n";
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘void build(int, int, int)’:
Main.cpp:27:17: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   27 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function ‘void modify(int, int, int, i64)’:
Main.cpp:50:22: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   50 |     int mid = t[p].l + t[p].r >> 1;
      |               ~~~~~~~^~~~~~~~
Main.cpp: In function ‘i64 query(int, int, int)’:
Main.cpp:59:22: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   59 |     int mid = t[p].l + t[p].r >> 1;
      |               ~~~~~~~^~~~~~~~

ジャッジ結果