LHPC 2016 pF. 毛毛蟲 ( Ad hoc )

本來以為很困難，最後幾分鐘突然靈感來。
假設由左到右有若干連續的人往右看，接著若干連續一排人往左看，那麼，哭哭的次數是固定的。假設左邊的人數為 L, 右邊的人數為 R, 考慮其中任何一個人，不失一般性取向右看的其中一人，不管他待到右邊的所有人都不見，還是一開始就被右邊的所有人看見，甚至是看了右邊 k 個人不見後，自己不見使剩下的 R - k 的人哭哭，是的，無論如何他的貢獻都是 R，不會變的。擴展到一般情況大家都亂排，這個道理也是不會變的。因此結論很簡單，答案就是兩人互看的組合數。

void solve(){
    int N; cin >> N;
    string s; cin >> s;
    vi A( N );
    for( int i = 0; i < N; ++i )
        A[ i ] = s[ i ] == 'R';
    vi pA( N + 1 );
    for( int i = 0; i < N; ++i )
        pA[ i + 1 ] = pA[ i ] + A[ i ];
    ll ans = 0;
    for( int i = 0; i < N; ++i ){
        if( A[ i ] == 0 )
            ans += pA[ i ];
        else
            ans += ( N - i - 1 - ( pA[ N ] - pA[ i + 1 ] ) );
    }
    cout << ans / 2 << endl;
}