题解 P4065 【[JXOI2017]颜色】

Nemlit

2019-09-04 22:00:13

Solution

$Orz$ 各位题解大佬,我来膜拜一发 ~~还有单调栈实在没弄懂~~ ### 法一:线段树+堆 首先,讨论区间的个数的题目,我们可以想到枚举一个端点$r$,找到所有的$l$ 我们不妨设:$ml[i]$为第i种颜色出现的最小位置,$mr[i]$为第i种出现的最大位置 我们想到对于一个右端点,他有那些值是不能选的: 假设有一种颜色的$mr$值比当前枚举的右端点小,则$[ml, mr]$里面的所有的左端点都不能选,对应到线段树中就是区间赋成0 再假设有一种颜色,当前枚举的右端点在$[ml[i], mr[i]]$之间,那么我们记录一个$last[i]$,表示小于当前右端点的最大的i 那么$[1, last[i]]$所有的值都不能选 然后我们要找到一个最大的last,用一个堆即可 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define int long long il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define mem(k, p) memset(k, p, sizeof(k)) #define ls k * 2 #define rs k * 2 + 1 #define maxn 300005 int n, m, a[maxn], last[maxn], ans, ml[maxn], mr[maxn], tag[maxn << 2], sum[maxn << 2]; struct node {int id, val; il bool operator < (const node&x) const{return val < x.val;}}; priority_queue<node> q; il void pushdown(int k, int l, int r, int mid) { if(tag[k] == -1) return; sum[ls] = (mid - l + 1) * tag[k], sum[rs] = (r - mid) * tag[k]; tag[ls] = tag[rs] = tag[k]; tag[k] = -1; } il void modify(int k, int l, int r, int ll, int rr, int x) { if(l > rr || ll > r) return; if(ll <= l && r <= rr) return (void)(tag[k] = x, sum[k] = (r - l + 1) * x); int mid = (l + r) >> 1; pushdown(k, l, r, mid); modify(ls, l, mid, ll, rr, x), modify(rs, mid + 1, r, ll, rr, x); sum[k] = sum[ls] + sum[rs]; } il int query(int k, int l, int r, int ll, int rr) { if(l > rr || ll > r) return 0; if(ll <= l && r <= rr) return sum[k]; int mid = (l + r) >> 1; pushdown(k, l, r, mid); return query(ls, l, mid, ll, rr) + query(rs, mid + 1, r, ll, rr); } il void solve() { n = read(), ans = 0, mem(tag, -1), modify(1, 1, n, 1, n, 1); while(!q.empty()) q.pop(); rep(i, 1, n) ml[i] = n + 1, mr[i] = last[i] = 0; rep(i, 1, n) a[i] = read(), ml[a[i]] = min(ml[a[i]], i), mr[a[i]] = max(mr[a[i]], i); rep(i, 1, n) { last[a[i]] = i, q.push((node){a[i], last[a[i]]}); if(i == mr[a[i]]) modify(1, 1, n, ml[a[i]] + 1, mr[a[i]], 0); while(!q.empty()) { int x = q.top().id; if(last[x] == mr[x]) q.pop(); else break; } int pax = (q.empty() ? 1 : q.top().val + 1); ans += query(1, 1, n, pax, i); } printf("%lld\n", ans); } signed main() { int T = read(); while(T --) solve(); return 0; } ``` ### 随机化 对于每一个位置,我们需要随机一个值,然后需要保证相同的颜色的所有的随机值异或结果为$0$ 由于异或满足$a\ $^$\ b = 0$,所以我们把每个颜色的除了最后一项的所有随机值异或起来,让最后一位等于这个随机值 然后我们不难发现,每一个满足条件的一段区间,他的异或的值显然是等于0的 所以问题就转化成了:有多少区间的异或和等于0 由于上述异或的性质,于是我们只需要用$map$存一下即可 跟据@$Ebola$大佬的证明,我们的错误率是很小的。 ### $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define int long long il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define Next(i, u) for(re int i = head[u]; i; i = e[i].next) #define mem(k, p) memset(k, p, sizeof(k)) #define lb(x) (x)&(-(x)) #define ls k * 2 #define rs k * 2 + 1 #define maxn 300005 int n, m, a[maxn], val[maxn]; vector<int>q[maxn]; map<int, int> p; il int Random() { return 1ll * rand() * rand() * rand(); } signed main() { srand(time(0)); int T = read(); while(T --) { n = read(); rep(i, 1, n) a[i] = read(), q[a[i]].push_back(i), val[i] = 0; rep(i, 1, n) { int sum = 0; for(re int j = 0; j < q[i].size(); ++ j) { if(j == q[i].size() - 1) val[q[i][j]] = sum; else sum ^= (val[q[i][j]] = Random()); } q[i].clear(); } int ans = 0, now = 0; p[0] = 1; rep(i, 1, n) now ^= val[i], ans += p[now], ++ p[now]; rep(i, 1, n) now ^= val[i], p[now] = 0; printf("%lld\n", ans); } return 0; } ```