Codechef 12.4 TSUBSTR 后缀自动机+Trie
Codechef 12.6 CLOSEST KDTree

Codechef 11.10 BAKE 树状数组

shinbokuow posted @ Nov 20, 2015 08:11:21 PM in Something with tags 树状数组 , 891 阅读

 

题目大意:
维护一些出售产品的信息,要么插入一条出售信息,要么查询所有在给定范围内的出售信息的总销售额,信息可能有省略,具体内容请参见原题。
算法讨论:
用树状数组维护年龄这一维,剩下的维度没有区间查询,则可以被压成一个$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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter