翻车笔记_ [Poi2014]Couriers [主席树, 翻车]

60道留念? REfun的一半留念? 我太菜了留念?

这年头刷水真不容易…重要的翻车说三遍:

数组不要开太大!!!!!!!!!

数组不要开太大!!!!!!!!!

数组不要开太大!!!!!!!!!

懵逼的 题目

ZKJ的OJ

扯淡的 题解

裸的主席树

唯一有必要说一句的就是

我写完了之后, 样例始终过不去, 调试发现我写的没有任何问题, 但是ins()的时候有一个值始终不对, 然后就连锁反应影响了后面的值

任何发现我的数组: MAXN << 32

其实我想写MAXN * 32的…

然后卡了半天空间…在zzzyc的帮助下底下的代码是可以过的…

沙茶的 代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**************************************************************
Problem: 3524
User: Cansult
Language: C++
Result: Accepted
Time:8088 ms
Memory:198556 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
using namespace std;
struct node
{
int le, ri, zh, ls, rs;
}b[MAXN*20];
int root[MAXN], cntb, n, m;
void push_up(int dq)
{ b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh; }
void ins(int& dq, int pre, int le, int ri, int zh)
{
dq = ++cntb;
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].zh = b[pre].zh + 1;
return ;
}
int mi = (le + ri) >> 1;
if (zh > mi)
b[dq].ls = b[pre].ls, ins(b[dq].rs, b[pre].rs, mi + 1, ri, zh);
else
b[dq].rs = b[pre].rs, ins(b[dq].ls, b[pre].ls, le, mi, zh);
push_up(dq);
}
int cx(int lt, int rt, int k)
{
if (b[rt].le == b[rt].ri)
{
if (b[rt].zh - b[lt].zh > k)
return b[rt].le;
else
return 0;
}
if (b[b[rt].ls].zh - b[b[lt].ls].zh > k)
return cx(b[lt].ls, b[rt].ls, k);
else if (b[b[rt].rs].zh - b[b[lt].rs].zh > k)
return cx(b[lt].rs, b[rt].rs, k);
else
return 0;
}
int main()
{
// cout << "Hello world!" << endl;
// freopen("in.in", "r", stdin);
b[0].ls = b[0].rs = b[0].zh = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
int srx;
scanf("%d", &srx);
ins(root[i], root[i - 1], 1, n, srx);
}
for (int i = 1; i <= m; i++)
{
int srl, srr;
scanf("%d%d", &srl, &srr);
printf("%d\n", cx(root[srl - 1], root[srr], (srr - srl + 1) >> 1));
}
return 0;
}

/*
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
*/

By 沙茶 Cansult