BZOJ1493 : [NOI2007]项链工厂
工厂 项链
2023-09-11 14:15:05 时间
设delta表示翻转后的增量,flip表示是否翻转,
第x个位置对应原来位置为(flip?n+2-x+delta:x-delta)%n
再根据x,y的大小关系以及flip的是否讨论出现在作用的区间
用线段树维护最左端最右端的颜色和块数
这种神级码农题我居然一遍AC…
#include<cstdio> #define N 500010 int n,q,i,A[N],x,y,z,delta,flip,cx,cy,tot,l[N<<1],r[N<<1],cl[N<<1],cr[N<<1],sum[N<<1],tag[N<<1];char ch[10]; inline void read(int&a){char ch;while(!(((ch=getchar())>='0')&&(ch<='9')));a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';} inline void col1(int x,int p){cl[x]=cr[x]=tag[x]=p,sum[x]=1;} inline void pb(int x){if(tag[x])col1(l[x],tag[x]),col1(r[x],tag[x]),tag[x]=0;} inline void up(int x){cl[x]=cl[l[x]],cr[x]=cr[r[x]],sum[x]=sum[l[x]]+sum[r[x]]-(cr[l[x]]==cl[r[x]]);} void build(int a,int b){ int x=++tot; if(a==b){cl[x]=cr[x]=A[a],sum[x]=1;return;} int mid=(a+b)>>1; l[x]=tot+1,build(a,mid); r[x]=tot+1,build(mid+1,b); up(x); } void col(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){col1(x,p);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)col(l[x],a,mid,c,d,p); if(d>mid)col(r[x],mid+1,b,c,d,p); up(x); } int ask(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return sum[x]; pb(x); int mid=(a+b)>>1,t; if(d<=mid){t=ask(l[x],a,mid,c,d);return up(x),t;} if(c>mid){t=ask(r[x],mid+1,b,c,d);return up(x),t;} t=ask(l[x],a,mid,c,d)+ask(r[x],mid+1,b,c,d)-(cr[l[x]]==cl[r[x]]); return up(x),t; } int askcol(int x,int a,int b,int c){ if(a==b)return cl[x]; pb(x); int mid=(a+b)>>1,t=c<=mid?askcol(l[x],a,mid,c):askcol(r[x],mid+1,b,c); return up(x),t; } inline int form(int x){ x=(flip?n+2-x+delta:x-delta)%n; while(x<=0)x+=n; return x; } int main(){ for(read(n),read(i),i=1;i<=n;i++)read(A[i]); build(1,n); read(q); while(q--){ scanf("%s",ch); if(ch[0]=='R')read(x),(delta+=x)%=n; else if(ch[0]=='F')flip^=1,delta*=-1; else if(ch[0]=='S')read(x),read(y),cx=askcol(1,1,n,x=form(x)),cy=askcol(1,1,n,y=form(y)),col(1,1,n,x,x,cy),col(1,1,n,y,y,cx); else if(ch[0]=='P'){ read(x),read(y),read(z),x=form(x),y=form(y); if(!flip)x<=y?col(1,1,n,x,y,z):(col(1,1,n,x,n,z),col(1,1,n,1,y,z));else x>=y?col(1,1,n,y,x,z):(col(1,1,n,y,n,z),col(1,1,n,1,x,z)); }else if(ch[0]=='C'&&ch[1]=='S'){ read(x),read(y),x=form(x),y=form(y); if(!flip)printf("%d\n",x<=y?ask(1,1,n,x,y):ask(1,1,n,x,n)+ask(1,1,n,1,y)-(cl[1]==cr[1]));else printf("%d\n",x>=y?ask(1,1,n,y,x):ask(1,1,n,y,n)+ask(1,1,n,1,x)-(cl[1]==cr[1])); }else printf("%d\n",sum[1]==1?1:sum[1]-(cl[1]==cr[1])); } return 0; }
相关文章
- php设计模式-工厂模式
- 抽象工厂在ADO.Net中的应用
- 设计模式1——策略模式 | 适配器模式 | 工厂模式
- 简单工厂、工厂方法和抽象工厂
- 抽象工厂模式造车
- 抽象工厂模式(Abstract Factory)
- 《Spring攻略(第2版)》——1.8 使用工厂Bean和Utility Schema定义集合
- 工厂方法模式与抽象工厂模式
- 【Java萌新】面试常问设计模式——工厂模式
- 程序员35岁真的会失业?Python程序员离开大厂进工厂?制造业巨头招聘热闹程度堪比春运 背后原因振奋人心
- SuperSocket接收过滤器工厂(ReceiveFilterFactory)
- 单例、观察者、代理、备忘录、工厂
- 设计模式之美:Abstract Factory(抽象工厂)
- 抽象工厂
- 设计模式(一)工厂模式Factory(创建型)
- IOS设计模式-简单工厂
- 简单工厂模式练习:简单工厂模式在农场系统中实现(IDEA演示、适合小白)