Statistical Operations on Intervals

Problem Description

Given a sequence of up to 1e5 elements, support three operations on intervals [l, r]:

1. Add a constant value to all elements in the interval
2. Calculate the average of elements in the interval
3. Calculate the variance of elements in the itnerval

Variance Calculation Approach

Variance is the key operation in this problem. The other two operations are straightforward.

Consider how to compute interval variance efficiently. The variance formula for k elements (where k = r - l + 1) is:

[ s^2 = \frac{\sum_{i=l}^{r} (\bar{x} - x_i)^2}{k} ]

Expanding this formula:

[ s^2 = \frac{\sum_{i=l}^{r} (\bar{x}^2 - 2\bar{x}x_i + x_i^2)}{k} ]

[ s^2 = \frac{1}{k}\sum_{i=l}^{r} x_i^2 - \bar{x}^2 ]

Where \(\bar{x}\) is the average value in the interval.

This shows that variance can be computed using two values:

1. The sum of elements in the interval
2. The sum of squared elements in the interval

Handling Interval Updates

When adding a constant value v to all elements in an interval, both the sum and sum of squares need to be updated. For the sum of squares:

[ \sum (x_i + v)^2 = \sum (x_i^2 + 2vx_i + v^2) = \sum x_i^2 + 2v\sum x_i + kv^2 ]

Where k is the number of elements in the interval.

Implementation

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

const int MAX_N = 100005;

double seq[MAX_N];

struct StatSegmentTree {
    struct Node {
        double total;
        double squared_total;
        double lazy;
        int left, right;
    };
    
    vector<Node> tree;
    
    int left_child(int idx) { return idx * 2; }
    int right_child(int idx) { return idx * 2 + 1; }
    
    void combine(int idx) {
        tree[idx].total = tree[left_child(idx)].total + tree[right_child(idx)].total;
        tree[idx].squared_total = tree[left_child(idx)].squared_total + tree[right_child(idx)].squared_total;
    }
    
    void apply_lazy(int idx, double value) {
        int length = tree[idx].right - tree[idx].left + 1;
        tree[idx].squared_total += 2.0 * value * tree[idx].total + length * value * value;
        tree[idx].total += length * value;
        tree[idx].lazy += value;
    }
    
    void propagate(int idx) {
        if (tree[idx].lazy != 0) {
            apply_lazy(left_child(idx), tree[idx].lazy);
            apply_lazy(right_child(idx), tree[idx].lazy);
            tree[idx].lazy = 0;
        }
    }
    
    void build(int idx, int l, int r) {
        tree[idx].left = l;
        tree[idx].right = r;
        tree[idx].lazy = 0;
        
        if (l == r) {
            tree[idx].total = seq[l];
            tree[idx].squared_total = seq[l] * seq[l];
            return;
        }
        
        int mid = (l + r) / 2;
        build(left_child(idx), l, mid);
        build(right_child(idx), mid + 1, r);
        combine(idx);
    }
    
    void range_add(int idx, int l, int r, double value) {
        if (l <= tree[idx].left && tree[idx].right <= r) {
            apply_lazy(idx, value);
            return;
        }
        if (tree[idx].right < l || r < tree[idx].left) return;
        
        propagate(idx);
        range_add(left_child(idx), l, r, value);
        range_add(right_child(idx), l, r, value);
        combine(idx);
    }
    
    pair<double, double> query_stats(int idx, int l, int r) {
        if (l <= tree[idx].left && tree[idx].right <= r) {
            return {tree[idx].total, tree[idx].squared_total};
        }
        if (tree[idx].right < l || r < tree[idx].left) {
            return {0, 0};
        }
        
        propagate(idx);
        auto left_res = query_stats(left_child(idx), l, r);
        auto right_res = query_stats(right_child(idx), l, r);
        return {left_res.first + right_res.first, left_res.second + right_res.second};
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> seq[i];
    }
    
    StatSegmentTree sst;
    sst.tree.resize(4 * n + 5);
    sst.build(1, 1, n);
    
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        
        if (op == 1) {
            double k;
            cin >> k;
            sst.range_add(1, x, y, k);
        } else {
            auto stats = sst.query_stats(1, x, y);
            double interval_sum = stats.first;
            double interval_squared_sum = stats.second;
            int length = y - x + 1;
            
            if (op == 2) {
                cout << fixed << setprecision(4) << interval_sum / length << endl;
            } else {
                double average = interval_sum / length;
                double variance = interval_squared_sum / length - average * average;
                cout << fixed << setprecision(4) << variance << endl;
            }
        }
    }
    
    return 0;
}

Binary Sequence Operations

Problem Description

Given a binary sequence of up to 1e5 elements (each element is 0 or 1), support four operations on intervals [l, r]:

1. Set all elements to 0
2. Set all elements to 1
3. Flip all elements (0 becomes 1, 1 becomes 0)
4. Count the number of 1s in the interval
5. Find the length of longest consecutive sequence of 1s in the interval

Implemantation Strategy

This problem requires maintaining two complementary sets of information for each node:

1. Statistics for the current state (1s)
2. Statistics for the flipped state (0s)

For each node, we maintain:

• Total count of 1s
• Longest consecutive 1s in the node
• Longest consecutive 1s starting from the left
• Longest consecutive 1s ending at the right

And the same four values for the flipped state (0s).

Udpate Operations

1. Set operation: Directly assign values and clear flip flags
2. Flip operation: Swap the statistics for 1s and 0s, and toggle the flip flag

When propagating updates, handle the priority: set operations override flip operations.

Implementation

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 100005;

int binary_seq[MAX_N];

struct BinarySegmentTree {
    struct NodeData {
        int total_ones;
        int max_consecutive;
        int left_consecutive;
        int right_consecutive;
        int length;
    };
    
