問題概要
制約
省略
解答
s を一つ固定し， k=0, \ldots,N-1 に対し，「左から k 番目にある正電荷」と「 左からk 番目にある負電荷」を対応付け，ペアと呼びます．このうち右，左にあるものの位置をそれぞれ a(s, k)，b(s, k) と定めます．ポテンシャルによる対応付けとは一般に異なることに注意してください．
このとき，
となります．ただし \delta_{x, y} はKroneckerのデルタで，x=y ならば 1 を，さもなくば 0 をとります．したがって，問題の答えは，
となります．
\left(\delta_{i,a(s, k)} - \delta_{i,b(s,k)}\right) について考えます．この式は，位置 i に k 番目の正電荷または負電荷がある場合に限り 0 でない値をとり，具体的にはそれがペアの左なら 1 ，右なら -1 をとります．
位置 i に k 番目の正電荷がある場合
半開区間 \left[0, i\right) に k 個の正電荷があるので，同じ区間に \left(i-k\right) 個の負電荷があります．したがって，位置 i の正電荷がペアの左である条件は k\geq i-k です．この条件は s に依存しないので，s の個数を数え上げたあとで 1 倍または -1 倍すればよいです．
T_i が-の場合，0 通りです．そうでない場合，\left[0, i\right) に k 個，\left(i, 2N\right) に N-k-1 個の正電荷があればよく，このような割り当て方の数は二項係数の積として表せます．
具体的には，T\left[0..i\right) に X 個の?及び Y 個の+が含まれるとすれば，この部分の割り当て方は \binom{X}{k-Y} 通りです．T\left(i..2N\right) も同様です．適当な前計算（\Theta\left(N\right) 時間）を行うことでこれらは定数時間で求められます．
位置 i に k 番目の負電荷がある場合
正電荷の場合と同様に，今度は各区間に含まれる負電荷の個数を考えればよいです．
以上により，\Theta\left(N^2\right) 時間 で解くことができました．