实用数据结构(二)

这篇博文主要介绍一下fenwick树状数组
线段树

树状数组

fenwick01
fenwick02
fenwick03

HDU2492

把待求的前缀和exist[1] + exist[2] + … + exist[n]
用fenwick树封装
fenwick成员函数中, x表示exist的下标

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
86
const int maxn = 200000 + 10;

inline int lowbit(int x) {
return x & (-x);
}

int cnt1[maxn], cnt2[maxn];
int A[maxn];

void init() {
Set(cnt1, 0);
Set(cnt2, 0);
}

class Fenwick {
public:
vector<int> exist;
int n;

void clear() {
fill(exist.begin(), exist.end(), 0);
}

void resize(int n) {
this->n = n;
exist.resize(n);
}

int sum(int x) {
int ret = 0;
while (x > 0) {
ret += exist[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
exist[x] += d;
x += lowbit(x);
}
}
};

Fenwick fwick;

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
init();
int maxa = 0;
int n;
scanf("%d", &n);
_rep(i, 1, n) {
scanf("%d", &A[i]);
maxa = max(maxa, A[i]);
}

fwick.resize(maxa);
fwick.clear();

_rep(i, 1, n) {
int val = A[i];
fwick.add(val, 1);
cnt1[i] = fwick.sum(val - 1);
}

fwick.clear();
_forDown(i, n, 1) {
int val = A[i];
fwick.add(val, 1);
cnt2[i] = fwick.sum(val - 1);
//debug(cnt2[i]);
}

llong ans = 0;
_rep(i, 1, n) {
ans += ((llong)cnt2[i] * (llong)(i - 1 - cnt1[i]) + (llong)cnt1[i] * (llong)(n - i - cnt2[i]));
}
printf("%lld\n", ans);
}
}

树状数组求解区间问题(一)

CH242
CH248

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
const int maxm = 100000 + 10;
const int maxn = 100000 + 10;
int n, m;

llong A[maxn];

void init() {
Set(A, 0);
}

