参考代码（吗？）

P3901 数列找不同

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
#include<bits/stdc++.h>
using namespace std;
int vis[100000 + 10], a[100000 + 10], sum;
void add(int x) {
	if (vis[a[x]] == 1)
		sum++;
	vis[a[x]]++;
}
void remove(int x) {
	vis[a[x]]--;
	if (vis[a[x]] == 1)
		sum--;
}
int n, Q, bel[100000 + 10];
struct query {
	int l, r, id; bool ans;
	friend bool operator<(const query& a, const query& b) {
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[100000 + 10];
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) bel[i] = ceil(sqrt(i));
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r, q[j].id = j;
	sort(q + 1, q + Q + 1);
	for (int i = q[1].l; i <= q[1].r; ++i) add(i);
	//cout << q[1].l << ' ' << q[1].r << ' ' << sum << endl;
	q[1].ans = sum == 0;
	for (int j = 2; j <= Q; ++j) {
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		q[j].ans = sum == 0;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << (q[i].ans ? "Yes" : "No") << endl;
	return 0;
}

P2709 小B的询问

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
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define __gcd gcd
#endif // !ONLINE_JUDGE
using namespace std;
int vis[500000 + 10], a[500000 + 10];
long long sum;
void add(int x) {
	sum -= (vis[a[x]] * 1ll) * vis[a[x]];
	vis[a[x]]++;
	sum += (vis[a[x]] * 1ll) * vis[a[x]];
}
void remove(int x) {
	sum -= (vis[a[x]] * 1ll) * vis[a[x]];
	vis[a[x]]--;
	sum += (vis[a[x]] * 1ll) * vis[a[x]];
}
int n, Q, bel[500000 + 10];
struct query {
	int l, r, id; long long ans;
	friend bool operator<(const query& a, const query& b) {
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[100000 + 10];
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	int k;
	cin >> n >> Q >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) bel[i] = ceil(sqrt(i));
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r, q[j].id = j;
	sort(q + 1, q + Q + 1);
	for (int i = q[1].l; i <= q[1].r; ++i) add(i);
	//cout << q[1].l << ' ' << q[1].r << ' ' << sum << endl;
	q[1].ans = sum;
	for (int j = 2; j <= Q; ++j) {
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		q[j].ans = sum;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}

P1494 [国家集训队] 小 Z 的袜子

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
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define __gcd gcd
#endif // !ONLINE_JUDGE
using namespace std;
int vis[100000 + 10], a[100000 + 10];
long long sum;
void add(int x) {
	sum -= (vis[a[x]] - 1ll) * vis[a[x]];
	vis[a[x]]++;
	sum += (vis[a[x]] - 1ll) * vis[a[x]];
}
void remove(int x) {
	sum -= (vis[a[x]] - 1ll) * vis[a[x]];
	vis[a[x]]--;
	sum += (vis[a[x]] - 1ll) * vis[a[x]];
}
int n, Q, bel[100000 + 10];
struct query {
	int l, r, id; string ans;
	friend bool operator<(const query& a, const query& b) {
		if (a.l > a.r) return false;
		if (b.l > b.r) return true;
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[100000 + 10];
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) bel[i] = ceil(sqrt(i));
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r, q[j].id = j;
	sort(q + 1, q + Q + 1);
	for (int i = q[1].l; i <= q[1].r; ++i) add(i);
	//cout << q[1].l << ' ' << q[1].r << ' ' << sum << endl;
	long long tmp = (q[1].r + 1ll - q[1].l) * (q[1].r - q[1].l);
	long long t = __gcd(tmp, sum);
	if (sum == 0 || tmp == 0) {
		q[1].ans = "0/1";
	}
	else
		q[1].ans = to_string(sum / t) + '/' + to_string(tmp / t);
	for (int j = 2; j <= Q; ++j) {
		if (q[j].l > q[j].r) {
			q[j].ans = "0/1";
			continue;
		}
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		tmp = (q[j].r + 1ll - q[j].l) * (q[j].r - q[j].l);
		t = __gcd(tmp, sum);
		if (sum == 0 || tmp == 0) {
			q[j].ans = "0/1";
			continue;
		}
		q[j].ans = to_string(sum / t) + '/' + to_string(tmp / t);
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}

P4462 [CQOI2018] 异或序列

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
#include<bits/stdc++.h>
using namespace std;
long long vis[100000 + 10], a[100000 + 10], k;
long long sum;
void add(int x) {
	sum -= k ? vis[a[x]] * vis[a[x] ^ k] : (vis[a[x]]) * (vis[a[x]] - 1) / 2;
	vis[a[x]]++;
	sum += k ? vis[a[x]] * vis[a[x] ^ k] : (vis[a[x]]) * (vis[a[x]] - 1) / 2;
}
void remove(int x) {
	sum -= k ? vis[a[x]] * vis[a[x] ^ k] : (vis[a[x]]) * (vis[a[x]] - 1) / 2;
	vis[a[x]]--;
	sum += k ? vis[a[x]] * vis[a[x] ^ k] : (vis[a[x]]) * (vis[a[x]] - 1) / 2;
}
int n, Q, bel[100000 + 10];
struct query {
	int l, r, id; long long ans;
	friend bool operator<(const query& a, const query& b) {
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[100000 + 10];
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] ^= a[i - 1];
	int t1 = 1, t2 = pow(n, 0.5), t3 = 1;
	for (int i = 1; i <= n; ++i) {
		bel[i] = t3;
		if (t1 == t2) t1 = 1, t3++;
		t1++;
	}
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r, q[j].id = j, q[j].l--;
	sort(q + 1, q + Q + 1);
	q[0].l = 1;
	for (int j = 1; j <= Q; ++j) {
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		q[j].ans = sum;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}

P3709 大爷的字符串题

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
#include<bits/stdc++.h>
using namespace std;
int vis[200000 + 10], a[200000 + 10], sum, viss[200000 + 10];
void add(int x) {
	viss[vis[a[x]]]--;
	vis[a[x]]++;
	viss[vis[a[x]]]++;
	sum = max(sum, vis[a[x]]);
}
void remove(int x) {
	viss[vis[a[x]]]--;
	if (vis[a[x]] == sum && !viss[vis[a[x]]]) sum--;
	vis[a[x]]--;
	viss[vis[a[x]]]++;
}
int n, Q, bel[200000 + 10];
struct query {
	int l, r, id; int ans;
	friend bool operator<(const query& a, const query& b) {
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[200000 + 10];
vector<int>tmpp;
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i], tmpp.emplace_back(a[i]);
	sort(tmpp.begin(), tmpp.end());
	tmpp.erase(unique(tmpp.begin(), tmpp.end()), tmpp.end());
	for (int i = 1; i <= n; ++i) a[i] = lower_bound(tmpp.begin(), tmpp.end(), a[i]) - tmpp.begin() + 1;
	for (int i = 1; i <= n; ++i) bel[i] = ceil(sqrt(i));
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r, q[j].id = j;
	sort(q + 1, q + Q + 1);
	for (int i = q[1].l; i <= q[1].r; ++i) add(i);
	//cout << q[1].l << ' ' << q[1].r << ' ' << sum << endl;
	q[1].ans = sum;
	for (int j = 2; j <= Q; ++j) {
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		q[j].ans = sum;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << -q[i].ans << endl;
	return 0;
}

P1903 [国家集训队] 数颜色 / 维护队列

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
#include<bits/stdc++.h>
using namespace std;
int vis[1000000 + 10], a[133333 + 10], sum, chg[133333 + 10], pos[133333 + 10];
int n, Q, bel[133333 + 10];
struct query {
	int l, r, id, t; int ans;
	friend bool operator<(const query& a, const query& b) {
		return
			bel[a.l] == bel[b.l] ?
			bel[a.r] == bel[b.r] ?
			a.t < b.t :
			bel[a.l] % 2 == 1 ?
			bel[a.r] < bel[b.r] :
			bel[a.r] > bel[b.r]
			: bel[a.l] < bel[b.l];
	}
}q[133333 + 10];
void add(const int& x) {
	sum += vis[a[x]]++ >= 1;
}
void remove(const int& x) {
	sum -= --vis[a[x]] >= 1;
}
void upt(int& x, const int& j) {
	x++;
	if (q[j].l <= pos[x] && pos[x] <= q[j].r) remove(pos[x]), add((swap(a[pos[x]], chg[x]), pos[x]));
	else swap(a[pos[x]], chg[x]);
}
void dnt(int& x, const int& j) {
	if (q[j].l <= pos[x] && pos[x] <= q[j].r) remove(pos[x]), add((swap(a[pos[x]], chg[x]), pos[x]));
	else swap(a[pos[x]], chg[x]);
	x--;
}
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	int t1 = 1, t2 = pow(n, 0.666), t3 = 1;
	for (int i = 1; i <= n; ++i) {
		bel[i] = t3;
		if (t1 == t2) t1 = 1, t3++;
		t1++;
	}
	int t4 = 1;
	for (int j = 1; j <= Q; ++j) {
		static char opt;
		cin >> opt >> q[j].l >> q[j].r;
		if (opt == 'R') {
			++t4;
			chg[t4] = q[j].r;
			pos[t4] = q[j].l;
			swap(a[pos[t4]], chg[t4]);
			j--, Q--;
			continue;
		}
		q[j].id = j; q[j].t = t4;
	}
	sort(q + 1, q + Q + 1);
	//for (int i = 1; i <= Q; ++i) cout << q[i].l << ' ' << q[i].r << ' ' << q[i].t << endl;
	//for (int i = 2; i <= t4; ++i) cout << i << ':' << pos[i] << ' ' << chg[i] << ' ' << bef[i] << endl;
	q[0].t = t4;
	for (int j = 1; j <= Q; ++j) {
		while (q[j - 1].l < q[j].l) remove(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) remove(q[j - 1].r), q[j - 1].r--;
		while (q[j - 1].t < q[j].t) upt(q[j - 1].t, j);
		while (q[j - 1].t > q[j].t) dnt(q[j - 1].t, j);
		q[j].ans = q[j].r - q[j].l + 1 - sum;
		//cout << q[j].l << ' ' << q[j].r << ' ' << q[j].t << ':';
		//for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}

P4867 Gty的妹子序列

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
#include<bits/stdc++.h>
using namespace std;
int n, Q, bel[100000 + 10], a[100000 + 10], R[316 + 10];
struct Query {
	int l, r, a, b, id, ans;
	friend bool operator<(const Query& a, const Query& b) {
		return bel[a.l] == bel[b.l] ? bel[a.l] % 2 == 1 ? a.r<b.r : a.r>b.r : bel[a.l] < bel[b.l];
	}
}q[1000000 + 10];
namespace {
	void print();
	int vis[100000 + 10], Sum[316 + 10];
	void add(int x) {
		vis[a[x]]++;
		Sum[bel[a[x]]] += vis[a[x]] == 1;
		//cout << "add a[" << x << "]=" << a[x] << " done" << endl;
		//print();
	}
	void del(int x) {
		vis[a[x]]--;
		Sum[bel[a[x]]] -= vis[a[x]] == 0;
		//cout << "del a[" << x << "]=" << a[x] << " done" << endl;
		//print();
	}
	int query(int a, int b) {
		int ans = 0;
		if (bel[a] == bel[b]) {
			for (int i = a; i <= b; ++i) ans += bool(vis[i]);
			return ans;
		}
		for (int i = bel[a] + 1; i < bel[b]; ++i) ans += Sum[i];
		for (int i = a; i <= R[bel[a]]; ++i) ans += bool(vis[i]);
		for (int i = R[bel[b] - 1] + 1; i <= b; ++i) ans += bool(vis[i]);
		return ans;
	}
	void print() {
		cout << "bel: ";
		for (int i = 1; i <= n; ++i) cout << bel[i] << ' ';
		cout << endl << "rst: ";
		for (int i = 1; i <= n; ++i) cout << R[bel[i]] << ' ';
		cout << endl << "vis: ";
		for (int i = 1; i <= n; ++i) cout << vis[i] << ' ';
		cout << endl << "sum: ";
		for (int i = 1; i <= n; ++i) cout << Sum[bel[i]] << ' ';
		cout << endl;
	}
}
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	int t1 = 1, t2 = pow(n, 0.5), t3 = 1;
	for (int i = 1; i <= n; ++i) {
		bel[i] = t3;
		if (t1 == t2) t1 = 0, R[t3] = i, t3++;
		t1++;
	}
	R[t3] = n;
	for (int j = 1; j <= Q; ++j) cin >> q[j].l >> q[j].r >> q[j].a >> q[j].b, q[j].id = j/*, q[j].l--*/;
	sort(q + 1, q + Q + 1);
	q[0].l = 1;
	for (int j = 1; j <= Q; ++j) {
		//cerr << "beg to deal with [" << q[j].l << ',' << q[j].r << "](" << q[j].a << ',' << q[j].b << ")\n" << "from [" << q[j - 1].l << ',' << q[j - 1].r << ']' << endl;
		while (q[j - 1].l < q[j].l) del(q[j - 1].l), q[j - 1].l++;
		while (q[j - 1].l > q[j].l) add(q[j - 1].l - 1), q[j - 1].l--;
		while (q[j - 1].r < q[j].r) add(q[j - 1].r + 1), q[j - 1].r++;
		while (q[j - 1].r > q[j].r) del(q[j - 1].r), q[j - 1].r--;
		q[j].ans = query(q[j].a, q[j].b);
	}
	sort(q + 1, q + Q + 1, [](const Query& a, const Query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}

AT_joisc2014_c 歴史の研究

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
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define __gcd gcd
#endif // !ONLINE_JUDGE
using namespace std;
int a[100000 + 10];
long long sum, lst;
unordered_map<int, int>vis;
void add(int x) {
	vis[a[x]]++;
	sum = max(sum, vis[a[x]] * 1ll * a[x]);
}
int n, Q, bel[100000 + 10], R[100000 + 10];
struct query {
	int l, r, id; long long ans;
	friend bool operator<(const query& a, const query& b) {
		return bel[a.l] == bel[b.l] ? a.r < b.r : bel[a.l] < bel[b.l];
	}
}q[100000 + 10];
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> Q;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	int t1 = 0, t2 = pow(n, 0.5), t3 = 1;
	for (int i = 1; i <= n; ++i) {
		bel[i] = t3;
		t1++;
		if (t1 == t2) R[t3] = i, t1 = 0, t3++;
	}
	//for (int i = 1; i <= n; ++i) cout << bel[i] << ' '; cout << endl;
	for (int j = 1; j <= Q; ++j) cin >>  q[j].l >> q[j].r, q[j].id = j;
	sort(q + 1, q + Q + 1);
	int r = 0;
	for (int j = 1; j <= Q; ++j) {
		//cout << q[j].l << ' ' << q[j].r << ' ' << bel[q[j].l] << endl;
		if (bel[q[j - 1].l] ^ bel[q[j].l]) {
			unordered_map<int, int>().swap(vis);
			sum = 0;
			while (bel[q[j].r] == bel[q[j].l]) {
				//cout << "BF: " << q[j].l << ' ' << q[j].r << ' ' << bel[q[j].l] << endl;
				for (int i = q[j].l; i <= q[j].r; ++i) add(i);
				q[j].ans = sum;
				unordered_map<int, int>().swap(vis);
				sum = 0;
				if (bel[q[j].l] ^ bel[q[j + 1].l]) break;
				j++;
			}
			if ((bel[q[j].l] ^ bel[q[j + 1].l]) && bel[q[j].r] == bel[q[j].l]) continue;
			r = R[bel[q[j].l]] + 1;
			add(r);
		}
		1;
		while (r < q[j].r) add(++r);
		lst = sum;
		int l = R[bel[q[j].l]]; add(l);
		while (l > q[j].l) add(--l);
		//cout << "add " << "[" << l << '(' << q[j].l << ')' << ',' << r << '(' << q[j].r << ')' << "] with vis:"; for (int i = 1; i <= 10; ++i) cout << vis[i] << ' '; cout << endl;
		q[j].ans = sum;
		while (l <= R[bel[q[j].l]]) vis[a[l]]--, l++;
		sum = lst;
	}
	sort(q + 1, q + Q + 1, [](const query& a, const query& b)->bool {return a.id < b.id; });
	for (int i = 1; i <= Q; ++i) cout << q[i].ans << endl;
	return 0;
}