#849 div4

E:

题目：

现在存在一个数组 a，现在可以执行任意次的，反转相邻两个数字。

问你数组的和最大多少。

思路：

假设1为正数，-1为负数

首先反转相邻两个数字，如果说一个 1 一个-1，反转，那么-1的个数不会发生改变。如果说两个-1，那么反转

之后，-1都变为1。所以我们可以把负数都反转到一起，如果有偶数个负数那么，都变为0，如果奇数那么剩下一个。

考虑 0，对于0 和 负数反转，负数会变为正数。所以只要数组中存在一个0，那么让每一个负数都与0反转都变为正数。

代码

void solved()
{
    cin >> n;
    int sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i] >= 0) sum += a[i];
        else sum -= a[i];
    }

    int minn = 1e9;

    for(int i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            cout << sum << endl;
            return;
        }

        minn = min(minn, abs(a[i]));
        if(a[i] < 0) cnt++;
    }


    if(cnt % 2 == 0)
    {
        cout << sum <<endl;
    }else cout << sum - minn - minn << endl;
}

F：

题目：

存在一个数组a和两种操作。

1.使得 l - r 内的数字都变为他们数位上数字的和。

2.查询a[x]

思路：

1.set

不难发现，即使最大的99999999，最多只需要3次就变为个位数，不会再改变。

所以整个数组最多操作 6e5次。所以我们用set存所有还没变为1位数的下标。

每次二分找到 l 到 r 的范围，然后对其中数字操作。

2.修改线段树，并且维护区间内是否变为个位数

代码1

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i];

    set<int>se;
    for(int i = 1; i <= n; i++) if(a[i] >= 10) se.insert(i);

    for(int i = 0; i < m; i++)
    {
        int op, l, r;
        cin >> op;

        if(op == 1)
        {
            cin >> l >> r;
            auto ll = se.lower_bound(l);
            auto rr = se.upper_bound(r);
            vector<int>p;


            for(auto i = ll; i != rr; i++)
            {
                int x = *i;

                a[x] = get(a[x]);
                if(a[x] < 10) p.push_back(x);
            }
            for(auto x : p) se.erase(x);
        }else
        {
            cin >> l;
            cout << a[l] << endl;
        }

代码2

struct Node
{
    int l, r;
    int sum;
    int lazy;
    bool flag;

}tr[N * 4];

int get(int u)
{
    if(u == 0) return 0;
    int sum = 0;
    while(u)
    {
        sum += u % 10;
        u /= 10;
    }
    return sum;
}

void push_up(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].flag = tr[u << 1].flag && tr[u << 1 | 1].flag;
}


void build(int u, int l, int r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[l], 0};
        return;
    }

    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    push_up(u);
}

void modify(int u, int l, int r)
{
    if(tr[u].flag) return;
    if(tr[u].l >= l && tr[u].r <= r && tr[u].l == tr[u].r)
    {
        tr[u].sum = get(tr[u].sum);
        if(tr[u].sum < 10) tr[u].flag = true;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r);
    if(r > mid) modify(u << 1 | 1, l, r);
    push_up(u);
}

int query(int u, int x)
{
    if(tr[u].l == x && tr[u].r == x)
    {
        return tr[u].sum;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    int ans = 0;
    if(x <= mid) ans += query(u << 1, x);
    if(x > mid) ans += query(u << 1 | 1, x);

    return ans;
}

void solved()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    for(int i = 0; i < m; i++)
    {
        int op, l, r;
        cin >> op;

        if(op == 1)
        {
            cin >> l >> r;
            modify(1, l, r);
        }else
        {
            cin >> l;
            cout << query(1, l) <<endl;
        }
    }

}

G1

题目：

存在 1 - n 上每个位置一个 tel，而你在 0，每次左右走代价为1，取走位置上的tel，代价为a[pos]，并且取走tel后，传送到0

现在只有m 个硬币，问你最多取多少个tel

思路：

小根堆维护每个位置上代价。

代码

void solved()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i];

    priority_queue<int, vector<int>, greater<int>>q;

    for(int i = 1; i <= n; i++)
    {
        w[i] = a[i] + i - 0;
        q.push(w[i]);
    }

    int ans = 0;
    while(q.size())
    {
        int x = q.top();
        q.pop();
        if(m < x) break;
        m -= x;
        ans++;
    }

    cout << ans << endl;

}