Niitty

use std::collections::VecDeque;
use std::{cmp, io};

fn main() {
    let stdin = io::stdin();

    let n: usize = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        input.trim().parse().unwrap()
    };

    let mut tree_last_row: Vec<Vec<u32>> = Vec::with_capacity(2 * n);
    for _ in 0..n {
        let mut row_columns: Vec<u32> = Vec::with_capacity(n);

        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let mut chars = input.trim().chars();
        for _ in 0..n {
            let char = chars.next().unwrap().to_ascii_uppercase();
            debug_assert!(char.is_ascii_alphabetic());

            let index = get_char_index(char);
            let flower = 1 << index;
            row_columns.push(flower);
        }

        let subtree = build_tree(row_columns, sum_flower_cells);
        tree_last_row.push(subtree);
    }

    let tree = build_tree(tree_last_row, sum_flower_rows);

    let all_flower_types: u32 = tree[0][0];
    let mut counter: u128 = 0;
    for start_y in 0..n {
        for end_y in start_y..n {
            let vertical = get_flowers(start_y, end_y, n, &tree, sum_flower_rows);
            if vertical[0] != all_flower_types {
                continue;
            }
            for start_x in 0..n {
                for end_x in start_x..n {
                    let complete = get_flowers(start_x, end_x, n, &vertical, sum_flower_cells);
                    if complete == all_flower_types {
                        counter += 1;
                    }
                }
            }
        }
    }
    println!("{}", counter);

}

fn build_tree<T : Default>(mut bottom_row: Vec<T>, sum_function: fn(&T, &T) -> T) -> Vec<T> {
    let bottom_row_len = bottom_row.len().next_power_of_two();
    for _ in bottom_row.len()..bottom_row_len {
        bottom_row.push(T::default());
    }
    debug_assert!(bottom_row.len().is_power_of_two());
    debug_assert_eq!(bottom_row.len(), bottom_row_len);

    let mut tree: VecDeque<T> = VecDeque::with_capacity(bottom_row_len * 2);
    tree.extend(bottom_row);
    let default_t = T::default();
    let mut sum_start = 0;
    let mut sum_len = bottom_row_len;
    while sum_len > 1 {
        let dest_len = sum_len / 2;
        for i in (0..dest_len).rev() {
            let a = sum_start + i * 2;
            let b = a + 1;

            let a_item = &tree[a];
            let b_item = if b >= (sum_start + sum_len) { &default_t } else { &tree[b] };

            tree.push_front(sum_function(a_item, b_item));
            sum_start += 1;
        }

        sum_len = dest_len;
        sum_start -= dest_len;
    }

    Vec::from(tree)
}

fn get_flowers<T : Default>(mut start: usize, mut end: usize, n: usize, tree: &Vec<T>, sum_function: fn(&T, &T) -> T) -> T {
    let mut level_len = n.next_power_of_two();
    let mut level_start = tree.len() - level_len;
    let mut sum = T::default();
    while start <= end {
        debug_assert!(end < level_len);
        if start % 2 == 1 {
            //eprintln!("+ start {}", level_start + start);
            sum = sum_function(&sum, &tree[level_start + start]);
            start += 1;
        }
        if end % 2 == 0 {
            //eprintln!("+ end {}", level_start + end);
            sum = sum_function(&sum, &tree[level_start + end]);
            if end == 0 {
                break;
            } else {
                end -= 1;
            }
        }

        // Move one level up
        level_len /= 2;
        level_start -= level_len;
        start /= 2;
        end /= 2;
    }

    sum
}

// Valid indices start from 1. 0 is reserved for an invalid/dummy state without actual flowers.
fn get_char_index(flower: char) -> u32 {
    if 'A' <= flower && flower <= 'Z' {
        flower as u32 - 'A' as u32 + 1
    } else {
        panic!("Illegal flower: {}", flower);
    }
}

fn sum_flower_cells(a: &u32, b: &u32) -> u32 {
    *a | *b
}

fn sum_flower_rows(a: &Vec<u32>, b: &Vec<u32>) -> Vec<u32> {
    let len = cmp::max(a.len(), b.len());
    let mut vec = Vec::with_capacity(len);
    if a.len() == b.len() {
        for i in 0..len {
            vec.push(sum_flower_cells(&a[i], &b[i]));
        }
    } else {
        // This would also work for the other case, but this is probably slower.
        debug_assert_eq!(cmp::min(a.len(), b.len()), 0);
        let mut a_iter = a.iter().chain([0].iter().cycle());
        let mut b_iter = b.iter().chain([0].iter().cycle());
        for _ in 0..len {
            vec.push(sum_flower_cells(a_iter.next().unwrap(), b_iter.next().unwrap()));
        }
    }
    vec
}

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 14

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

Test 18

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 6

Verdict: TIME LIMIT EXCEEDED