Prefix XOR sum, XOR difference array

[USACO07MAR]Face The Right Way G ( Prefix exclusive or and , XOR differential array )

Title Description

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

$N$ Cows lined up $1\le N\le 5000$. Each cow is either forward or backward . To keep all the cows facing forward , Every time a farmer can $K$ A continuous cow turned $1\le K\le N$, Find the corresponding... That minimizes the number of operations $K$ And the minimum number of operations $M$.$F$ To face forward ,$B$ To face back .

Please output two numbers on one line $K$ and $M$, Separate with spaces .

Input format

Line 1: A single integer: N

Lines 2…N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

Output format

Line 1: Two space-separated integers: K and M

Examples #1

The sample input #1

7
B
B
F
B
F
B
B

Sample output #1

3 3

Tips

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

---

First of all, I came up with two binary answers , Then find a two-point answer . Know that after writing, only 10 branch , I found that this question has no two paragraphs ！

Only violence can be enumerated ,（ Because the answer output is reversed , Direct isolation ）. TLE after , It is found that we can use difference to do .

But I don't know how to know the state of the current element , Read other people's code , Is to maintain the differential array , Maintain prefixes and differences , The state of the current element is $preExclusive\; ora[i]$ .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10,M=1e9+7;

int n,a[5010],b[5010],Xor[N];
pair<int,int>res(5010,5010);

bool check(int x){
    
    int cnt = 0;
    fo(i,1,n)b[i] = a[i],Xor[i] = 0;
    int pre = 0; //  Prefix exclusive or and 
    for(int i=1;i<=n-x+1;i++){
    
     	int t = pre ^ a[i];
     	//  The current state of each point is the prefix XOR and the original state of XOR 
    	if(!t){
    
            cnt++;
            Xor[i] ^= 1;
            Xor[i+x-1] ^= 1;
            //  XOR difference 
        }
        pre ^= Xor[i];
        if(cnt>res.first)return false;
        
    }

	for(int i=n-x+2;i<=n;i++){
    
		int t = pre ^ a[i];
		if(!t)return false;
		pre ^= Xor[i];
	}
	
    if(cnt < res.first)res = {
    cnt,x};
    return true;
}

void solve(){
    
    cin>>n;
    fo(i,1,n){
    
        char x;cin>>x;
        if(x == 'F')a[i] = 1;
        else a[i] = 0;
    }
    for(int mid = 1;mid<=n;mid++){
    
        check(mid);
    }
    cout<<res.second<<" "<<res.first;
}
int main(){
    
    solve();
    return 0;
}