class Fenwick {
public:
int n;
vector<int> h;

void resize(int n) {
this->n = n;
h.resize(n);
}

void clear() {
fill(h.begin(), h.end(), 0);
}

int sum(int x) {
int ret = 0;
while (x) {
ret += h[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
h[x] += d;
x += lowbit(x);
}
}
};

Fenwick fwick;

int main() {
freopen("input.txt", "r", stdin);
init();
cin >> n >> m;

_rep(i, 1, n) cin >> A[i];
//debug(A[n]);

//fflush(stdin);
fwick.clear();
fwick.resize(maxn);

//getchar();
_for(i, 0, m) {
char ch;
cin >> ch;
//debug(ch);
if(ch == 'C') {
//
int l, r, d;
cin >> l >> r >> d;
//debug(l);

fwick.add(l, d);
fwick.add(r + 1, -d);
}
else {
//
int x;
cin >> x;
cout << A[x] + (llong)fwick.sum(x) << endl;
}
}
}

树状数组求解区间问题(二)

POJ3468

POJ3468

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
const int maxn = 100000 + 10;
int n, m;
int A[maxn];
llong sum[maxn];

void init() {
Set(A, 0);
Set(sum, 0);
}

class Fwick {
public:
llong C[2][maxn];
int n;

void clear() {
memset(C, 0, sizeof(C));
}

void resize(int n) {
this->n = n;
}

llong ask(int k, int x) {
llong ret = 0;
while (x) {
ret += C[k][x];
x -= lowbit(x);
}
return ret;
}

void add(int k, int x, int d) {
while (x <= n) {
C[k][x] += d;
x += lowbit(x);
}
}
};

Fwick fwick;

int main() {
freopen("input.txt", "r", stdin);
init();

scanf("%d%d", &n, &m);
_rep(i, 1, n) {
scanf("%d", &A[i]);
sum[i] = sum[i - 1] + A[i];
}

fwick.clear();
fwick.resize(n);

_for(i, 0, m) {
char op[2];
scanf("%s", op);

if(op[0] == 'C') {
//
int l, r, d;
scanf("%d%d%d", &l, &r, &d);

fwick.add(0, l, d);
fwick.add(0, r + 1, -d);

fwick.add(1, l, l * d);
fwick.add(1, r + 1, -(r + 1) * d);
}
else {
//
int l, r;
scanf("%d%d", &l, &r);
llong ans = sum[r] + (r + 1) * fwick.ask(0, r) - fwick.ask(1, r);
ans -= (sum[l - 1] + l * fwick.ask(0, l - 1) - fwick.ask(1, l - 1));
printf("%lld\n", ans);
}
}
}

树状数组解决区间第k大数问题

树状数组+二分
POJ2182
POJ2182

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
const int maxn = 100000 + 10;
int A[maxn], n, h[maxn];

void init() {
Set(A, 0);
Set(h, 0);
}

class Fwick {
public:
vector<int> C;
int n;

void resize(int n) {
this->n = n;
C.resize(n);
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int sum(int x) {
int ret = 0;
while (x) {
ret += C[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
C[x] += d;
x += lowbit(x);
}
}

int find(int l, int r, int val) {
// find sum(p) == val
while (l < r) {
int mid = (l + r) >> 1;
if(sum(mid) < val) l = mid + 1;
else r = mid;
}
return l;
}
};

Fwick fwick;

int main() {
freopen("input.txt", "r", stdin);
init();

scanf("%d", &n);

fwick.resize(n);
fwick.clear();

fwick.add(1, 1);
_rep(i, 2, n) {
scanf("%d", &A[i]);
fwick.add(i, 1);
}

_forDown(i, n, 1) {
int val = A[i] + 1;
h[i] = fwick.find(1, n, val);
fwick.add(h[i], -1);
}

_rep(i, 1, n) cout << h[i] << endl;
}

POJ2828

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
86
87
88
89
90
const int maxn = 200000 + 10;
int n;

class Peo {
public:
int p, v;
};

Peo peo[maxn];
int ans[maxn];

void init() {
Set(ans, 0);
}

class Fwick {
public:
vector<int> C;
int n;

void resize(int n) {
this->n = n;
C.resize(n);
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int sum(int x) {
int ret = 0;
while (x) {
ret += C[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
C[x] += d;
x += lowbit(x);
}
}

int find(int l, int r, int val) {
while (l < r) {
int mid = (l + r) >> 1;
if(sum(mid) < val) l = mid + 1;
else r = mid;
}
return l;
}
};

Fwick fwick;


int main() {
freopen("input.txt", "r", stdin);
while (~scanf("%d", &n)) {
//debug(n);
init();
fwick.resize(n);
fwick.clear();

_rep(i, 1, n) {
//debug(i);
scanf("%d%d", &peo[i].p, &peo[i].v);
//debug(peo[i].p);
//debug(peo[i].v);
fwick.add(i, 1);
}

_forDown(i, n, 1) {
int val = peo[i].p;
int pos = fwick.find(1, n, val + 1);
//debug(pos);

ans[pos] = peo[i].v;
fwick.add(pos, -1);

//debug(peo[i].v);
}
_rep(i, 1, n) {
if(i != n) printf("%d ", ans[i]);
else printf("%d\n", ans[i]);
}
}
}

树状数组处理栈(扩展域)

LA5902

LA5902

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
const int maxn = 100000 + 10;
int n, m;
int pos[maxn];

void init() {
Set(pos, 0);
}


class Fwick {
public:
vector<int> C;
int n;

void resize(int n) {
C.resize(n + 1);
this->n = n;
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int sum(int x) {
int ret = 0;
while (x) {
ret += C[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
C[x] += d;
x += lowbit(x);
}
}
};

Fwick fwick;

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
//init();

scanf("%d%d", &n, &m);

fwick.resize((maxn + 1) * 2);
fwick.clear();

int st = maxn;

_rep(i, 1, n) {
pos[i] = st + i;
fwick.add(pos[i], 1);
}

_for(i, 0, m) {
int x;
scanf("%d", &x);
printf("%d%c", fwick.sum(pos[x] - 1), i == m - 1 ? '\n' : ' ');

fwick.add(pos[x], -1);
pos[x] = --st;
fwick.add(pos[x], 1);
}
}
}

树状数组和康托尔排列

UVA11525
P11525
UVA11525

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
const int maxn = 50000 + 10;
int n;

class Fwick {
public:
vector<int> C;
int n;

void resize(int n) {
this->n = n;
C.resize(n + 1);
}

void clear() {
fill(C.begin(), C.end(), 0);
}

int sum(int x) {
int ret = 0;
while (x) {
ret += C[x];
x -= lowbit(x);
}
return ret;
}

void add(int x, int d) {
while (x <= n) {
C[x] += d;
x += lowbit(x);;
}
}

int find(int l, int r, int val) {
while (l < r) {
int mid = (l + r) >> 1;
if(sum(mid) < val) l = mid + 1;
else r = mid;
}
return l;
}
};

Fwick fwick;

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
scanf("%d", &n);
fwick.resize(n);
fwick.clear();

_rep(i, 1, n) fwick.add(i, 1);

_rep(i, 1, n) {
int x;
scanf("%d", &x);

int pos = fwick.find(1, n, x + 1);
printf("%d%c", pos, i == n ? '\n' : ' ');

fwick.add(pos, -1);
}
}
}

并查集练习

并查集和坐标离散化

BZOJ4195

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
const int maxn = 100000 + 10;

class Con {
public:
int i, j;
int e;
};

Con cons[maxn];
int n;

int pa[maxn * 2];
int arr[maxn * 2];

void init() {
_for(i, 0, maxn) pa[i] = i;
Set(arr, 0);
}

int find(int x) {
return x == pa[x] ? x : (pa[x] = find(pa[x]));
}

void discrete(int* arr, int m, int& n) {
sort(arr, arr + m);
n = unique(arr, arr + m) - arr;
}

int query(int* arr, int n, int x) {
return lower_bound(arr, arr + n, x) - arr;
}

void solve() {
int m = n * 2;
int n2 = 0;
discrete(arr, m, n2);

_rep(i, 0, n2) pa[i] = i;

_for(i, 0, n) {
int p = find(query(arr, n2, cons[i].i)), q = find(query(arr, n2, cons[i].j));
if(cons[i].e) pa[p] = q;
}

_for(i, 0, n) {
int p = find(query(arr, n2, cons[i].i)), q = find(query(arr, n2, cons[i].j));
if(!cons[i].e && p == q) {
printf("NO\n");
return;
}
}
printf("YES\n");
}

int main() {
freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);

while (T--) {
init();

scanf("%d", &n);
_for(i, 0, n) {
scanf("%d%d%d", &cons[i].i, &cons[i].j, &cons[i].e);

arr[i * 2] = cons[i].i;
arr[i * 2 + 1] = cons[i].j;
}

// then solve the problem
solve();

}
}

并查集+贪心

POJ1456

POJ1456

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
const int maxn = 10000 + 10;
int pa[maxn];
int n;

void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}

int find(int x) {
return x == pa[x] ? x : (pa[x] = find(pa[x]));
}

class Stuf {
public:
int prof, day;
bool operator< (const Stuf& rhs) const {
return prof > rhs.prof;
}
};

Stuf stufs[maxn];

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) != EOF) {

int maxd = 0;
_for(i, 0, n) {
scanf("%d%d", &stufs[i].prof, &stufs[i].day);
maxd = max(maxd, stufs[i].day);
}

sort(stufs, stufs + n);

initPa(maxd);
int ans = 0;
_for(i, 0, n) {
int d = find(stufs[i].day);
if(d) {
ans += stufs[i].prof;
pa[d] = d - 1;
}
}

printf("%d\n", ans);
}
}

