题目
思路
- 操作2和操作3都非常好实现，直接累加一个和就行
- 关键在于操作1（nums1数组所有元素大小在0~1之间）翻转
- 线段树相比树状数组更好理解
- 具体细节见代码
代码
ini
复制代码
class Solution { typedef long long LL; static const int N = 100010; int n, m; int w[N]; struct Node { int l, r; LL sum, add;//懒标记：是否翻转过 }tr[N * 4]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { left.add ^= root.add; left.sum = (LL)(left.r - left.l + 1 - left.sum); right.add ^= root.add; right.sum = (LL)(right.r - right.l + 1 - right.sum); root.add = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, w[r], 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int d) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].add ^= d; tr[u].sum = (LL)(tr[u].r - tr[u].l + 1 - tr[u].sum); } else // 一定要分裂 { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, d); if (r > mid) modify(u << 1 | 1, l, r, d); pushup(u); } } LL query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid) sum = query(u << 1, l, r); if (r > mid) sum += query(u << 1 | 1, l, r); return sum; } public: vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) { int n = nums1.size(); LL add = 0; for(auto &x:nums2)add += x; for(int i = 1;i <= n;i ++) { w[i] = nums1[i-1]; } build(1,1,n); vector<LL> ans; for(auto &t:queries) { if(t[0] == 1)modify(1,t[1]+1,t[2]+1,1); else if(t[0] == 2)add += tr[1].sum*t[1]; else ans.push_back(add); } return ans; } };