    struct Node {
        NodeData ones, zeros;
        int set_flag;
        int flip_flag;
        int left, right;
    };
    
    vector<Node> tree;
    
    int left_child(int idx) { return idx * 2; }
    int right_child(int idx) { return idx * 2 + 1; }
    
    NodeData create_data(int value, int len) {
        return {value * len, value * len, value * len, value * len, len};
    }
    
    NodeData merge(const NodeData &a, const NodeData &b) {
        NodeData result;
        result.length = a.length + b.length;
        result.total_ones = a.total_ones + b.total_ones;
        
        result.max_consecutive = max(a.max_consecutive, b.max_consecutive);
        result.max_consecutive = max(result.max_consecutive, a.right_consecutive + b.left_consecutive);
        
        result.left_consecutive = a.left_consecutive;
        if (a.left_consecutive == a.length) {
            result.left_consecutive += b.left_consecutive;
        }
        
        result.right_consecutive = b.right_consecutive;
        if (b.right_consecutive == b.length) {
            result.right_consecutive += a.right_consecutive;
        }
        
        return result;
    }
    
    void apply_set(int idx, int value) {
        tree[idx].set_flag = value;
        tree[idx].flip_flag = 0;
        
        int len = tree[idx].right - tree[idx].left + 1;
        tree[idx].ones = create_data(value, len);
        tree[idx].zeros = create_data(1 - value, len);
    }
    
    void apply_flip(int idx) {
        if (tree[idx].set_flag != -1) {
            tree[idx].set_flag ^= 1;
            swap(tree[idx].ones, tree[idx].zeros);
        } else {
            tree[idx].flip_flag ^= 1;
            swap(tree[idx].ones, tree[idx].zeros);
        }
    }
    
    void propagate(int idx) {
        if (tree[idx].set_flag != -1) {
            apply_set(left_child(idx), tree[idx].set_flag);
            apply_set(right_child(idx), tree[idx].set_flag);
            tree[idx].set_flag = -1;
        }
        
        if (tree[idx].flip_flag) {
            apply_flip(left_child(idx));
            apply_flip(right_child(idx));
            tree[idx].flip_flag = 0;
        }
    }
    
    void build(int idx, int l, int r) {
        tree[idx].left = l;
        tree[idx].right = r;
        tree[idx].set_flag = -1;
        tree[idx].flip_flag = 0;
        
        if (l == r) {
            int value = binary_seq[l];
            tree[idx].ones = create_data(value, 1);
            tree[idx].zeros = create_data(1 - value, 1);
            return;
        }
        
        int mid = (l + r) / 2;
        build(left_child(idx), l, mid);
        build(right_child(idx), mid + 1, r);
        
        tree[idx].ones = merge(tree[left_child(idx)].ones, tree[right_child(idx)].ones);
        tree[idx].zeros = merge(tree[left_child(idx)].zeros, tree[right_child(idx)].zeros);
    }
    
    void range_set(int idx, int l, int r, int value) {
        if (r < tree[idx].left || tree[idx].right < l) return;
        if (l <= tree[idx].left && tree[idx].right <= r) {
            apply_set(idx, value);
            return;
        }
        
        propagate(idx);
        range_set(left_child(idx), l, r, value);
        range_set(right_child(idx), l, r, value);
        
        tree[idx].ones = merge(tree[left_child(idx)].ones, tree[right_child(idx)].ones);
        tree[idx].zeros = merge(tree[left_child(idx)].zeros, tree[right_child(idx)].zeros);
    }
    
    void range_flip(int idx, int l, int r) {
        if (r < tree[idx].left || tree[idx].right < l) return;
        if (l <= tree[idx].left && tree[idx].right <= r) {
            apply_flip(idx);
            return;
        }
        
        propagate(idx);
        range_flip(left_child(idx), l, r);
        range_flip(right_child(idx), l, r);
        
        tree[idx].ones = merge(tree[left_child(idx)].ones, tree[right_child(idx)].ones);
        tree[idx].zeros = merge(tree[left_child(idx)].zeros, tree[right_child(idx)].zeros);
    }
    
    int query_count(int idx, int l, int r) {
        if (r < tree[idx].left || tree[idx].right < l) return 0;
        if (l <= tree[idx].left && tree[idx].right <= r) {
            return tree[idx].ones.total_ones;
        }
        
        propagate(idx);
        return query_count(left_child(idx), l, r) + query_count(right_child(idx), l, r);
    }
    
    NodeData query_consecutive(int idx, int l, int r) {
        if (l <= tree[idx].left && tree[idx].right <= r) {
            return tree[idx].ones;
        }
        if (r < tree[idx].left || tree[idx].right < l) {
            return {0, 0, 0, 0, 0};
        }
        
        propagate(idx);
        NodeData left_res = query_consecutive(left_child(idx), l, r);
        NodeData right_res = query_consecutive(right_child(idx), l, r);
        
        return merge(left_res, right_res);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    
    for (int i = 1; i <= n; i++) {
        cin >> binary_seq[i];
    }
    
    BinarySegmentTree bst;
    bst.tree.resize(4 * n + 5);
    bst.build(1, 1, n);
    
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        l++; r++;  // Convert to 1-based indexing
        
        if (op == 0 || op == 1) {
            bst.range_set(1, l, r, op);
        } else if (op == 2) {
            bst.range_flip(1, l, r);
        } else if (op == 3) {
            cout << bst.query_count(1, l, r) << endl;
        } else if (op == 4) {
            auto result = bst.query_consecutive(1, l, r);
            cout << result.max_consecutive << endl;
        }
    }
    
    return 0;
}