并查集按秩压缩

并查集执行Union(int rootp, int rootq)操作之后
pa[rootp] = rootq
rootp及其后代元素都成为rootq的子节点
这个时候sz[rootq] += sz[rootp]

另外

1
std::ios::sync_with_stdio(false);

比scanf好用

CH4101

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
const int maxn = 30000 + 1;
int pa[maxn];
int d[maxn];
int sz[maxn];

void init() {
_for(i, 0, maxn) sz[i] = 1;
_for(i, 0, maxn) d[i] = 0;
}

void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}

int find(int x) {
if(x == pa[x]) return x;
int root = find(pa[x]);
d[x] += d[pa[x]];
return pa[x] = root;
}

void Union(int p, int q) {
pa[p] = q;
d[p] = sz[q];
sz[q] += sz[p];
}

int main() {
std::ios::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
int T;
cin >> T;

initPa(maxn);
init();
while (T--) {
char cmd;
cin >> cmd;

int i, j;
cin >> i >> j;
//debug(i);
//debug(j);

int p = find(i), q = find(j);
//debug(p);
//debug(q);

if(cmd == 'C') {
//
if(p == q) cout << abs(d[i] - d[j]) - 1 << endl;
else cout << "-1" << endl;
}
else {
//
Union(p, q);
}
}
}

