首页 > 代码库 > 【BZOJ-1493】项链工厂 Splay

【BZOJ-1493】项链工厂 Splay

2024-09-02 16:40:09   216人阅读

1493: [NOI2007]项链工厂

Time Limit: 30 Sec  Memory Limit: 64 MB
Submit: 1440  Solved: 626
[Submit][Status][Discuss]

Description

T公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。
最近T公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。该项链自助生产系统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成，而软件系统尚未开发，T公司的人找到了正在参加全国信息学竞赛的你，你能帮助T公司编写一个软件模拟系统吗？一条项链包含 N 个珠子，每个珠子的颜色是 1，2，…，c 中的一种。项链被固定在一个平板上，平板的某个位置被标记位置 1 ，按顺时针方向其他位置被记为1，2，3，…，N。
技术分享
你将要编写的软件系统应支持如下命令：
技术分享

Input

输入文件第一行包含两个整数 N，c ，分别表示项链包含的珠子数目以及颜色数目。
第二行包含 N 个整数，x1，x2，…，xn ，表示从位置 1 到位置 N 的珠子的颜色，1≤xi≤c 。
第三行包含一个整数 Q ，表示命令数目。接下来的 Q 行每行一条命令，如上文所述。N≤500000 ，Q≤500000，c≤1000 
 

Output

对于每一个 C 和 CS 命令，应输出一个整数代表相应的答案。

Sample Input

5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1

Sample Output

4
1

HINT

注意旋转命令旋转“珠子”但不改变“位置”的编号，而反转命令始终以位置 1 为对称轴。例如当 N=10 时，项
链上的位置编号如图1：

技术分享


但注意此时项链上的位置编号仍然如图1所示，于是翻转的对称轴不变。因而再执行一次“F”命令时，项链的颜色如图4所示。
2. 关于CountSegment命令CS命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于 N 时，我们仍然将查询部分作为“线段”理解。例如在图4所示的情况中，执行“CS 1 10”命令，查询从位置 1 开始到位置 10 结束的这个长度为 10 的线段中有多少个“部分”，于是得到返回值 3 。与之形成对照的是，若执行“C”命令，返回值则为 2

Source

Solution

所有操作Splay都可以做，那就直接搞了。

维护只需要维护 颜色段数、左端颜色、右端颜色 即可。

R操作就是把最后$k$个切掉连到前面，F操作就是区间$[2,N]$翻转，其余的打打标记很基础了，先旋转操作处理完再转回来就好。

C查询就是先CS查询$[1,N]$再判断断点衔接就好了..注意纯色段不能直接$-1$

Splay的常数好像有点大，调试的时候突然想到可以利用线段树来做..代码量和常数应该会小不少....

