9 minutes
[BZOJ3196][TYVJ1730]二逼平衡树（分块·伪）
平衡树三道题终于全A了。为什么说分块是伪呢，毕竟这是平衡树的题目，然后我用了分块（我弱啊，不会树套）。听说TY上还有大爷直接用sort A掉了，这算什么嘛，还有话说我BZOJ上A掉的代码在TY上死活RE30分，还WA了两个点。不管了。。
分块的话没什么好说的，就一个带修改的区间第K大，直接上代码
//tyvj 1730.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
//#define LOCAL
#define READ_FREAD
//#define READ_FILE
//#define VISUAL_STUDIO
const int MAXS = 5 * 1024 * 1024;
const int MAXN = 100000;
const int MAX_LENGTH_BLOCK = 500;
#ifdef LOCAL
#define LOCAL_TIME
#define LOCAL_DEBUG
//#define LOCAL_DEBUG_NOUT
//#define LOCAL_SIMP
#endif
#ifdef LOCAL_TIME
#include<ctime>
#endif
#ifdef VISUAL_STUDIO
#pragma warning(disable:4996)
#endif
#ifdef READ_FREAD
//char fread_string[MAXS];
//char *fread_point = fread_string;
char fread_point;
inline int get_int()
{
int ret = 0;
bool sign = false;
while ((fread_point < '0') || (fread_point > '9') || (fread_point == '-'))
{
if (fread_point == '-')
{
sign = true;
}
else
{
sign = false;
}
fread_point = getchar();
}
while ((fread_point >= '0') && (fread_point <= '9'))
{
ret = ret * 10 + fread_point - '0';
fread_point = getchar();
}
if (sign)
{
return -ret;
}
return ret;
}
#endif
inline void read(int &a)
{
#ifdef READ_FREAD
a = get_int();
#else
scanf("%d", &a);
#endif
}
typedef long long ll;
struct block_node
{
int val[MAX_LENGTH_BLOCK];
int order[MAX_LENGTH_BLOCK];
int size;
};
inline int min(const int a, const int b)
{
if (a == -1)
{
return b;
}
if (b == -1)
{
return a;
}
return a < b ? a : b;
}
block_node block_list[MAXN / MAX_LENGTH_BLOCK];
const int OP_Q_RANK = 1;
const int OP_Q_NUM = 2;
const int OP_CHANGE = 3;
const int OP_PREV = 4;
const int OP_NEXT = 5;
int n, m;
int init_read[MAXN];
int op, op_l, op_r, k;
int num_max = -1, num_min = -1;
inline void block_init(const int n)
{
for (int i = 0, j = 0; j < n; i++, j += MAX_LENGTH_BLOCK)
{
for (int t = j; t < j + MAX_LENGTH_BLOCK, t < n; t++)
{
block_list[i].val[t - j] = init_read[t];
}
block_list[i].size = std::min(MAX_LENGTH_BLOCK, n - j);
memcpy(block_list[i].order, block_list[i].val, block_list[i].size * sizeof(int));
std::sort(block_list[i].order, block_list[i].order + block_list[i].size);
}
}
inline int block_find(int &x)
{
int ret = x / MAX_LENGTH_BLOCK;
x %= MAX_LENGTH_BLOCK;
return ret;
}
inline int block_smaller(const int block, const int val)
{
int l = 0, r = block_list[block].size;
int mid;
while (l + 1 < r)
{
mid = (l + r) >> 1;
if (block_list[block].order[mid] >= val)
{
r = mid;
}
else
{
l = mid + 1;
}
}
while ((l < block_list[block].size) && (block_list[block].order[l] < val))
{
l++;
}
return l;
}
inline int block_query_smaller(const int block, const int l, const int r, const int val)
{
int ret = 0;
for (int i = l; i <= r; i++)
{
if (block_list[block].val[i] < val)
{
ret++;
}
}
return ret;
}
inline int block_b_smaller(const int block, const int val)
{
int binary_l = 0, binary_r = block_list[block].size, mid;
while (binary_l + 1 < binary_r)
{
mid = (binary_l + binary_r) >> 1;
if (block_list[block].order[mid] >= val)
{
binary_r = mid;
}
else
{
binary_l = mid;
}
}
/*while ((binary_l < block_list[block].size - 1) && (block_list[block].order[binary_l + 1] < val))
{
binary_l++;
}*/
while ((binary_l > 0) && (block_list[block].order[binary_l] >= val))
{
binary_l--;
}
if (block_list[block].order[binary_l] >= val)
{
return -1;
}
return block_list[block].order[binary_l];
}
inline int block_query_b_smaller(const int block, const int l, const int r, const int val)
{
int max_num = -1;
for (int i = l; i <= r; i++)
{
if (block_list[block].val[i] < val)
{
max_num = std::max(max_num, block_list[block].val[i]);
}
}
return max_num;
}
inline int block_s_bigger(const int block, const int val)
{
int binary_l = 0, binary_r = block_list[block].size, mid;
while (binary_l + 1 < binary_r)
{
mid = (binary_l + binary_r) >> 1;
if (block_list[block].order[mid] > val)
{
binary_r = mid;
}
else
{
binary_l = mid;
}
}
while ((binary_l < block_list[block].size - 1) && (block_list[block].order[binary_l] <= val))
{
binary_l++;
}
if (block_list[block].order[binary_l] <= val)
{
return -1;
}
return block_list[block].order[binary_l];
}
inline int block_query_s_bigger(const int block, const int l, const int r, const int val)
{
int min_num = -1;
for (int i = l; i <= r; i++)
{
if (block_list[block].val[i] > val)
{
min_num = min(min_num, block_list[block].val[i]);
}
}
return min_num;
}
inline int block_query_rank(int l, int r, const int val)
{
int block_l = block_find(l);
int block_r = block_find(r);
if (block_l == block_r)
{
if ((l == 0) && (r == block_list[block_l].size - 1))
{
return block_smaller(block_l, val) + 1;
}
else
{
return block_query_smaller(block_l, l, r, val) + 1;
}
}
else
{
int ret = 0;
if (l == 0)
{
ret += block_smaller(block_l, val);
}
else
{
ret += block_query_smaller(block_l, l, block_list[block_l].size - 1, val);
}
if (r == block_list[block_l].size - 1)
{
ret += block_smaller(block_r, val);
}
else
{
ret += block_query_smaller(block_r, 0, r, val);
}
for (int i = block_l + 1; i < block_r; i++)
{
ret += block_smaller(i, val);
}
return ret + 1;
}
}
inline int block_query_num(const int l, const int r, const int k)
{
int binary_l = num_min, binary_r = num_max, mid;
int ret;
while (binary_l < binary_r)
{
mid = (binary_l + binary_r) >> 1;
ret = block_query_rank(l, r, mid) - 1;
if ((ret < k) && (block_query_rank(l, r, mid + 1) > k))
{
return mid;
}
else if (ret < k)
{
binary_l = mid + 1;
}
else
{
binary_r = mid - 1;
}
}
return binary_l;
}
inline void block_change(int pt, const int val)
{
int block_pt = block_find(pt);
if (block_list[block_pt].val[pt] == val)
{
return;
}
int binary_l = 0, binary_r = block_list[block_pt].size, mid;
int loop = -1;
/*while (binary_l + 1 < binary_r)
{
mid = (binary_l + binary_r) >> 1;
if (block_list[block_pt].order[mid] == block_list[block_pt].val[pt])
{
loop = mid;
break;
}
else if (block_list[block_pt].order[mid] > block_list[block_pt].val[pt])
{
binary_l = mid;
}
else
{
binary_r = mid;
}
}*/
for (int i = 0; i < block_list[block_pt].size; i++)
{
if (block_list[block_pt].order[i] == block_list[block_pt].val[pt])
{
loop = i;
}
}
if (loop == -1)
{
loop = binary_l;
}
if (block_list[block_pt].val[pt] < val)
{
while ((loop + 1 < block_list[block_pt].size) && (block_list[block_pt].order[loop + 1] < val))
{
block_list[block_pt].order[loop] = block_list[block_pt].order[loop + 1];
loop++;
}
block_list[block_pt].order[loop] = val;
}
else
{
while ((loop > 0) && (block_list[block_pt].order[loop - 1] > val))
{
block_list[block_pt].order[loop] = block_list[block_pt].order[loop - 1];
loop--;
}
block_list[block_pt].order[loop] = val;
}
block_list[block_pt].val[pt] = val;
}
inline int block_prev(int l, int r, const int val)
{
int block_l = block_find(l);
int block_r = block_find(r);
if (block_l == block_r)
{
if ((l == 0) && (r == block_list[block_l].size - 1))
{
return block_b_smaller(block_l, val);
}
else
{
return block_query_b_smaller(block_l, l, r, val);
}
}
else
{
int ret;
if (l == 0)
{
ret = block_b_smaller(block_l, val);
}
else
{
ret = block_query_b_smaller(block_l, l, block_list[block_l].size - 1, val);
}
if (r == block_list[block_r].size - 1)
{
ret = std::max(ret, block_b_smaller(block_r, val));
}
else
{
ret = std::max(ret, block_query_b_smaller(block_r, 0, r, val));
}
for (int i = block_l + 1; i < block_r; i++)
{
ret = std::max(ret, block_b_smaller(i, val));
//ret = std::max(ret, block_query_b_smaller(i, 0, block_list[block_l].size - 1, val));
}
return ret;
}
}
inline int block_next(int l, int r, const int val)
{
int block_l = block_find(l);
int block_r = block_find(r);
if (block_l == block_r)
{
if ((l == 0) && (r == block_list[block_l].size - 1))
{
return block_s_bigger(block_l, val);
}
else
{
return block_query_s_bigger(block_l, l, r, val);
}
}
else
{
int ret;
if (l == 0)
{
ret = block_s_bigger(block_l, val);
}
else
{
ret = block_query_s_bigger(block_l, l, block_list[block_l].size - 1, val);
}
if (r == block_list[block_r].size - 1)
{
ret = min(ret, block_s_bigger(block_r, val));
}
else
{
ret = min(ret, block_query_s_bigger(block_r, 0, r, val));
}
for (int i = block_l + 1; i < block_r; i++)
{
ret = min(ret, block_s_bigger(i, val));
}
return ret;
}
}
#ifdef LOCAL_DEBUG
inline void checker()
{
int loop = 0;
int pt = 0;
for (int i = 0; i < n; i++)
{
if (pt >= block_list[loop].size)
{
pt = 0;
loop++;
}
printf("%d ", block_list[loop].val[pt]);
pt++;
}
printf("n");
}
#endif
#ifndef LOCAL_SIMP
int main()
{
#ifdef LOCAL_TIME
ll start_time_ = clock();
#endif
#ifdef READ_FILE
freopen("input4.in", "r", stdin);
freopen("3196.out", "w", stdout);
#endif
fread_point = getchar();
read(n);
read(m);
for (int i = 0; i < n; i++)
{
read(init_read[i]);
num_max = std::max(num_max, init_read[i]);
num_min = min(num_min, init_read[i]);
}
block_init(n);
for (int i = 0; i < m; i++)
{
read(op);
#ifdef LOCAL_DEBUG
printf("%d %d ", i, op);
if (i == 446)
{
//printf("DEBUG ");
}
#endif
if (op == OP_Q_RANK)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
#ifndef LOCAL_DEBUG_NOUT
printf("%dn", block_query_rank(op_l - 1, op_r - 1, k));
#endif
}
else if (op == OP_Q_NUM)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
#ifndef LOCAL_DEBUG_NOUT
printf("%dn", block_query_num(op_l - 1, op_r - 1, k));
#endif
}
else if (op == OP_CHANGE)
{
read(op_l);
read(k);
num_max = std::max(num_max, k);
num_min = min(num_min, k);
#ifdef LOCAL_DEBUG
printf("%d %dn", op_l, k);
#endif
block_change(op_l - 1, k);
}
else if (op == OP_PREV)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
//#ifndef LOCAL_DEBUG_NOUT
printf("%dn", block_prev(op_l - 1, op_r - 1, k));
//#endif
}
else if (op == OP_NEXT)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
//#ifndef LOCAL_DEBUG_NOUT
printf("%dn", block_next(op_l - 1, op_r - 1, k));
//#endif
}
#ifdef LOCAL_DEBUG_NOUT
checker();
#endif
}
#ifdef LOCAL_TIME
printf("run time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
#else
int main()
{
freopen("3196.in", "r", stdin);
freopen("3196simp.out", "w", stdout);
fread_point = getchar();
read(n);
read(m);
for (int i = 0; i < n; i++)
{
read(init_read[i]);
num_max = std::max(num_max, init_read[i]);
num_min = min(num_min, init_read[i]);
}
for (int i = 0; i < m; i++)
{
read(op);
#ifdef LOCAL_DEBUG
printf("%d %d ", i, op);
#endif
if (op == OP_Q_RANK)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
}
else if (op == OP_Q_NUM)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
}
else if (op == OP_CHANGE)
{
read(op_l);
read(k);
num_max = std::max(num_max, k);
num_min = min(num_min, k);
#ifdef LOCAL_DEBUG
printf("%d %dn", op_l, k);
#endif
init_read[op_l - 1] = k;
}
else if (op == OP_PREV)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
int max_num = -1;
for (int i = op_l - 1; i < op_r; i++)
{
if (init_read[i] < k)
{
max_num = std::max(max_num, init_read[i]);
}
}
printf("%dn", max_num);
}
else if (op == OP_NEXT)
{
read(op_l);
read(op_r);
read(k);
#ifdef LOCAL_DEBUG
printf("%d %d %dn", op_l, op_r, k);
#endif
int min_num = -1;
for (int i = op_l - 1; i < op_r; i++)
{
if (init_read[i] > k)
{
min_num = min(min_num, init_read[i]);
}
}
printf("%dn", min_num);
}
for (int j = 0; j < n; j++)
{
printf("%d ", init_read[j]);
}
printf("n");
}
fclose(stdin);
fclose(stdout);
}
#endif
Read other posts