并查集处理奇偶运算

POJ1733
POJ1733

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
const int maxn = 10000 + 10;

struct Query {
int l, r, ans;
};
Query query[maxn];

void discrete(int* arr, int n, int& n2) {
sort(arr + 1, arr + 1 + n);
n2 = unique(arr + 1, arr + 1 + n) - arr - 1;
}

int getid(int* arr, int n2, int x) {
return lower_bound(arr + 1, arr + 1 + n2, x) - arr;
}

int arr[maxn], n, m;
int pa[maxn], d[maxn];

void init() {
Set(arr, 0);
}

void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
_rep(i, 0, n) d[i] = 0;
}

int find(int x) {
if(x == pa[x]) return x;
int root = find(pa[x]);

d[x] ^= d[pa[x]];
return pa[x] = root;
}


int main() {
freopen("input.txt", "r", stdin);
std::ios::sync_with_stdio(false);

cin >> n >> m;

int k = 0;
_rep(i, 1, m) {
char str[5];
cin >> query[i].l >> query[i].r;

scanf("%s", str);
if(str[0] == 'o') query[i].ans = 1;
else query[i].ans = 0;

arr[++k] = query[i].l - 1;
arr[++k] = query[i].r;
}
discrete(arr, k, n);
//debug(n);
// [0, m - 1] is all query

initPa(n);
_rep(i, 1, m) {
int x = getid(arr, n, query[i].l - 1);
int y = getid(arr, n, query[i].r);
int p = find(x), q = find(y);

if(p == q) {
//
if( (d[x] ^ d[y]) != query[i].ans ) {
cout << i - 1 << endl;
return 0;
}
}
else {
pa[p] = q;
d[p] = d[x] ^ d[y] ^ query[i].ans;
}
}
cout << m << endl;
return 0;
}

并查集扩展域

POJ1733-02

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
const int maxn = (10000 + 1) * 2;

struct Query {
int l, r, ans;
};
Query query[maxn];

void discrete(int* arr, int n, int& n2) {
sort(arr + 1, arr + 1 + n);
n2 = unique(arr + 1, arr + 1 + n) - arr - 1;
}

int getid(int* arr, int n2, int x) {
return lower_bound(arr + 1, arr + 1 + n2, x) - arr;
}

int arr[maxn], n, m;
int pa[maxn];

void init() {
Set(arr, 0);
}

void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}

int find(int x) {
return x == pa[x] ? x : find(pa[x]);
}



int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

int k = 0;
_rep(i, 1, m) {
char str[5];
cin >> query[i].l >> query[i].r;
scanf("%s", str);

if(str[0] == 'o') query[i].ans = 1;
else query[i].ans = 0;

arr[++k] = query[i].l - 1;
arr[++k] = query[i].r;
}
discrete(arr, k, n);

initPa(n * 2);

_rep(i, 1, m) {
int x = getid(arr, n, query[i].l - 1);
int y = getid(arr, n, query[i].r);

int xodd = x, xeven = x + n;
int yodd = y, yeven = y + n;

if(query[i].ans == 0) {
if(find(xodd) == find(yeven)) {
cout << i - 1 << endl;
return 0;
}
pa[find(xodd)] = find(yodd);
pa[find(xeven)] = find(yeven);
}
else {
if(find(xodd) == find(yodd)) {
cout << i - 1 << endl;
return 0;
}
pa[find(xodd)] = find(yeven);
pa[find(xeven)] = find(yodd);
}
}
cout << m << endl;
}

扩展域多节点

POJ1182

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
const int maxn = 50000 + 10;

int pa[maxn * 3];
int n, k;

// usage: initPa(n * 3)
void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}

int find(int x) {
return x == pa[x] ? x : pa[x] = find(pa[x]);
}

// x: self x + n: eat x + 2n: enemy

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &k);

initPa(n * 3);
int ans = 0;

