UVA 1597 Searching the Web

stl应用。爆搜虽然能过，但是其实可以根据词建一个索引，我用了pair<int, int>来代表词出现在第几篇文章的第几行。这样做有个好处就是，把pair<int, int>丢进set，自动就按照文章-行的顺序排好了。接下来只要判断然后构建符合条件的文章set<int>就好（判断成功时顺便），可以用algorithm的交集并集，不过我没用。能改进的地方其实挺多的，不过这样就100ms水进Leaderboard前十了，因垂丝汀。以及sstream真的好慢，去掉直接快20ms……

#include <iostream>
#include <map>
#include <vector>
#include <set>

using namespace std;
map<string, vector<pair<int, int>>> dict;
vector<vector<string>> passages;

int main() {
    int n, cur, cnt = 0;
    string line, word, key;
    cin >> n; getline(cin, line);
    cur = 0;
    passages.push_back(vector<string>());
    while (n) {
        getline(cin, line);
        if (line[0] == '*' && line.size() == 10) {
            if (++cur == n) break;
            else {
                cnt = 0;
                passages.push_back(vector<string>());
            }
            continue;
        }
        word.clear(); line.push_back('\n');
        for (char c: line) {
            if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z') {
                word.push_back(tolower(c));
            } else if (word.size() > 0) {
                pair<int, int> term;
                if (dict.count(word) == 0)
                    dict[word] = vector<pair<int, int>>();
                term.first = cur; term.second = cnt;
                dict[word].push_back(term);
                word.clear();
            }
        }
        cnt++;
        passages[cur].push_back(line);
    }
    cin >> n; getline(cin, line);
    vector<string> expr;
    bool hit = false;
    set<int> found;
    set<pair<int, int>> lines;
    while (n--) {
        getline(cin, line);
        expr.clear(); hit = false; found.clear(); lines.clear();
        int ls = 0, i = 0;
        while(++i <= line.size())
            if (i == line.size() || line[i] == ' ')
                expr.push_back(line.substr(ls, i)), ls = i + 1;
        key = expr.size() == 2? expr[1]: expr[0];
        if (dict.count(key) > 0) {
            for (auto p: dict[key]) {
                found.insert(p.first);
                lines.insert(p);
            }
        }
        if (expr.size() == 2) {
            for (int i = 0; i < passages.size(); i++) {
                if (found.count(i) > 0) continue;
                if (hit) cout << "----------\n";
                for (auto l: passages[i]) cout << l;
                hit = true;
            }
        } else {
            if (expr.size() == 3) {
                if (expr[1][0] == 'A') {
                    set<int> nfound;
                    if (dict.count(expr[2]) > 0) {
                        for (auto p: dict[expr[2]])
                            if (found.count(p.first) > 0) {
                                nfound.insert(p.first);
                                lines.insert(p);
                            }
                    }
                    found = nfound;
                } else {
                    if (dict.count(expr[2]) > 0) {
                        for (auto p: dict[expr[2]]) {
                            found.insert(p.first);
                            lines.insert(p);
                        }
                    }
                }
            }
            if (found.size() > 0) {
                int last = 0;
                for (auto p: lines) {
                    if (found.count(p.first) == 0) continue;
                    if (hit && p.first != last) cout << "----------\n";
                    cout << passages[p.first][p.second];
                    hit = true; last = p.first;
                }
            }
        }
        if (!hit) cout << "Sorry, I found nothing.\n";
        cout << "==========\n";
    }
    return 0;
}