BZOJ2080 : [Poi2010]Railway
2024-08-24 23:06:07
如果存在$k$使得$i<j<k$,且$a[k]<a[i]<a[j]$,那么$i$和$j$不能在一个栈中。
设$b[i]=\min(a[i..n])$,如果$b[j]<a[i]<a[j]$,那么$i$和$j$不能在一个栈中。
设$c[i]$表示最大的$j$,满足$b[j]<i$,则$i$要向位置在$[i+1,c[a[i]]]$之间所有$a[j]>a[i]$的$j$连边,还要向$a$在$[b[i]+1,a[i]-1]$里所有位置$<i$的$j$连边。
然后二分图染色即可,最后检查是否合法。
在染色的时候,维护两棵线段树,第一棵按位置维护$a$的最大值,第二棵按$a$维护位置的最小值,即可不重不漏地取出所有没有染过色的点,每次取出一个点就要将它从两棵树中删除。
时间复杂度$O(n\log n)$。
#include<cstdio>
const int N=100010,M=262150;
int n,i,j,a[N],b[N],c[N],f[N],va[M],vb[M],pos[N],tmp,col[N],bit[3][N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int min(int a,int b){return a<b?a:b;}
inline int mergea(int x,int y){
if(!x||!y)return x+y;
return a[x]>a[y]?x:y;
}
inline int mergeb(int x,int y){
if(!x||!y)return x+y;
return x<y?x:y;
}
void build(int x,int a,int b){
if(a==b){
pos[a]=x;
va[x]=a;
vb[x]=f[a];
return;
}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b);
va[x]=mergea(va[x<<1],va[x<<1|1]);
vb[x]=mergeb(vb[x<<1],vb[x<<1|1]);
}
void aska(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){tmp=mergea(tmp,va[x]);return;}
int mid=(a+b)>>1;
if(c<=mid)aska(x<<1,a,mid,c,d);
if(d>mid)aska(x<<1|1,mid+1,b,c,d);
}
void askb(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){tmp=mergeb(tmp,vb[x]);return;}
int mid=(a+b)>>1;
if(c<=mid)askb(x<<1,a,mid,c,d);
if(d>mid)askb(x<<1|1,mid+1,b,c,d);
}
inline void del(int x){
int y=pos[x];
for(va[y]=0,y>>=1;y;y>>=1)va[y]=mergea(va[y<<1],va[y<<1|1]);
y=pos[a[x]];
for(vb[y]=0,y>>=1;y;y>>=1)vb[y]=mergeb(vb[y<<1],vb[y<<1|1]);
}
void dfs(int x,int y){
del(x);
col[x]=y;
int l=i+1,r=c[a[x]];
if(l<=r)while(1){
tmp=0;
aska(1,1,n,l,r);
if(!tmp)break;
if(a[tmp]<a[x])break;
dfs(tmp,3-y);
}
l=b[x]+1,a[x]-1;
if(l<=r)while(1){
tmp=0;
askb(1,1,n,l,r);
if(!tmp)break;
if(tmp>x)break;
dfs(tmp,3-y);
}
}
inline void add(int*b,int x){for(;x<=n;x+=x&-x)b[x]++;}
inline int ask(int*b,int x){int t=0;for(;x;x-=x&-x)t+=b[x];return t;}
int main(){
read(n);
for(i=1;i<=n;i++)read(a[i]),f[a[i]]=i;
for(b[n]=a[n],i=n-1;i;i--)b[i]=min(a[i],b[i+1]);
for(i=1;i<=n;c[i++]=j)while(j<n&&b[j+1]<i)j++;
build(1,1,n);
for(i=1;i<=n;i++)if(!col[i])dfs(i,1);
for(i=1;i<=n;i++){
if(ask(bit[col[i]],a[i]-1)>ask(bit[col[i]],b[i]))return puts("NIE"),0;
add(bit[col[i]],a[i]);
}
for(puts("TAK"),i=1;i<=n;i++)printf("%d%c",col[i],i<n?' ':'\n');
return 0;
}
最新文章
- 安装centos后无法引导启动windows7的解决方法
- 关于位图读取函数int Load_Bitmap_File的lseek问题。
- Sign-Magnitude Representation
- 生产者-消费者 用非阻塞队列、Object.wait()、Object.notify()实现
- zoj1530 bfs
- 仿照CREATE_FUNC实现CCLayer中的返回CCScene* 的静态函数,宏包装成CREATE_SCENE(XXLayer)
- Mysql 的安装与配置
- 普通Java类获取spring 容器的bean的5种方法
- ACM2032
- Objective-C中的内存管理——手动内存管理
- Coffee
- sql中的for xml path() 实现字符串拼接
- ubuntu下动态链接库的编译和使用实例
- 进程命令ps/top/kill
- VirtualBox fedora29 安装
- Javascript中类的实现机制(四)
- 字符串以及for循环
- Windows应急响应操作手册
- Cocos2d-x学习笔记(五)调度
- commonJS规范基本结构