第 116 场双周赛(双指针，背包问题，线段树+lz标记)-526互联

本题为双指针和贪心。当我们遇到奇数个0或1时，直接将下一位改变即可。

class Solution {
public:
    int minChanges(string s) {
        int n = s.size();

        int res = 0;
        int l = 0, r = -1;
        while(r ++ < n - 1) {
            if(s[l] == s[r]) continue;
            if((r - l) % 2 == 0) {
                l = r;
                continue;
            }
            s[r] = s[r] == '0'? '1': '0';
            l = r + 1;
            res ++ ;
        }

        return res;
    }
};

本题f[i][j]表示只从前i个数中选，子序列和为j的所有方案数

if (j >= nums[i]) f[i][j] = f[i - 1][j - nums[i]] + 1　　属于完全装满的01背包问题。

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> f(1010, INT_MIN);
        f[0] = 0;
        int s = 0;

        for(auto x: nums) {
            s = min(s + x, target);
            for(int j = s; j >= x; j -- ) {
                f[j] = max(f[j], f[j - x] + 1);
            }
        }

        return f[target] > 0 ? f[target]: -1;
    }
};

首先本题要求区间不同计数的平方和。

可以将此问题拆分为：

　　　　　　　　1、某个区间的不同数的个数

　　　　　　　　2、子问题1所求得个数的平方和

可以用线段树来求解。

1、快速求出区间不同数的个数 -> 哈希 + 线段树

另 unordered_map<int, int> last; 即为nums[i]上一次出现的位置，那么对于last[nums[i]] 到 i 之间的所有区间，就都相当于包含了次数字。

2、快速求出区间平方和 -> 线段树 + lz标记

我们同时维护区间和s1和区间平方和s2,

　　　　　　　　　　　　s2 = s2 + 2 * k * s1 + k * k

　　　　　　　　　　　　s1 = s1 + len * k

class Solution {
public:
    const static int N = 1e5 + 10, MOD = 1e9 + 7;

    struct Node {
        int l, r;
        long long sum1, sum2;
        int lazy;
    }tr[N * 4];

    void push_up(int u) {
        tr[u].sum1 = (tr[u << 1].sum1 + tr[u << 1 | 1].sum1) % MOD;
        tr[u].sum2 = (tr[u << 1].sum2 + tr[u << 1 | 1].sum2) % MOD;
    }

    void add(int u, int K) {
        int len = tr[u].r - tr[u].l + 1;
        tr[u].sum2 = (tr[u].sum2 + 2LL * K * tr[u].sum1 + 1LL * K * K % MOD * len);
        tr[u].sum1 = (tr[u].sum1 + 1LL * K * len) % MOD;
    }

    void push_down(int u) {
        tr[u << 1].lazy += tr[u].lazy;
        add(u << 1, tr[u].lazy);
        tr[u << 1 | 1].lazy += tr[u].lazy;
        add(u << 1 | 1, tr[u].lazy);
        tr[u].lazy = 0;
    }

    void build(int u, int l, int r) {
        if(l == r) tr[u] = {l, r, 0, 0, 0};
        else {
            tr[u] = {l, r, 0, 0};
            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].l >= l && tr[u].r <= r) {
            add(u, 1);
            tr[u].lazy ++ ;
        } else {
            push_down(u);
            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 sumCounts(vector<int>& nums) {
        int n = nums.size();
        build(1, 1, n + 5);
        long long res = 0;
        unordered_map<int, int> last;
        for(int i = 1; i <= n; i ++ ) {
            auto &old = last[nums[i - 1]];
            modify(1, old + 1, i);
            old = i;
            res = (res + tr[1].sum2) % MOD;
        }

        return res;
    }
};