ZJT's Blog

大変に気分がいい~

[UOJ #356] [JOI2017春季合宿] Port Facility

2018-6-5 7:132018-6-5 7:16
UOJJOI并查集线段树

题目链接

本题的限制等价于把一堆区间分成两个集合,每个集合内的区间两两之间要么不相交,要么完全包含。

我们把限制建成一个无向图,每两个冲突的区间之间都连一条边。显然,如果建出来不是二分图,答案必定为$0$(一个奇环上无法黑白染色使得两两相邻不同色)。我们把孤立的点去掉(去掉每个点会使答案乘$2$),考虑左边的每个点$x$,记右边与它相邻的点为$S_x$,则$S_x$中的点肯定是同色的,且$x$的颜色由$S_x$的颜色唯一确定。所以我们只需要把每个$S_x$用并查集并起来,最后统计右边的连通块数就行了。

然而直接建图搞的复杂度是$O(n^2)$的,我们考虑优化。注意到二分图的两边都可以看成一个合法的括号序列,我们建出对应的树结构。设右边所有区间中包含$x$的左端点及右端点的最小区间分别为$y_1,y_2$,则$S_x$即为$y_1$到$y_2$路径上的所有点减去两个点的LCA。这个东西在树上用并查集随便搞搞就行了。

关于求初始的二分图,我的做法是直接广搜,搜完之后检查一下合法性。对区间左端点建一个线段树,线段树每个区间按右端点的顺序维护未访问的所有区间。这里可以做到$O(n\log n)$的复杂度,加上前面的求LCA,总复杂度为$O(n\log n)$。

#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;

const int P=1000000007;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n;
pair<int,int> p[MAXN];
int p1[MAXN],pt1[MAXN],pt2[MAXN];
int *s[MAXN*3],len[MAXN*3],cur[MAXN*3];
int c[MAXN],pre[MAXN][21],dep[MAXN],top[MAXN];
int f[MAXN];
queue<int> Q;

int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}

