/
Order_Tree.h
65 lines (64 loc) · 2.02 KB
/
Order_Tree.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct Mail_Cmp {
bool operator()(const Mail* a, const Mail* b) const {
if (a -> date != b -> date)
return a -> date < b -> date;
return a -> id < b -> id;
}
};
class Order_Tree {
set<Mail*, Mail_Cmp> all;
set<Mail*, Mail_Cmp> from[user_range];
set<Mail*, Mail_Cmp> to[user_range];
public:
void query(int from_id, int to_id, long long begin, long long end, Expression &exp) {
// print here
Mail beg(begin, 0), ed(end, MAX_ID);
vector<int> ans;
if (~from_id) {
auto p = from[from_id].lower_bound(&beg);
auto q = from[from_id].upper_bound(&ed);
if (~to_id) {
for (; p != q; ++p)
if ((*p) -> to == to_id && (*p) -> keyword.match(exp))
ans.push_back((*p) -> id);
}
else
for (; p != q; ++p)
if ((*p) -> keyword.match(exp)) {
ans.push_back((*p) -> id);
}
}
else if (~to_id) {
auto p = to[to_id].lower_bound(&beg);
auto q = to[to_id].upper_bound(&ed);
for (; p != q; ++p)
if ((*p) -> keyword.match(exp))
ans.push_back((*p) -> id);
}
else {
auto p = all.lower_bound(&beg);
auto q = all.upper_bound(&ed);
for (; p != q; ++p)
if ((*p) -> keyword.match(exp))
ans.push_back((*p) -> id);
}
if (ans.empty())
puts("-");
else {
sort(ans.begin(), ans.end());
for (int i = 0; i < int(ans.size()); ++i)
printf("%d%c", ans[i], " \n"[i + 1 == int(ans.size())]);
}
}
// When id = -1, means nothing
void insert(Mail &M) {
all.insert(&M);
from[M.from].insert(&M);
to[M.to].insert(&M);
}
void erase(Mail &M) {
all.erase(&M);
from[M.from].erase(&M);
to[M.to].erase(&M);
}
};