Code

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>using namespace std;inline int read(){	int x=0,f=1; char ch=getchar();	while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}	while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}	return x*f;}#define MAXN 500010int N,C,Q,a[MAXN];namespace SplayTree{#define lson(x) son[x][0]#define rson(x) son[x][1]	int size[MAXN],fa[MAXN],son[MAXN][2],sz,root;	int val[MAXN],lc[MAXN],rc[MAXN],cnt[MAXN],rev[MAXN],cov[MAXN];	inline void Newnode(int &x,int last,int v)	{		x=++sz;		fa[x]=last; son[x][0]=son[x][1]=0;		val[x]=lc[x]=rc[x]=v;		cnt[x]=v? 1:0;	}	inline void Update(int x)	{		if (!x) return;		size[x]=size[lson(x)]+size[rson(x)]+1;		cnt[x]=cnt[lson(x)]+cnt[rson(x)]+1;		lc[x]=rc[x]=val[x];		if (lson(x)) lc[x]=lc[lson(x)],cnt[x]-=(val[x]==rc[lson(x)]? 1:0);		if (rson(x)) rc[x]=rc[rson(x)],cnt[x]-=(val[x]==lc[rson(x)]? 1:0);	}	inline int Build(int l,int r,int last)	{		int mid=(l+r)>>1,x;		Newnode(x,last,a[mid]);		if (mid-1>=l) son[x][0]=Build(l,mid-1,x);		if (mid+1<=r) son[x][1]=Build(mid+1,r,x);		Update(x);		return x; 	}	inline void Rev(int x) {if (!x) return; rev[x]^=1; swap(son[x][1],son[x][0]); swap(lc[x],rc[x]);}	inline void Cov(int x,int c) {if (!x) return; cov[x]=c; rev[x]=0; cnt[x]=1; lc[x]=rc[x]=val[x]=c;}	inline void Pushdown(int x)	{				if (cov[x])			Cov(son[x][0],cov[x]),Cov(son[x][1],cov[x]),cov[x]=0;		if (rev[x])			Rev(son[x][0]),Rev(son[x][1]),rev[x]^=1;	}	inline int Right(int x) {return son[fa[x]][1]==x;}    inline void Rotate(int x)    {        int y=fa[x],z=fa[y],w=Right(x);        Pushdown(y); Pushdown(x);        son[y][w]=son[x][w^1]; fa[son[y][w]]=y;        fa[y]=x; son[x][w^1]=y; fa[x]=z;        if (z) son[z][son[z][1]==y]=x;        Update(y); Update(x);    }    inline void Splay(int x,int tar)    {        for (int y; (y=fa[x])!=tar; Rotate(x))            if (fa[y]!=tar) Rotate(Right(x)==Right(y) ? y:x);        if (!tar) root=x;    }    inline int Find(int x,int k)    {        Pushdown(x);        if (size[son[x][0]]>=k) return Find(son[x][0],k);        if (size[son[x][0]]+1==k) return x;        return Find(son[x][1],k-size[son[x][0]]-1);    }	inline int Split(int l,int r)	{		int x=Find(root,l),y=Find(root,r+2);		Splay(x,0); Splay(y,root); return lson(rson(root));	}	inline void Move(int k)	{		if (!k || k==N) return;		int x=Split(N-k+1,N),y=fa[x];		fa[x]=0; son[y][0]=0;		Update(y); Update(fa[y]);		int xx=Find(root,1),yy=Find(root,2);		Splay(xx,0); Splay(yy,root);		son[rson(root)][0]=x; fa[x]=rson(root);		Update(rson(root)); Update(root);	}	inline void Cover(int l,int r,int c)	{		int x;		if (l<=r)			x=Split(l,r),Cov(x,c);		else			Move(N-l+1),Cover(1,r+N-l+1,c),Move(l-1); 	}	inline int Query(int l,int r)	{		int x;		if (l<=r)			return cnt[Split(l,r)];		else 			return Move(N-l+1),x=Query(1,r+N-l+1),Move(l-1),x;	}	inline int Query()	{		int x=cnt[Split(1,N)],lc=val[Find(root,2)],rc=val[Find(root,N+1)];		return rc==lc? max(x-1,1):x;	}	inline void Swap(int x,int y)	{		int xc=val[Find(root,x+1)],yc=val[Find(root,y+1)];		Cover(x,x,yc); Cover(y,y,xc); 	}	inline void Rever() {int x=Split(2,N); Rev(x);}}using namespace SplayTree;int main(){	N=read(),C=read();	for (int i=1; i<=N; i++) a[i]=read();		Newnode(root,0,0);	Newnode(son[root][1],root,0);	son[son[root][1]][0]=SplayTree::Build(1,N,son[root][1]);		Q=read();	while (Q--) {		char opt[3]; scanf("%s",opt+1);		int x,y,c,k;		switch (opt[1]) {			case ‘R‘ : k=read(); SplayTree::Move(k); break;			case ‘F‘ : SplayTree::Rever(); break;			case ‘S‘ : x=read(),y=read(); SplayTree::Swap(x,y); break;			case ‘P‘ : x=read(),y=read(),c=read(); SplayTree::Cover(x,y,c); break;			case ‘C‘ : if (opt[2]==‘S‘) x=read(),y=read(),printf("%d\n",SplayTree::Query(x,y)); else printf("%d\n",SplayTree::Query()); break; 		}	}	return 0;}

　　

【BZOJ-1493】项链工厂 Splay


联系
我们