[380 ms] SQRT Decomposition
I was upset that my $O(nm)$ didn\'t pass so I wrote square root decomposition.  \n# Intuition\n Describe your first thoughts on how to solve this problem. \n\n#
I was upset that my $O(n*m)$ didn\'t pass so I wrote square root decomposition.  \n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe divide array to blocks from index. From index $0$ to $BLOCK\\_SIZE -1$, $BLOCK\\_SIZE$ to  $2*BLOCK\\_SIZE$, ..., $k*BLOCK\\_SIZE$ to $n$.\nIn each block, we calculate 4 styles of the maximum subsequence sum without adjacent elements:\n1. No condition.\n2. Do not use the first element.\n3. Do not use the last element.\n4. Do not use the first and the last element.\n\nAfter we calculate each block, we can combine the blocks by iterating block from first to last storing 2 values:\n1. `no_condition` Maximum subsequence sum without adjacent elements without condition.\n2. `no_last` Maximum subsequence sum without adjacent elements without using the last element from the latest block we iterate.\n\nYou can find the way to maintain these values for each iteration by using 4 variables in the block.\n\n# Complexity\n- Time complexity: $$O(Q * (BLOCK\\_SIZE + N/BLOCK\\_SIZE))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nconst int K = 8;\nconst int SIZE = 1 << K;\nconst int MASK = SIZE - 1;\nclass Solution {\npublic:\n    \n    struct BLOCK{\n        vector<int> vals;\n        vector<int> dp;\n        int full, no_first, no_last, no_fl;\n        void update() {\n            dp[0] = vals[0];\n            for (int i = 1;  i < SIZE; ++i) {\n                dp[i] = max(dp[i -1], (i > 1 ? dp[i -2] : 0) + vals[i]);\n            }\n            full = dp[SIZE -1], no_last = dp[SIZE - 2];\n            dp[1] = vals[1];\n            for (int i = 2; i < SIZE; ++i) {\n                dp[i] = max(dp[i -1], (i > 2 ? dp[i -2]: 0) + vals[i]);\n            }\n            no_first = dp[SIZE - 1];\n            no_fl = dp[SIZE - 2];\n        }\n        BLOCK() {\n            vals.resize(SIZE);\n            dp.resize(SIZE);\n            no_first = no_last = no_fl = 0;\n        }\n        \n    } block[256];\n    \n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int MOD = 1e9 + 7;\n        vector<long long> ans(nums.size());\n        ans[0] = max(0, nums[0]);\n        int n_block = (nums.size() + MASK) >> K;\n        for (int i = 0; i < nums.size(); ++i) {\n            block[i >> K].vals[i & MASK] = max(nums[i], 0);\n        }\n        for (int i = 0; i < n_block; ++i) {\n            block[i].update();\n        }\n        long long ret = 0;\n        for (auto &v: queries) {\n            int id = v[0], val = max(0, v[1]);\n            int b = id >> K;\n            id &= MASK;\n            block[b].vals[id] = val;\n            block[b].update();\n            long long nl = block[0].no_last, full = block[0].full;\n            for (int i = 1; i < n_block; ++i) {\n                long long nfull = max(nl + block[i].full, full + block[i].no_first);\n                long long nnl = max(nl + block[i].no_last, full + block[i].no_fl);\n                full = nfull, nl = nnl;\n            }\n            ret += full;\n            ret %= MOD;\n        }\n        return ret;\n    }\n};\n```
['C++']