Codechef 11.10 BAKE 树状数组
题目大意：
维护一些出售产品的信息，要么插入一条出售信息，要么查询所有在给定范围内的出售信息的总销售额，信息可能有省略，具体内容请参见原题。
算法讨论：
用树状数组维护年龄这一维，剩下的维度没有区间查询，则可以被压成一个$6$元组进行状态表示，那我们每次插入时，对于给定的$6$元组，我们修改所有这个$6$元组被包含在的信息可能不确定的$6$元组，这样的$6$元组最多有$1\times{2}\times{3}=6$种，令最大年龄为$n$，则每次修改复杂度为$O(\log n)$；对于每次查询直接在对应的树状数组中查询就行了，复杂度也为$O(\log n)$。
时空复杂度：
时间复杂度$O(S\log n)$，空间复杂度$O(n)$。
代码：（我根本不知道我写的是什么东西。。。）
#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int A[2][12][5][12][22][7][92];
#define low(x) (x & -x)
void update(int sex, int a1, int a2, int b1, int b2, int b3, int c, int v) {
for (; a1 <= 11; a1 += low(a1))
for (; a2 <= 4; a2 += low(a2))
for (; b1 <= 11; b1 += low(b1))
for (; b2 <= 21; b2 += low(b2))
for (; b3 <= 6; b3 += low(b3))
for (; c <= 91; c += low(c))
A[sex][a1][a2][b1][b2][b3][c] += v;
}
int query(int sex, int a1, int a2, int b1, int b2, int b3, int c) {
int ans = 0;
for (; a1; a1 ^= low(a1))
for (; a2; a2 ^= low(a2))
for (; b1; b1 ^= low(b1))
for (; b2; b2 ^= low(b2))
for (; b3; b3 ^= low(b3))
for (; c; c ^= low(c))
ans += A[sex][a1][a2][b1][b2][b3][c];
return ans;
}
char s[100010];
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
pii get_label() {
static int len, i, x, a[2], id;
scanf("%s", s + 1);
len = strlen(s + 1);
if (s[1] == '-')
return make_pair(11, 1);
id = 0;
for (i = 1; i <= len; ) {
x = 0;
while (i <= len && ('0' <= s[i] && s[i] <= '9'))
x = (x << 1) + (x << 3) + s[i++] - '0';
a[id++] = x;
++i;
}
if (id == 1)
return make_pair(a[0] + 1, 4);
else
return make_pair(a[0] + 1, a[1] + 1);
}
pii get_age() {
static int len, i, x, a[2], id;
scanf("%s", s + 1);
len = strlen(s + 1);
id = 0;
for (i = 1; i <= len; ) {
x = 0;
while (i <= len && ('0' <= s[i] && s[i] <= '9'))
x = (x << 1) + (x << 3) + s[i++] - '0';
a[id++] = x;
++i;
}
if (id == 1)
return make_pair(a[0], a[0]);
else
return make_pair(a[0], a[1]);
}
piii get_ins() {
static int len, i, x, a[3], id;
scanf("%s", s + 1);
len = strlen(s + 1);
if (s[1] == '-')
return make_pair(11, make_pair(1, 1));
id = 0;
for (i = 1; i <= len; ) {
x = 0;
while (i <= len && ('0' <= s[i] && s[i] <= '9'))
x = (x << 1) + (x << 3) + s[i++] - '0';
a[id++] = x;
++i;
}
if (id == 1)
return make_pair(a[0] + 1, make_pair(21, 6));
else if (id == 2)
return make_pair(a[0] + 1, make_pair(a[1] + 1, 6));
else
return make_pair(a[0] + 1, make_pair(a[1] + 1, a[2] + 1));
}
char getch() {
static char s[10];
scanf("%s", s);
return s[0];
}
vector<pii> work_label;
vector<piii> work_ins;
#define fi first
#define se second
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int Q, i, j;
cin >> Q;
pii label, age;
piii ins;
bool sex;
char type;
int v;
while (Q--) {
type = getch();
if (type == 'I') {
label = get_label();
ins = get_ins();
sex = getch() == 'M';
age = get_age();
work_label.clear();
work_ins.clear();
scanf("%d", &v);
while (1) {
work_label.push_back(make_pair(11, 1));
if (label.fi == 11)
break;
work_label.push_back(make_pair(label.fi, 4));
if (label.se == 4)
break;
work_label.push_back(make_pair(label.fi, label.se));
break;
}
while (1) {
work_ins.push_back(make_pair(11, make_pair(1, 1)));
if (ins.fi == 11)
break;
work_ins.push_back(make_pair(ins.fi, make_pair(21, 6)));
if (ins.se.fi == 21)
break;
work_ins.push_back(make_pair(ins.fi, make_pair(ins.se.fi, 6)));
if (ins.se.se == 6)
break;
work_ins.push_back(make_pair(ins.fi, make_pair(ins.se.fi, ins.se.se)));
break;
}
for (i = 0; i < (int)work_label.size(); ++i)
for (j = 0; j < (int)work_ins.size(); ++j)
update(sex, work_label[i].fi, work_label[i].se,
work_ins[j].fi, work_ins[j].se.fi,
work_ins[j].se.se, age.fi, v);
}
else {
label = get_label();
ins = get_ins();
sex = getch() == 'M';
age = get_age();
printf("%d\n", query(sex, label.fi, label.se, ins.fi, ins.se.fi, ins.se.se, age.se) -
query(sex, label.fi, label.se, ins.fi, ins.se.fi, ins.se.se, age.fi - 1));
}
}
return 0;
}
评论 (0)