BZOJ5011 [JXOI2017]颜色【线段树 + 主席树】

题目链接

题解

一定只有我这种智障会用这么奇怪的方法做这道题。。

由题我们知道最后剩余的一定是一个区间，而且区间内的颜色不存在于区间外

所以我们的目的就是为了找到这样的区间的数量

区间由左右端点确定，我们枚举右端点，尝试维护左端点数量

当我们从右向左枚举到\(r\)，\(r\)右边的颜色已经在区间外，一定不能被包含入区间，所以我们记录每个位置上一个同色位置\(pre[i]\)，指针\(r\)每越过一个位置，就在\(pre[i]\)处打一个标记，表示这个位置不能被包含。之后我们每次找到\(r\)左边第一个标记的位置，再往左一定不合法，这样我们就得到了我们的初始区间，记为\([l,r]\)。这个操作可以使用线段树维护

考虑这个区间还会有什么不满足的地方

就是区间内的颜色不能出现在区间外

对于一个在\(r\)左侧的位置\(i\)，颜色为\(c\)，记颜色\(c\)最左边的位置为\(p\)，那么\([p + 1,i]\)都不能被选择，因为选择其中任意一个位置，都会使颜色\(c\)被分割

如何维护？

另开一个线段树区间\(set\)为\(1\)即可，一个位置可能被多个区间叠加，但只能贡献\(1\)

由于区间\(set\)操作不能被撤回，所以我们更新顺序只能从左到右，但我们是从右到左枚举的，怎么办？

那就强行从左到右更新，并保存每一个版本的线段树——永久化标记主席树

这样我们就做完了这道题

复杂度\(O(nlogn)\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 300005,maxm = 8000005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int ls[maxm],rs[maxm],Sum[maxm],tag[maxm],rt[maxn],cnt;

void Upd(int u){

	Sum[u] = Sum[ls[u]] + Sum[rs[u]];

}

void Set(int& u,int pre,int l,int r,int L,int R){

	u = ++cnt; ls[u] = ls[pre]; rs[u] = rs[pre]; tag[u] = Sum[u] = 0;

	tag[u] = tag[pre];

	if (tag[u]){

		Sum[u] = r - l + 1;

		return;

	}

	if (l >= L && r <= R){

		tag[u] = 1; Sum[u] = r - l + 1;

		return;

	}

	int mid = l + r >> 1;

	if (mid >= L) Set(ls[u],ls[pre],l,mid,L,R);

	if (mid < R) Set(rs[u],rs[pre],mid + 1,r,L,R);

	Upd(u);

}

int Query(int u,int l,int r,int L,int R){

	if (tag[u]) return R - L + 1;

	if (l >= L && r <= R) return Sum[u];

	int mid = l + r >> 1;

	if (mid >= R) return Query(ls[u],l,mid,L,R);

	if (mid < L) return Query(rs[u],mid + 1,r,L,R);

	return Query(ls[u],l,mid,L,mid) + Query(rs[u],mid + 1,r,mid + 1,R);

}

int sum[maxn << 2],mp[maxn << 2];

void upd(int u,int l,int r){

	sum[u] = sum[u << 1] + sum[u << 1 | 1];

	int mid = l + r >> 1;

	if (mp[u << 1 | 1] == 0) mp[u] = 0;

	else if (mp[u << 1] == 0) mp[u] = mp[u << 1 | 1];

	else if (mp[u << 1 | 1] == mid + 1) mp[u] = mp[u << 1];

	else mp[u] = mp[u << 1 | 1];

}

void modify(int u,int l,int r,int pos){

	if (l == r) {sum[u] = 1; mp[u] = 0; return;}

	int mid = l + r >> 1;

	if (mid >= pos) modify(u << 1,l,mid,pos);

	else modify(u << 1 | 1,mid + 1,r,pos);

	upd(u,l,r);

}

int query(int u,int l,int r,int L,int R){

	if (!sum[u]) return l;

	if (l >= L && r <= R) return mp[u];

	int mid = l + r >> 1;

	if (mid >= R) return query(u << 1,l,mid,L,R);

	if (mid < L) return query(u << 1 | 1,mid + 1,r,L,R);

	int t1 = query(u << 1,l,mid,L,R),t2 = query(u << 1 | 1,mid + 1,r,L,R);

	if (t2 == 0) return 0;

	else if (t1 == 0) return t2;

	else if (t2 == mid + 1) return t1;

	else return t2;

}

void build(int u,int l,int r){

	sum[u] = 0;

	if (l == r){

		mp[u] = l;

		return;

	}

	int mid = l + r >> 1;

	build(u << 1,l,mid);

	build(u << 1 | 1,mid + 1,r);

	upd(u,l,r);

}

int last[maxn],pre[maxn],F[maxn];

int n,A[maxn];

int main(){

	int T = read();

	while (T--){

		n = read(); REP(i,n) A[i] = read();

		cnt = 0; build(1,1,n);

		for (int i = 1; i <= n; i++) last[i] = 0;

		for (int i = 1; i <= n; i++){

			if (!last[A[i]]) F[A[i]] = i;

			pre[i] = last[A[i]];

			last[A[i]] = i;

			rt[i] = rt[i - 1];

			if (F[A[i]] < i) Set(rt[i],rt[i - 1],1,n,F[A[i]] + 1,i);

		}

		LL ans = 0;

		for (int i = n; i; i--){

			int l = query(1,1,n,1,i),r = i;

			if (pre[i]) modify(1,1,n,pre[i]);

			if (!l) continue;

			int t = Query(rt[i],1,n,l,r);

			ans += (r - l + 1) - t;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

BZOJ5011 [JXOI2017]颜色【线段树 + 主席树】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ5011 [JXOI2017]颜色 【线段树 + 主席树】

题目链接

题解

最新文章

热门文章

BZOJ5011 [JXOI2017]颜色【线段树 + 主席树】