大神的世界

討論區有公佈一個解答，方法是計算每個 A 的左右 Q 個數再相乘

挺厲害的，我沒想到可以這樣做~~~~ ， 下面就獻醜拉

因為題目要 QAQ ，所以只需紀錄 Q 和 A 即可

另外，用兩個 list 分別紀錄 Q 和 A

Q list 只紀錄 Q 的位置

A 的 list 除了紀錄位置，還紀錄 A 後 Q 的個數

而計算 QAQ 的方法就是

從某個 Q 出發，加總此 Q 後面所有 A 紀錄的 後面 Q 數

#include <iostream>
#include <stdint.h>
#include <list>
#include <cstring>

using namespace std;

typedef struct A_struct{
    uint32_t pos;
    uint32_t Q_number;
} A;

int main()
{
    list<A*> A_list;
    list<uint32_t> Q_list;

    char str[100000];
    uint64_t QAQ;

    while(cin >> str){

        QAQ = 0;

        uint32_t len = strlen(str);
        uint32_t Q_num = 0;

        for(int32_t i = len-1; i>=0; i--)
            if(str[i] == 'Q'){
                Q_list.push_front(i);
                Q_num++;
            }
            else if(str[i] == 'A'){
                A* new_A = new A;
                new_A->pos = i;
                new_A->Q_number = Q_num;
                A_list.push_front(new_A);
            }

        list<A*>::iterator Ait, AitTemp;
        list<uint32_t>::iterator Qit;

        for( Qit = Q_list.begin(), Ait = A_list.begin(); Qit != Q_list.end(); Qit++){
            while(Ait != A_list.end() && *Qit > (*Ait)->pos)
                Ait++;

            for(AitTemp = Ait; AitTemp != A_list.end(); AitTemp++)
                QAQ += (*AitTemp)->Q_number;
        }

        cout << QAQ << endl;

        Q_list.clear();
        A_list.clear();
    }

}