NOI2007项链工厂

2014年7月31日5,5190

Description

Input

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

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

对于60%的数据，N ≤ 1 000，Q ≤ 1 000；对于100%的数据，N ≤ 500 000，Q ≤ 500 000，c ≤ 1 000。

题解

真是神烦线段树

主要就是记录下整个项链是否翻转过以及旋转的度。。。

其它是线段树基本操作

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool rev;
int n,m,delta;
struct data{int l,r,sum;};
struct seg{int l,r,tag;data c;}t[2000005];
void cal(int &x,int &y)
{
	if(rev)
	{
		x=(n+n+2-delta-x)%n;
		y=(n+n+2-delta-y)%n;
		swap(x,y);
	}
	else 
	{
		x=(x-delta+n)%n;
	    y=(y-delta+n)%n;
	}
	if(x==0)x=n;if(y==0)y=n;
}
data merge(data a,data b)
{
	data tmp;
	tmp.l=a.l;tmp.r=b.r;
	tmp.sum=a.sum+b.sum;
	if(a.r==b.l)tmp.sum--;
	return tmp;
}
void update(int k)
{
	t[k].c=merge(t[k<<1].c,t[k<<1|1].c);
}
void pushdown(int k)
{
	if(!t[k].tag||t[k].l==t[k].r)return;
	int tag=t[k].tag;t[k].tag=0;
	t[k<<1].tag=t[k<<1|1].tag=tag;
	t[k<<1].c.l=t[k<<1|1].c.l=tag;
	t[k<<1].c.r=t[k<<1|1].c.r=tag;
	t[k<<1].c.sum=t[k<<1|1].c.sum=1;
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r)
	{
	    t[k].c.l=t[k].c.r=read();
		t[k].c.sum=1;
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	update(k);
}
data query(int k,int x,int y)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r)return t[k].c;
	int mid=(l+r)>>1;
	if(y<=mid)return query(k<<1,x,y);
	else if(x>mid)return query(k<<1|1,x,y);
	else
	{
		return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
	}
}
void modify(int k,int x,int y,int val)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r)
	{
		t[k].c.l=t[k].c.r=t[k].tag=val;
		t[k].c.sum=1;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)modify(k<<1,x,y,val);
	else if(x>mid)modify(k<<1|1,x,y,val);
	else 
	{
		modify(k<<1,x,mid,val);
		modify(k<<1|1,mid+1,y,val);
	}
	update(k);
}
int main()
{
	n=read();m=read();
	build(1,1,n);
	char ch[5];
	m=read();
	int x,y,val;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",ch);
		if(ch[0]=='R')
		{
			x=read();
			if(rev)delta=(delta+n-x)%n;
			else delta=(delta+x)%n;
		}
		if(ch[0]=='F')rev^=1;
		if(ch[0]=='S')
		{
			x=read();y=read();
			int a,b;
		    cal(x,y);data ans;
			if(x>y)
			{
				ans=query(1,y,x);
				a=ans.r;b=ans.l;
			}
			else 
			{
				ans=query(1,x,y);
				a=ans.l;b=ans.r;
			}
			modify(1,x,x,b);modify(1,y,y,a);
		}
		if(ch[0]=='P')
		{
			x=read();y=read();val=read();
		    cal(x,y);
			if(x<=y)modify(1,x,y,val);
			else 
			{
				modify(1,x,n,val);modify(1,1,y,val);
			}
		}
	    if(ch[0]=='C'&&ch[1]=='S')
		{
			x=read();y=read();
		    cal(x,y);
			data ans;
			if(x<=y)ans=query(1,x,y);
			else 
				ans=merge(query(1,x,n),query(1,1,y));
			printf("%d\n",ans.sum);
		}
		if(ch[0]=='C'&&ch[1]!='S')
		{
			data ans=query(1,1,n);
			int tmp=ans.sum;
			if(ans.l==ans.r)
				tmp=max(tmp-1,1);
			printf("%d\n",tmp);
		}
	}
	return 0;
}

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

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

#define inf 0x7fffffff

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool rev;

int n,m,delta;

struct data{int l,r,sum;};

struct seg{int l,r,tag;data c;}t[2000005];

void cal(int &x,int &y)

{

if(rev)

{

x=(n+n+2-delta-x)%n;

y=(n+n+2-delta-y)%n;

swap(x,y);

}

else

{

x=(x-delta+n)%n;

y=(y-delta+n)%n;

}

if(x==0)x=n;if(y==0)y=n;

}

data merge(data a,data b)

{

data tmp;

tmp.l=a.l;tmp.r=b.r;

tmp.sum=a.sum+b.sum;

if(a.r==b.l)tmp.sum--;

return tmp;

}

void update(int k)

{

t[k].c=merge(t[k<<1].c,t[k<<1|1].c);

}

void pushdown(int k)

{

if(!t[k].tag||t[k].l==t[k].r)return;

int tag=t[k].tag;t[k].tag=0;

t[k<<1].tag=t[k<<1|1].tag=tag;

t[k<<1].c.l=t[k<<1|1].c.l=tag;

t[k<<1].c.r=t[k<<1|1].c.r=tag;

t[k<<1].c.sum=t[k<<1|1].c.sum=1;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r)

{

t[k].c.l=t[k].c.r=read();

t[k].c.sum=1;

return;

}

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

update(k);

}

data query(int k,int x,int y)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)return t[k].c;

int mid=(l+r)>>1;

if(y<=mid)return query(k<<1,x,y);

else if(x>mid)return query(k<<1|1,x,y);

else

{

return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));

}

void modify(int k,int x,int y,int val)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r)

{

t[k].c.l=t[k].c.r=t[k].tag=val;

t[k].c.sum=1;

return;

}

int mid=(l+r)>>1;

if(y<=mid)modify(k<<1,x,y,val);

else if(x>mid)modify(k<<1|1,x,y,val);

else

{

modify(k<<1,x,mid,val);

modify(k<<1|1,mid+1,y,val);

}

update(k);

}

int main()

{

n=read();m=read();

build(1,1,n);

char ch[5];

m=read();

int x,y,val;

for(int i=1;i<=m;i++)

{

scanf("%s",ch);

if(ch[0]=='R')

{

x=read();

if(rev)delta=(delta+n-x)%n;

else delta=(delta+x)%n;

}

if(ch[0]=='F')rev^=1;

if(ch[0]=='S')

{

x=read();y=read();

int a,b;

cal(x,y);data ans;

if(x>y)

{

ans=query(1,y,x);

a=ans.r;b=ans.l;

}

else

{

ans=query(1,x,y);

a=ans.l;b=ans.r;

}

modify(1,x,x,b);modify(1,y,y,a);

}

if(ch[0]=='P')

{

x=read();y=read();val=read();

cal(x,y);

if(x<=y)modify(1,x,y,val);

else

{

modify(1,x,n,val);modify(1,1,y,val);

}

if(ch[0]=='C'&&ch[1]=='S')

{

x=read();y=read();

cal(x,y);

data ans;

if(x<=y)ans=query(1,x,y);

else

ans=merge(query(1,x,n),query(1,1,y));

printf("%d\n",ans.sum);

}

if(ch[0]=='C'&&ch[1]!='S')

{

data ans=query(1,1,n);

int tmp=ans.sum;

if(ans.l==ans.r)

tmp=max(tmp-1,1);

printf("%d\n",tmp);

}

return 0;

}

« 「BZOJ2733」[HNOI2012] 永无乡「POJ3321」Apple Tree »

hzwer.com _ Home | http://hzwer.com

NOI2007项链工厂

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论