bzoj2054疯狂的馒头——线段树

中文题面,一排有n个馒头,用刷子把整个连续的区间刷成一种颜色。因为颜色会覆盖掉之前的。所以我们可以用线段树来反着处理。如果这段区间之前刷到过就不要再遍历进去了,因为这次已经被上次刷的颜色给覆盖了。最后遍历线段树到叶子节点,输出最后的值就行了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 1e6+;
int sum[M<<];
void pushup(int rt){
sum[rt]=sum[rt<<]&&sum[rt<<|];
}
void update(int p,int x,int y,int l,int r,int rt){
if(sum[rt]){
return ;
}
if(l==r)
{
sum[rt]=p;
return;
}
mid;
if(x<=m) update(p,x,y,lson);
if(y>m) update(p,x,y,rson);
pushup(rt);
}
void pr(int l,int r,int rt)
{
if(l==r)
{
printf("%d\n",sum[rt]);
return;
}
mid;
pr(lson);
pr(rson);
}
int main()
{
int n,m,p,q;
scanf("%d%d%d%d",&n,&m,&p,&q);
for(int i=m;i>=;i--)
{
int lll,rrr;
lll=((i*p+q)%n)+;
rrr=((i*q+p)%n)+;
//cout<<l<<" "<<r<<endl;
if(rrr<lll)
{
int t=rrr;
rrr=lll;
lll=t;
}
update(i,lll,rrr,,n,);
}
pr(,n,);
return ;
}
上一篇:springmvc 关于controller的字符编码


下一篇:IntelliJ IDEA 插件 阿里巴巴Java开发手册(Alibaba Java Coding Guidelines)