Độ bất đối xứng


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Gọi độ bất đối xứng của một xâu $T$ độ dài $M$ là số lượng cặp $(T_i,T_{M-i+1})$ sao cho $i<\frac{M+1}{2}$ và $T_i \neq T_{M-i+1}$.

Cho chuỗi $S$ chỉ chứa kí tự latin in thường. Cho $Q$ truy vấn, mỗi truy vấn là hai số nguyên $x$, $y$. Hãy tính độ bất đối xứng của xâu con $S[x..y]$.

Dữ liệu

  • Dòng đầu tiên chứa xâu $S \ (|S| \le 10^3)$;
  • Dòng tiếp theo chứa số nguyên $Q \ (1\le Q \le 10^5)$;
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x,y \ (1\le x \le y \le |S|)$.

Kết quả

  • In trên $Q$ dòng, mỗi dòng là kết quả của truy vấn thứ $i$.

Chấm điểm

50;$Q \le 10^3$. 50;Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

aacbca
2
2 6
1 4

output

0
2

Comments

There are no comments at the moment.