_for(i, 0, k) {
int cmd, x, y;
scanf("%d%d%d", &cmd, &x, &y);

if(cmd == 2 && (x == y)) {
ans++;
continue;
}

if(x > n || y > n) {
ans++;
continue;
}

if(cmd == 1) {
//
if((find(x + n) == find(y)) || (find(x) == find(y + n))) {
ans++;
continue;
}
}
if(cmd == 2) {
//
if((find(x) == find(y)) || (find(x) == find(y + n))) {
ans++;
continue;
}
}

if(cmd == 1) {
//
pa[find(x)] = find(y);
pa[find(x + n)] = find(y + n);
pa[find(x + n * 2)] = find(y + n * 2);
}
else if(cmd == 2) {
//
pa[find(x)] = find(y + n * 2);
pa[find(x + n)] = find(y);
pa[find(x + n * 2)] = find(y + n);
}
}

cout << ans << endl;
}

并查集删除与扩展域

CH4901

CH4901

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
const int maxn = 20000 + 10;
const int maxm = 100000 + 10;
int pa[maxn * 2];
int n, m;

void initPa(int n) {
_rep(i, 0,n) pa[i] = i;
}
// usage initPa(n * 2);

class Cfl {
public:
int x, y, val;

bool operator< (const Cfl& rhs) const {
return val > rhs.val;
}
};

Cfl cfl[maxm];

int find(int x) {
return x == pa[x] ? x : pa[x] = find(pa[x]);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);


_for(i, 0, m) {
scanf("%d%d%d", &cfl[i].x, &cfl[i].y, &cfl[i].val);
}

initPa(n * 2);

sort(cfl, cfl + m);

_for(i, 0, m) {
Cfl& cur = cfl[i];
//debug(cur.x);
if(find(cur.x) == find(cur.y)) {
printf("%d\n", cur.val);
return 0;
}
pa[find(cur.x)] = find(cur.y + n);
pa[find(cur.y)] = find(cur.x + n);
}
printf("0\n");
return 0;
}

POJ2912
POJ2912

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
const int maxn = 500 + 10;
const int maxm = 2000 + 10;

int pa[maxn * 3];

void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}
// usage: initPa(n * 3)
// self: x lower: x + n greater: x + n * 2

class Expr {
public:
int x;
char op;
int y;
};

Expr expr[maxm];
int n, m;
int line[maxm];

void init() {
Set(line, 0);
}

int find(int x) {
return x == pa[x] ? x : pa[x] = find(pa[x]);
}


bool conflict(const Expr& expr) {
int x = expr.x, y = expr.y;
char op = expr.op;
//debug(op);

if(op == '>') {
//puts("ok");
if((find(x) == find(y)) || (find(x) == find(y + n * 2))) return 1;

pa[find(x + n * 2)] = find(y);
pa[find(x)] = find(y + n);
pa[find(x + n)] = find(y + n * 2);
}

if(op == '<') {
//puts("ok");
if((find(x) == find(y)) || (find(x) == find(y + n))) return 1;

pa[find(x + n)] = find(y);
pa[find(x)] = find(y + n * 2);
pa[find(x + n * 2)] = find(y + n);
}

if(op == '=') {
//puts("ok");
if((find(x) == find(y + n)) || (find(x + n) == find(y))) return 1;

pa[find(x)] = find(y);
pa[find(x + n)] = find(y + n);
pa[find(x + n * 2)] = find(y + n * 2);
}

return 0;
}

void Rochambeau() {
//
_for(i, 0, m) scanf("%d%c%d", &expr[i].x, &expr[i].op, &expr[i].y);
//debug(expr[0].op);

init();

int cnt = 0, id = 0;
_for(i, 0, n) {
// i is judge
bool fail = 0;
_rep(k, 0, n * 3) pa[k] = k;

_for(j, 0, m) {
Expr cur = expr[j];

//debug(cur.x);
//debug(cur.y);
if(cur.x != i && cur.y != i && conflict(cur)) {
fail = 1;
if(j > line[i]) line[i] = j + 1;
break;
}
}

if(!fail) {
id = i;
cnt++;
}
}

//debug(cnt);
if(!cnt) puts("Impossible");
else if(cnt == 1) {
int ans = 0;
_for(i, 0, n) if(line[i] > ans) ans = line[i];
printf("Player %d can be determined to be the judge after %d lines\n", id, ans);
}
else puts("Can not determine");
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF) Rochambeau();
}