cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2024 · MediumLocal invariant updates

Count Binary Runs Under Bit Flips

National Olympiad — National round (2024 season)

Submission name: bitstring.cpp

Solve in Editor →

Problem summary

Maintain a binary string under Inv i flips and Print x queries. Following the complete official sample, Print counts maximal runs of the requested bit.

Source clarification. The printed statement calls these objects substrings, but its complete sample and explanation count maximal constant runs. For example, 1110110111 has three one-runs rather than fifteen all-one substrings. This solution follows that demonstrated interpretation.

Input

The binary string, command count, then Inv i or Print x. Positions are 1-based.

Output

One run count per Print command.

Constraints

1≤string length,command count≤1000000.

Worked example

Input and output for the worked example discussed below.

Input

1100111011
11
Inv 8
Inv 3
Inv 7
Print 1
Inv 5
Inv 3
Print 0
Inv 2
Inv 9
Print 0
Print 1

Output

3
2
3
4

Solution analysis

  1. A run starts at i precisely when i=0 or its bit differs from the previous bit. Maintain separate counters for zero-run and one-run starts.
  2. Flipping position i can affect only start tests i and i+1. Remove those old contributions, flip, and add the new contributions; all other comparisons remain unchanged.
  3. After the first three sample flips, 1110110111 has three one-runs: 111,11,111. The remaining commands produce counts 2,3,4. Each maximal run counts once regardless of length.

Why it works

The start condition identifies one position for each maximal run. Exactly the two tests using the changed bit can change, and both are recomputed. This preserves the run counts after each operation.

Complexity: O(n+t) time and O(n) space, with O(1) per command after initialization.

Watch out. Do not count all homogeneous substrings: that would contradict the source sample. Convert the 1-based flip index and check the right endpoint.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string bits;
    cin>>bits;
    int runs[2]={0,0};
    auto change=[&](int position,int delta){
        if(position<int(bits.size())&&(position==0||bits[position]!=bits[position-1])){
            runs[bits[position]-'0']+=delta;
        }
    };
    for(int i=0;i<int(bits.size());i++){
        change(i,1);
    }
    int commands;
    cin>>commands;
    while(commands-->0){
        string command;
        int value;
        cin>>command>>value;
        if(command=="Print"){
            cout<<runs[value]<<'\n';
        }
        else{
            int position=value-1;
            // Only these two possible starts use the flipped bit.
            change(position,-1);
            change(position+1,-1);
            bits[position]=bits[position]=='0'?'1':'0';
            change(position,1);
            change(position+1,1);
        }
    }
}

Source: Arena Olimpiici ↗