void build(int x,int l,int r){
    if(l==r){
        if(p1[l]){
            s[x]=new int[len[x]=1];
            s[x][0]=p1[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    int x0=0,x1=0,x2=0,l1=len[x<<1],l2=len[x<<1|1];
    s[x]=new int[len[x]=l1+l2];
    while(x1<l1 || x2<l2){
        if(x1==l1) s[x][x0++]=s[x<<1|1][x2++];
        else if(x2==l2) s[x][x0++]=s[x<<1][x1++];
        else if(p[s[x<<1][x1]].second>p[s[x<<1|1][x2]].second) s[x][x0++]=s[x<<1][x1++];
        else s[x][x0++]=s[x<<1|1][x2++];
    }
}

void extend(int x,int cl,int cr,int l,int r,int nc){
    if(l<=cl && cr<=r){
        while(cur[x]<len[x] && p[s[x][cur[x]]].second>r){
            int t=s[x][cur[x]++];
            if(c[t]==-1){
                c[t]=nc;
                Q.push(t);
            }
        }
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) extend(x<<1,cl,mid,l,r,nc);
    if(r>mid) extend(x<<1|1,mid+1,cr,l,r,nc);
}

void bfs(int x){
    Q.push(x);
    c[x]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        extend(1,1,n<<1,p[x].first,p[x].second,c[x]^1);
        extend(1,1,n<<1,1,p[x].first,c[x]^1);
    }
}

bool check(){
    static stack<int> S;
    for(int _i=1;_i<=n<<1;_i++){
        while(!S.empty() && p[S.top()].second<_i) S.pop();
        if(p1[_i] && !c[p1[_i]]){
            int i=p1[_i];
            if(!S.empty() && p[S.top()].second<p[i].second) return 0;
            if(!S.empty()) pre[i][0]=S.top();
            S.push(i);
            dep[i]=dep[pre[i][0]]+1;
            top[i]=pre[i][0]?top[pre[i][0]]:i;
        }
        if(!S.empty()) pt1[_i]=S.top();
    }
    while(!S.empty()) S.pop();
    for(int _i=1;_i<=n<<1;_i++){
        while(!S.empty() && p[S.top()].second<_i) S.pop();
        if(p1[_i] && c[p1[_i]]){
            int i=p1[_i];
            if(!S.empty() && p[S.top()].second<p[i].second) return 0;
            if(!S.empty()) pre[i][0]=S.top();
            S.push(i);
            dep[i]=dep[pre[i][0]]+1;
            top[i]=pre[i][0]?top[pre[i][0]]:i;
        }
        if(!S.empty()) pt2[_i]=S.top();
    }
    return 1;
}

void pre_gao(){
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            pre[j][i]=pre[pre[j][i-1]][i-1];
}

int getLCA(int x,int y){
    if(top[x]^top[y]) return 0;
    if(dep[x]>dep[y]) swap(x,y);
    int dd=dep[y]-dep[x];
    for(int i=0,l=1;l<=dd;i++,l<<=1)
        if(dd&l) y=pre[y][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(pre[x][i]^pre[y][i])
            x=pre[x][i],y=pre[y][i];
    return pre[x][0];
}

void merge(int x,int y){
    int y0=y;
    y=getf(y);
    while((x=getf(x))^y){
        if(pre[x][0]^y0) f[x]=pre[x][0];
        x=pre[x][0];
    }
}

void query1(int x){
    printf("%d %d\n",pt2[p[x].first],pt2[p[x].second]);
}

void query2(int x){
    printf("%d %d\n",pt1[p[x].first],pt1[p[x].second]);
}

int gao(){
    int ans=1;
    static vector<pair<int,int> > qs;
    for(int i=1;i<=n;i++)
        if(!c[i]){
            int t1=pt2[p[i].first],t2=pt2[p[i].second];
            if((!t1 && !t2) || t1==t2) ans=ans*2%P;
            else if(!t1 || !t2){
                merge(t1+t2,0);
            }else{
                int lca=getLCA(t1,t2);
                if(t1==lca) merge(t2,t1);
                else if(t2==lca) merge(t1,t2);
                else{
                    merge(t1,lca); merge(t2,lca);
                    qs.push_back(make_pair(t1,t2));
                }
            }
        }
    for(auto i:qs)
        if(getf(i.first)^getf(i.second))
            f[f[i.first]]=f[i.second];
    for(int i=1;i<=n;i++)
        if(c[i] && getf(i)==i)
            ans=ans*2%P;
    return ans;
}

int main(){
#ifdef DEBUG
    freopen("356.in","r",stdin);
#endif
    n=read();
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++) p[i].first=read(),p[i].second=read();
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++) p1[p[i].first]=i;
    build(1,1,n<<1);
    memset(c,-1,sizeof c);
    for(int i=1;i<=n;i++)
        if(c[i]==-1) 
            bfs(i);
    if(!check()){
        puts("0");
        return 0;
    }
    pre_gao();
    printf("%d\n",gao());
}

查看详细内容

集训队作业之AGC011-F

2017-11-24 13:452017-11-24 13:45
集训队作业AtCoderDP线段树

传送门

这题难点是读题吧。。。(雾)

首先我们可以通过每层尽量往左移,使得$0\to N$的车不用在站点等待(即左上到右下的为一条直线),且至少有一个站点是会出现$0\to N$的车刚到,$N\to0$的车就马上从这个站点出发的情况(即两个方向的时间线会在某个站点处相交)。

我们可以进行DP,对于$i$号车站,处理出$N\to i$和$i\to0$最少的等待时间。为了转移这个DP,我们需要知道从一个站点开始,只要不会撞车就一直开,能一直开到哪个站点。如果我们把$B_i=2$的线段去掉,这其实就是从一个点引出射线,求跟已有线段的第一个交点的位置。这个直接用一个支持区间改值的线段树就行了。由于值域很大,需要动态开点,或者也可以离散化之后再做。DP完之后,我们直接枚举中间的交点,就能统计答案了。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

namespace Seg{
    struct node{
        int lc,rc,max;
    }a[20000010];

    int size;

    int newnode(){
        int x=++size;
        a[x].lc=a[x].rc=a[x].max=0;
        return x;
    }

    void init(){
        size=0;
        newnode();
    }

    void setMax(int x,int cl,int cr,int l,int r,int v){
        if(l<=cl && cr<=r){
            a[x].max=v;
            return;
        }
        int mid=(cl+cr)>>1;
        if(l<=mid){
            if(!a[x].lc) a[x].lc=newnode();
            setMax(a[x].lc,cl,mid,l,r,v);
        }
        if(r>mid){
            if(!a[x].rc) a[x].rc=newnode();
            setMax(a[x].rc,mid+1,cr,l,r,v);
        }
    }

    int getMax(int x,int cl,int cr,int pos){
        if(cl==cr) return a[x].max;
        int mid=(cl+cr)>>1;
        if(pos<=mid && a[x].lc) return max(a[x].max,getMax(a[x].lc,cl,mid,pos));
        if(pos>mid && a[x].rc) return max(a[x].max,getMax(a[x].rc,mid+1,cr,pos));
        return a[x].max;
    }
}

int n;
LL a[MAXN],b[MAXN],k,s[MAXN];
LL f1[MAXN],f2[MAXN];

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%lld",&n,&k);
    bool flag=1;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",a+i,b+i);
        if(b[i]==1) flag=0;
        s[i]=s[i-1]+a[i];
    }
    if(flag){
        printf("%lld\n",s[n]*2);
        return 0;
    }
    LL now=0;
    Seg::init();
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            int temp=min(k-1,now+2*a[i]-1);
            if(now+1<=temp) Seg::setMax(1,0,k-1,now+1,temp,i);
            if(now+2*a[i]-1>=k) Seg::setMax(1,0,k-1,0,now+2*a[i]-1-k,i);
        }
        now=(now+2*a[i])%k;
        int temp=Seg::getMax(1,0,k-1,now);
        if(!temp) f1[i]=s[i];
        else if(temp==i){
            puts("-1");
            return 0;
        }else{
            int pre=((now-(s[i]-s[temp])*2)%k+k)%k;
            f1[i]=f1[temp]+s[i]-s[temp]+(pre-now+k)%k;
        }
    }
    Seg::init();
    now=s[n]*2%k;
    for(int i=n;i>=1;i--){
        int temp=n-Seg::getMax(1,0,k-1,now)+1;
        if(temp==n+1) f2[i]=s[n]-s[i];
        else if(temp==i+1){
            puts("-1");
            return 0;
        }else{
            int pre=(now+(s[temp-1]-s[i])*2)%k;
            f2[i]=f2[temp-1]+s[temp-1]-s[i]+(now-pre+k)%k;
        }
        now=((now-2*a[i])%k+k)%k;
        if(b[i]==1){
            int temp=min(k-1,now+2*a[i]-1);
            if(now+1<=temp) Seg::setMax(1,0,k-1,now+1,temp,n-i+1);
            if(now+2*a[i]-1>=k) Seg::setMax(1,0,k-1,0,now+2*a[i]-1-k,n-i+1);
        }
    }
    LL ans=1LL<<62;
    for(int i=1;i<=n;i++)
        if(b[i]==1){
            ans=min(ans,f1[i]+f2[i]+s[n]);
        }
    printf("%lld\n",ans);
    return 0;
}

查看详细内容