Video Explanation (Binary Search intuition)
Explanation\n\nClick here for the video\n\n# Code\n\ntypedef long long int ll;\n\n#define pii pair<int, int>\n#define F first\n#define S second\n\nclass Solutio
# Explanation\n\n[Click here for the video](https://youtu.be/OJiVpzztP_s)\n\n# Code\n```\ntypedef long long int ll;\n\n#define pii pair<int, int>\n#define F first\n#define S second\n\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        vector<pii> rows(n, make_pair(-1, 0));\n        vector<pii> cols(n, make_pair(-1, 0));\n        \n        for (int j = 0; j < queries.size(); j ++) {\n            vector<int> q = queries[j];\n            \n            if (q[0] == 0) \n                rows[q[1]] = {j, q[2]};\n            else \n                cols[q[1]] = {j, q[2]};\n        }\n        \n        long long result = 0;\n        \n        /*\n        for (int r = 0; r < n; r ++) {\n            for (int c = 0; c < n; c ++) {\n                pii val = max (rows[r], cols[c]);\n                result += val.S;\n            }\n        }\n        */\n        \n        sort (cols.begin(), cols.end());\n        \n        vector<ll> prefix_cols(n+1, 0);\n        for (int j = 1; j <= n; j ++) prefix_cols[j] = prefix_cols[j-1] + cols[j-1].S;\n        \n        for (int r = 0; r < n; r ++) {\n            pii row = rows[r];\n            ll col_pos = lower_bound(cols.begin(), cols.end(), row) - cols.begin();\n            \n            result += col_pos * row.S;\n            if (col_pos < n) result += (prefix_cols[n] - prefix_cols[col_pos]);\n        }\n        \n        return result;\n    }\n};\n```
['C++']