12 minutes
[BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings（树状数组 + 主席树）
终于学会了主席树，写了高贵冷艳的带修改区间第K大（虽然二逼平衡树我是用分块水的），关于不带修改的区间第K大参见我的上一篇博客{% post_link poj2104 %}，其实这个跟树状数组维护前缀和基本是一样的，只是修改时树状数组只需修改(log_2n)个节点，而现在需要修改(log_2n)棵线段树，一共(log_2^2n)个节点。这题在八中上妥妥A了，ZOJ被卡内存（内存小，数据规模还大，还有多组数据，改了半天），到现在都没卡过去，真是不开心。
八中：
//ZJU 2112.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO
const int MAXN = 10010;
const int MAXTMP = 100;
const int MAXTREE = 600000;
#ifdef LOCAL
#define LOCAL_TIME
#define LOCAL_DEBUG
//#define STD_DEBUG
//#define LOCAL_SIMP
#endif
#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif
#ifdef LOCAL_TIME
#include<ctime>
#endif
#ifdef READ_FREAD
char fread_char;
inline void fread_init()
{
fread_char = getchar();
}
inline int get_int()
{
int ret = 0;
while ((fread_char < '0') || (fread_char > '9'))
{
fread_char = getchar();
}
while ((fread_char >= '0') && (fread_char <= '9'))
{
ret = ret * 10 + fread_char - '0';
fread_char = getchar();
}
return ret;
}
inline char get_char()
{
while ((fread_char == ' ') || (fread_char == 'n'))
{
fread_char = getchar();
}
char ret = fread_char;
fread_char = getchar();
return ret;
}
#endif
inline void read(int &a)
{
#ifdef READ_FREAD
a = get_int();
#else
scanf("%d", &a);
#endif
}
inline void read(char &a)
{
#ifdef READ_FREAD
a = get_char();
#else
scanf("%c", &a);
#endif
}
struct discre_node
{
int val, id;
inline bool operator < (const discre_node &b) const
{
return val < b.val;
}
};
struct tree_node
{
int tot;
tree_node *l_child, *r_child;
inline tree_node *init()
{
l_child = r_child = 0;
return this;
}
};
tree_node recover_tree_node[MAXTREE];
tree_node *stack_recover_tree_node[MAXTREE];
int top_stack_recover_tree_node = MAXTREE;
inline void init_recover_tree_node()
{
for (int i = 0; i < MAXTREE; i++)
{
stack_recover_tree_node[i] = recover_tree_node + i;
}
}
inline tree_node *new_node()
{
return stack_recover_tree_node[--top_stack_recover_tree_node]->init();
}
inline void delete_node(tree_node *del_node)
{
stack_recover_tree_node[top_stack_recover_tree_node++] = del_node;
}
int n, m;
discre_node discre_tmp[2 * MAXN];
int tot_discre;
int discre_to_num[2 * MAXN];
int max_discre;
char op_string;
int discre[MAXN];
int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
tree_node *interval[MAXN];
inline void tree_insert(int root, const int val)
{
tree_node *tmp = interval[root];
tree_node **last_tmp = interval + root;
int l = 1, r = max_discre, mid;
while (l < r)
{
if (tmp == NULL)
{
*last_tmp = tmp = new_node();
tmp->tot = 1;
}
else
{
tmp->tot++;
}
mid = (l + r) >> 1;
if (val <= mid)
{
last_tmp = &tmp->l_child;
tmp = tmp->l_child;
r = mid;
}
else
{
last_tmp = &tmp->r_child;
tmp = tmp->r_child;
l = mid + 1;
}
}
if (tmp == NULL)
{
*last_tmp = tmp = new_node();
tmp->tot = 1;
}
else
{
tmp->tot++;
}
}
inline void tree_delete(int root, const int val)
{
tree_node *tmp = interval[root];
if (tmp == NULL)
{
return;
}
tree_node **last_tmp = interval + root;
int l = 1, r = max_discre, mid;
while (l < r)
{
tmp->tot--;
if (tmp->tot == 0)
{
delete_node(tmp);
*last_tmp = NULL;
}
mid = (l + r) >> 1;
if (val <= mid)
{
last_tmp = &tmp->l_child;
tmp = tmp->l_child;
r = mid;
}
else
{
last_tmp = &tmp->r_child;
tmp = tmp->r_child;
l = mid + 1;
} //我知道这样写不好。。但是不管了
}
tmp->tot--;
if (tmp->tot == 0)
{
delete_node(tmp);
*last_tmp = NULL;
}
}
inline int tree_left_size(tree_node *query_node)
{
if (query_node == NULL)
{
return 0;
}
if (query_node->l_child == NULL)
{
return 0;
}
return query_node->l_child->tot;
}
inline int lowerbit(const int x)
{
return x & (-x);
}
inline void interval_insert(int l, const int val)
{
while (l <= n)
{
tree_insert(l, val);
l += lowerbit(l);
}
}
inline void interval_delete(int l, const int val)
{
while (l <= n)
{
tree_delete(l, val);
l += lowerbit(l);
}
}
tree_node *tmp_add[MAXTMP];
int tot_tmp_add;
tree_node *tmp_minus[MAXTMP];
int tot_tmp_minus;
inline int interval_query(int l, int r, const int k)
{
tot_tmp_add = tot_tmp_minus = 0;
while (r > 0)
{
tmp_add[tot_tmp_add++] = interval[r];
r -= lowerbit(r);
}
l--;
while (l > 0)
{
tmp_minus[tot_tmp_minus++] = interval[l];
l -= lowerbit(l);
}
int binary_l = 1, binary_r = max_discre, mid, tot_left;
int tot_length = 0;
while (binary_l < binary_r)
{
mid = (binary_l + binary_r) >> 1;
tot_left = 0;
for (int i = 0; i < tot_tmp_add; i++)
{
tot_left += tree_left_size(tmp_add[i]);
}
for (int i = 0; i < tot_tmp_minus; i++)
{
tot_left -= tree_left_size(tmp_minus[i]);
}
if (tot_length + tot_left >= k)
{
for (int i = 0; i < tot_tmp_minus; i++)
{
if (tmp_minus[i] != NULL)
{
tmp_minus[i] = tmp_minus[i]->l_child;
}
}
for (int i = 0; i < tot_tmp_add; i++)
{
if (tmp_add[i] != NULL)
{
tmp_add[i] = tmp_add[i]->l_child;
}
}
binary_r = mid;
}
else
{
for (int i = 0; i < tot_tmp_minus; i++)
{
if (tmp_minus[i] != NULL)
{
tmp_minus[i] = tmp_minus[i]->r_child;
}
}
for (int i = 0; i < tot_tmp_add; i++)
{
if (tmp_add[i] != NULL)
{
tmp_add[i] = tmp_add[i]->r_child;
}
}
binary_l = mid + 1;
tot_length += tot_left;
}
}
return binary_l;
}
#ifndef LOCAL_SIMP
int main()
{
#ifdef LOCAL_TIME
long long start_time_ = clock();
#endif
#ifdef READ_FILE
freopen("1901.in", "r", stdin);
#ifndef STD_DEBUG
freopen("1901.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
fread_init();
#endif
init_recover_tree_node();
read(n);
read(m);
for (int i = 0; i < n; i++)
{
read(discre_tmp[i].val);
discre_tmp[i].id = i;
}
tot_discre = n;
for (int i = 0; i < m; i++)
{
read(op_string);
if (op_string == 'Q')
{
op[i] = 1;
read(op_i[i]);
read(op_j[i]);
read(op_k[i]);
}
else
{
op[i] = 2;
read(op_i[i]);
read(discre_tmp[tot_discre].val);
discre_tmp[tot_discre++].id = n + i;
}
}
std::sort(discre_tmp, discre_tmp + tot_discre);
max_discre = 0;
for (int i = 0; i < tot_discre; i++)
{
if ((i == 0) || (discre_tmp[i - 1] < discre_tmp[i]))
{
discre_to_num[++max_discre] = discre_tmp[i].val;
}
if (discre_tmp[i].id < n)
{
discre[discre_tmp[i].id] = max_discre;
}
else
{
op_k[discre_tmp[i].id - n] = max_discre;
}
}
for (int i = 0; i < n; i++)
{
interval_insert(i + 1, discre[i]);
}
for (int i = 0; i < m; i++)
{
#ifdef LOCAL_DEBUG
if (i == 6)
{
printf("");
}
#endif
if (op[i] == 1)
{
printf("%dn", discre_to_num[interval_query(op_i[i], op_j[i], op_k[i])]);
}
else if (op[i] == 2)
{
interval_delete(op_i[i], discre[op_i[i] - 1]);
interval_insert(op_i[i], op_k[i]);
discre[op_i[i] - 1] = op_k[i];
}
}
#ifdef LOCAL_TIME
printf("run time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
fclose(stdin);
#ifndef STD_DEBUG
fclose(stdout);
#endif
#endif
return 0;
}
#else
int a[MAXN];
int sort_tmp[MAXN];
//int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
int main()
{
const int N = 5;
const int M = 10;
const int RAND_BASE = 234;
freopen("1901.in", "w", stdout);
srand(RAND_BASE);
printf("%d %dn", N, M);
for (int i = 0; i < N; i++)
{
printf("%d ", a[i] = rand());
}
printf("n");
for (int i = 0; i < M; i++)
{
op[i] = rand() % 2;
if (op[i] == 0)
{
printf("Q ");
op_i[i] = rand() % N + 1;
op_j[i] = op_i[i] + rand() % (N - op_i[i] + 1);
op_k[i] = rand() % (op_j[i] - op_i[i] + 1) + 1;
printf("%d %d %dn", op_i[i], op_j[i], op_k[i]);
}
else if (op[i] == 1)
{
printf("C ");
op_i[i] = rand() % N + 1;
op_k[i] = rand();
printf("%d %dn", op_i[i], op_k[i]);
}
}
fclose(stdout);
freopen("1901std.out", "w", stdout);
for (int i = 0; i < M; i++)
{
if (op[i] == 1)
{
a[op_i[i] - 1] = op_k[i];
}
else if (op[i] == 0)
{
memcpy(sort_tmp, a + op_i[i] - 1, (op_j[i] - op_i[i] + 1) * sizeof(int));
std::sort(sort_tmp, sort_tmp + op_j[i] - op_i[i] + 1);
printf("%dn", sort_tmp[op_k[i] - 1]);
}
}
fclose(stdout);
}
#endif
POJ版（MLE）：
//ZJU 2112.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO
const int MAXN = 50010;
const int MAXM = 10000;
const int MAXTMP = 100;
const int MAXTREE = 3500000;
#ifdef LOCAL
#define LOCAL_TIME
#define LOCAL_DEBUG
//#define STD_DEBUG
//#define LOCAL_SIMP
#endif
#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif
#ifdef LOCAL_TIME
#include<ctime>
#endif
#ifdef READ_FREAD
char fread_char;
inline void fread_init()
{
fread_char = getchar();
}
inline int get_int()
{
int ret = 0;
while ((fread_char < '0') || (fread_char > '9'))
{
fread_char = getchar();
}
while ((fread_char >= '0') && (fread_char <= '9'))
{
ret = ret * 10 + fread_char - '0';
fread_char = getchar();
}
return ret;
}
inline char get_char()
{
while ((fread_char == ' ') || (fread_char == 'n'))
{
fread_char = getchar();
}
char ret = fread_char;
fread_char = getchar();
return ret;
}
#endif
inline void read(int &a)
{
#ifdef READ_FREAD
a = get_int();
#else
scanf("%d", &a);
#endif
}
inline void read(char &a)
{
#ifdef READ_FREAD
a = get_char();
#else
scanf("%c", &a);
#endif
}
struct discre_node
{
int val, id;
inline bool operator < (const discre_node &b) const
{
return val < b.val;
}
};
struct tree_node
{
int tot;
tree_node *l_child, *r_child;
inline tree_node *init()
{
l_child = r_child = 0;
return this;
}
};
tree_node recover_tree_node[MAXTREE];
tree_node *stack_recover_tree_node[MAXTREE];
int top_stack_recover_tree_node = MAXTREE;
inline void init_recover_tree_node()
{
for (int i = 0; i < MAXTREE; i++)
{
stack_recover_tree_node[i] = recover_tree_node + i;
}
}
inline tree_node *new_node()
{
return stack_recover_tree_node[--top_stack_recover_tree_node]->init();
}
inline void delete_node(tree_node *del_node)
{
stack_recover_tree_node[top_stack_recover_tree_node++] = del_node;
}
int n, m;
discre_node discre_tmp[MAXN + MAXM];
int tot_discre;
int discre_to_num[MAXN + MAXM];
int max_discre;
char op_string;
int discre[MAXN];
int cases;
int op[MAXN], op_i[MAXM], op_j[MAXM], op_k[MAXM];
tree_node *interval[MAXN];
inline void tree_insert(int root, const int val)
{
tree_node *tmp = interval[root];
tree_node **last_tmp = interval + root;
int l = 1, r = max_discre, mid;
while (l < r)
{
if (tmp == NULL)
{
*last_tmp = tmp = new_node();
tmp->tot = 1;
}
else
{
tmp->tot++;
}
mid = (l + r) >> 1;
if (val <= mid)
{
last_tmp = &tmp->l_child;
tmp = tmp->l_child;
r = mid;
}
else
{
last_tmp = &tmp->r_child;
tmp = tmp->r_child;
l = mid + 1;
}
}
if (tmp == NULL)
{
*last_tmp = tmp = new_node();
tmp->tot = 1;
}
else
{
tmp->tot++;
}
}
inline void tree_delete(int root, const int val)
{
tree_node *tmp = interval[root];
if (tmp == NULL)
{
return;
}
tree_node **last_tmp = interval + root;
int l = 1, r = max_discre, mid;
while (l < r)
{
tmp->tot--;
if (tmp->tot == 0)
{
delete_node(tmp);
*last_tmp = NULL;
}
mid = (l + r) >> 1;
if (val <= mid)
{
last_tmp = &tmp->l_child;
tmp = tmp->l_child;
r = mid;
}
else
{
last_tmp = &tmp->r_child;
tmp = tmp->r_child;
l = mid + 1;
} //我知道这样写不好。。但是不管了
}
if (tmp != NULL)
{
tmp->tot--;
if (tmp->tot == 0)
{
delete_node(tmp);
*last_tmp = NULL;
}
}
}
inline int tree_left_size(tree_node *query_node)
{
if (query_node == NULL)
{
return 0;
}
if (query_node->l_child == NULL)
{
return 0;
}
return query_node->l_child->tot;
}
inline int lowerbit(const int x)
{
return x & (-x);
}
inline void interval_insert(int l, const int val)
{
while (l <= n)
{
tree_insert(l, val);
l += lowerbit(l);
}
}
inline void interval_delete(int l, const int val)
{
while (l <= n)
{
tree_delete(l, val);
l += lowerbit(l);
}
}
tree_node *tmp_add[MAXTMP];
int tot_tmp_add;
tree_node *tmp_minus[MAXTMP];
int tot_tmp_minus;
inline int interval_query(int l, int r, const int k)
{
tot_tmp_add = tot_tmp_minus = 0;
while (r > 0)
{
tmp_add[tot_tmp_add++] = interval[r];
r -= lowerbit(r);
}
l--;
while (l > 0)
{
tmp_minus[tot_tmp_minus++] = interval[l];
l -= lowerbit(l);
}
int binary_l = 1, binary_r = max_discre, mid, tot_left;
int tot_length = 0;
while (binary_l < binary_r)
{
mid = (binary_l + binary_r) >> 1;
tot_left = 0;
for (int i = 0; i < tot_tmp_add; i++)
{
tot_left += tree_left_size(tmp_add[i]);
}
for (int i = 0; i < tot_tmp_minus; i++)
{
tot_left -= tree_left_size(tmp_minus[i]);
}
if (tot_length + tot_left >= k)
{
for (int i = 0; i < tot_tmp_minus; i++)
{
if (tmp_minus[i] != NULL)
{
tmp_minus[i] = tmp_minus[i]->l_child;
}
}
for (int i = 0; i < tot_tmp_add; i++)
{
if (tmp_add[i] != NULL)
{
tmp_add[i] = tmp_add[i]->l_child;
}
}
binary_r = mid;
}
else
{
for (int i = 0; i < tot_tmp_minus; i++)
{
if (tmp_minus[i] != NULL)
{
tmp_minus[i] = tmp_minus[i]->r_child;
}
}
for (int i = 0; i < tot_tmp_add; i++)
{
if (tmp_add[i] != NULL)
{
tmp_add[i] = tmp_add[i]->r_child;
}
}
binary_l = mid + 1;
tot_length += tot_left;
}
}
return binary_l;
}
#ifndef LOCAL_SIMP
int main()
{
#ifdef LOCAL_TIME
long long start_time_ = clock();
#endif
#ifdef READ_FILE
freopen("1901.in", "r", stdin);
#ifndef STD_DEBUG
freopen("1901.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
fread_init();
#endif
init_recover_tree_node();
read(cases);
while (cases--)
{
top_stack_recover_tree_node = MAXTREE;
init_recover_tree_node();
memset(interval, 0, sizeof(interval));
read(n);
read(m);
for (int i = 0; i < n; i++)
{
read(discre_tmp[i].val);
discre_tmp[i].id = i;
}
tot_discre = n;
for (int i = 0; i < m; i++)
{
read(op_string);
if (op_string == 'Q')
{
op[i] = 1;
read(op_i[i]);
read(op_j[i]);
read(op_k[i]);
}
else
{
op[i] = 2;
read(op_i[i]);
read(discre_tmp[tot_discre].val);
discre_tmp[tot_discre++].id = n + i;
}
}
std::sort(discre_tmp, discre_tmp + tot_discre);
max_discre = 0;
for (int i = 0; i < tot_discre; i++)
{
if ((i == 0) || (discre_tmp[i - 1] < discre_tmp[i]))
{
discre_to_num[++max_discre] = discre_tmp[i].val;
}
if (discre_tmp[i].id < n)
{
discre[discre_tmp[i].id] = max_discre;
}
else
{
op_k[discre_tmp[i].id - n] = max_discre;
}
}
for (int i = 0; i < n; i++)
{
interval_insert(i + 1, discre[i]);
}
for (int i = 0; i < m; i++)
{
#ifdef LOCAL_DEBUG
if (i == 6)
{
printf("");
}
#endif
if (op[i] == 1)
{
printf("%dn", discre_to_num[interval_query(op_i[i], op_j[i], op_k[i])]);
}
else if (op[i] == 2)
{
interval_delete(op_i[i], discre[op_i[i] - 1]);
interval_insert(op_i[i], op_k[i]);
discre[op_i[i] - 1] = op_k[i];
}
}
}
#ifdef LOCAL_TIME
printf("run time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
fclose(stdin);
#ifndef STD_DEBUG
fclose(stdout);
#endif
#endif
return 0;
}
#else
int a[MAXN];
int sort_tmp[MAXN];
//int op[MAXN], op_i[MAXN], op_j[MAXN], op_k[MAXN];
int main()
{
const int N = 50000;
const int M = 10000;
const int BASE = 4;
const int RAND_BASE = 23104;
freopen("1901.in", "w", stdout);
srand(RAND_BASE);
printf("%dn", BASE);
for (int j = 0; j < BASE; j++)
{
printf("%d %dn", N, M);
for (int i = 0; i < N; i++)
{
printf("%d ", a[i] = rand());
}
printf("n");
for (int i = 0; i < M; i++)
{
op[i] = rand() % 2;
if (op[i] == 0)
{
printf("Q ");
op_i[i] = rand() % N + 1;
op_j[i] = op_i[i] + rand() % (N - op_i[i] + 1);
op_k[i] = rand() % (op_j[i] - op_i[i] + 1) + 1;
printf("%d %d %dn", op_i[i], op_j[i], op_k[i]);
}
else if (op[i] == 1)
{
printf("C ");
op_i[i] = rand() % N + 1;
op_k[i] = rand();
printf("%d %dn", op_i[i], op_k[i]);
}
}
}
fclose(stdout);
/*freopen("1901std.out", "w", stdout);
for (int i = 0; i < M; i++)
{
if (op[i] == 1)
{
a[op_i[i] - 1] = op_k[i];
}
else if (op[i] == 0)
{
memcpy(sort_tmp, a + op_i[i] - 1, (op_j[i] - op_i[i] + 1) * sizeof(int));
std::sort(sort_tmp, sort_tmp + op_j[i] - op_i[i] + 1);
printf("%dn", sort_tmp[op_k[i] - 1]);
}
}
fclose(stdout);*/
}
#endif
心情好的话再写个分块试试能不能水过。
Read other posts