Loj 6187 Odd

Posted on | Edited on | Views:

随机化 + 分块维护 hash 表.

每个数出现奇数次有一个比较常用的处理方法,就给每个数随机分配一个较大的权值.

若区间内所有数权值异或和等于区间内所有出现过的数权值异或和,则说明每个数都出现了奇数次.

考虑枚举右端点 $r$ ,统计有几个左端点 $l$ 满足要求.

记 $p(x)$ 表示 $[x,r]$ 所有出现过的数权值异或和,在加入 $r$ 时给 $[lst(a_r)+1,r]$ 内的 $p$ 异或上 $a_r​$ 的权值.

记前缀和 $s(x)$ 表示 $[1,x]$ 内所有数的异或和,在加入 $r$ 时只用计算出 $s(r)$ ,对前面的 $r$ 无影响.

若区间 $[l,r]$ 合法,则有 $p(l)=s(r)\oplus s(l-1)$ ,即 $p(l)\oplus s(l-1)=s(r)$ .

给每个 $l$ 维护出 $val(l)=p(l)\oplus s(l-1)$ ,修改时会给某个区间异或上一个 $v$ ,询问时询问内区间有几个 $v$ .

用分块 + hash 表维护,修改时整块打标记,边角暴力重构,询问时整块直接询问 hash 表,边角暴力重构后再询问.

时间复杂度 $O(n\sqrt n)$ .

有一个很有用的剪枝,询问时,若边角块没有标记,就可以不用重构.

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
typedef unsigned long long ull;
mt19937 Generator(19260817);
ull gen()
{
	return Generator() | ((ull)(Generator()) << 32);
}
const int N = 2e5 + 10, M = 1e6 + 10, B = 300, S = (N / B) + 10, P = 20007;
struct HashTable
{
	int tot, head[P], nx[S], cnt[S];
	ull t[S];
	void ins(ull x)
	{
		int pos = x % P;
		for (int i = head[pos]; i; i = nx[i])
			if (t[i] == x)
			{
				++cnt[i];
				return;
			}
		t[++tot] = x, cnt[tot] = 1, nx[tot] = head[pos], head[pos] = tot;
	}
	int Find(ull x)
	{
		int pos = x % P;
		for (int i = head[pos]; i; i = nx[i])
			if (t[i] == x)
				return cnt[i];
		return 0;
	}
	void reset()
	{
		for (int i = 1; i <= tot; ++i)
			head[t[i] % P] = 0, cnt[i] = 0;
		tot = 0;
	}
} Hash[S];
int n, bel[N], lp[S], rp[S], a[N], lst[M];
ull val[N], b[M], tag[S], sum = 0;
void ReBuild(int x)
{
	Hash[x].reset();
	for (int i = lp[x]; i <= rp[x]; ++i)
	{
		val[i] ^= tag[x];
		Hash[x].ins(val[i]);
	}
	tag[x] = 0;
}
void pushdown(int x)
{
	if (tag[x])
		ReBuild(x);
}
void upd(int L, int R, ull x)
{
	if (bel[L] == bel[R])
	{
		for (int i = L; i <= R; ++i)
			val[i] ^= x;			
		ReBuild(bel[L]);
	}
	else
	{
		for (int i = L; i <= rp[bel[L]]; ++i)
			val[i] ^= x;
		ReBuild(bel[L]);
		for (int i = bel[L] + 1; i <= bel[R] - 1; ++i)
			tag[i] ^= x;
		for (int i = lp[bel[R]]; i <= R; ++i)
			val[i] ^= x;
		ReBuild(bel[R]);			
	}
}
int query(int L, int R, ull x)
{
	int s = 0;
	if (bel[L] == bel[R])
	{
		pushdown(bel[L]);
		for (int i = L; i <= R; ++i)
			s += (val[i] == x);
	}
	else
	{
		pushdown(bel[L]);
		for (int i = L; i <= rp[bel[L]]; ++i)
			s += (val[i] == x);
		for (int i = bel[L] + 1; i <= bel[R] - 1; ++i)
			s += Hash[i].Find(x ^ tag[i]);
		pushdown(bel[R]);
		for (int i = lp[bel[R]]; i <= R; ++i)
			s += (val[i] == x);
	}
	return s;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		a[i] = read();
		b[a[i]] = gen();
	}
	for (int i = 1; i <= n; ++i)
	{
		bel[i] = (i - 1) / B + 1;
		lp[bel[i]] = (bel[i] - 1) * B + 1;
		rp[bel[i]] = bel[i] * B;
	}
	rp[bel[n]] = n;
	for (int i = 1; i <= n; ++i)
	{
		val[i] = sum;
		sum ^= b[a[i]]; 
	}
	for (int i = 1; i <= bel[n]; ++i)
		ReBuild(i);
	sum = 0;
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		sum ^= b[a[i]];
		upd(lst[a[i]] + 1, i, b[a[i]]);
		ans += query(1, i, sum);
		lst[a[i]] = i;
	}
	printf("%lld\n", ans);
	return 0;
}