ZJT's Blog

大変に気分がいい~

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

2018-6-5 3:132018-6-5 3: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());
}

查看详细内容

集训队作业之AGC002-D

2017-10-7 20:112017-10-7 20:11
集训队作业AtCoder整体二分并查集可持久化

传送门

裸的整体二分+可持久化并查集。

直到现在才彻底搞清楚可持久化并查集的时间戳到底是怎么打的。。。我好菜啊。。。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 100010
using namespace std;

int n,m,numq;
int e[MAXN][2];
int f[MAXN],rk[MAXN],tf[MAXN];
vector< pair<int,int> > size[MAXN];
int ans[MAXN];

struct Query{
    int x1,x2,k,id;
}q[MAXN],q0[MAXN];

int getf(int x,int t){
    while(x!=f[x] && tf[x]<=t) x=f[x];
    return x;
}

int getsize(int x,int t){
    int l=0,r=size[x].size()-1;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(size[x][mid].first<=t) l=mid;
        else r=mid-1;
    }
    return size[x][l].second;
}

void build(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        size[i].push_back(make_pair(0,1));
    }
    for(int i=1;i<=m;i++){
        int x=getf(e[i][0],m),y=getf(e[i][1],m);
        if(x==y) continue;
        if(rk[x]<rk[y]) x^=y^=x^=y;
        f[y]=x;
        tf[y]=i;
        if(rk[x]==rk[y]) rk[x]++;
        size[x].push_back(make_pair(i,size[x][size[x].size()-1].second+size[y][size[y].size()-1].second));
    }
}

void solve(int l,int r,int ql,int qr){
    if(ql>qr) return;
    if(l==r){
        for(int i=ql;i<=qr;i++)
            ans[q[i].id]=l;
        return;
    }
    int mid=(l+r)>>1;
    for(int i=ql;i<=qr;i++) q0[i]=q[i];
    int now1=ql-1,now2=qr+1;
    for(int i=ql;i<=qr;i++){
        int x1=q0[i].x1,x2=q0[i].x2,k=q0[i].k;
        x1=getf(x1,mid); x2=getf(x2,mid);
        int res=getsize(x1,mid);
        if(x1!=x2) res+=getsize(x2,mid);
        if(res>=k) q[++now1]=q0[i];
        else q[--now2]=q0[i];
    }
    solve(l,mid,ql,now1);
    solve(mid+1,r,now2,qr);
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&e[i][0],&e[i][1]);
    scanf("%d",&numq);
    for(int i=1;i<=numq;i++){
        scanf("%d%d%d",&q[i].x1,&q[i].x2,&q[i].k);
        q[i].id=i;
    }
    build();
    solve(1,m,1,numq);
    for(int i=1;i<=numq;i++)
        printf("%d\n",ans[i]);
    return 0;
}

查看详细内容

集训队作业之AGC006-F

2017-10-7 16:572017-10-7 16:59
集训队作业AtCoder结论题并查集拆点

传送门

这一题从看题到AC总共花了4.5h,有大概3h都在盯着草稿纸发呆。。。还是要提高一个做题的效率。

首先显然可以把每个格子转成有向图的一条边,然后就变成了可以选$u\to v,v\to w$两条边,然后加上$w\to u$这条新边,然后问最后最多能有多少边。

考虑每条边是怎么产生的。产生一条新边需要两条已有的边,所以我们每次可以把一条边分成两条边,一直分下去,最后能得到一个已有的边组成的序列,并且这个序列的边不考虑方向时是图中的一条路径(不一定是简单路径)。考虑沿着这条路径走,每走一步可能是沿着这条边的方向走,也可能是逆着他的方向走。记正着走是1,反着走是-1,那么这个路径就能表示成1和-1组成的一个边权的序列。

考虑这个序列合法(即这些边最终能凑出一条连接路径两端的边)的条件。首先所有边权的和必须模3余1。这是因为两个-1能拼成一个1,两个1能拼成一个-1,而这些转换的过程都保证了所有边权的和在模3意义下是不变的。既然最终需要拼成一条正向的边,而一条正向边的权值是1,那所有边权的和就只能一直为1了。

上面仅仅是一个必要条件,而且确实有反例,比如$1,-1,1,...,1,-1,1$。这时我们需要一个充分必要条件。注意到反例的序列中相邻的元素都不同,那是不是只要存在两个相邻元素相同,就能直接说明序列合法呢?事实上这个结论是正确的(就是这个鬼结论我tm证了半小时)。考虑归纳,当结论对所有长度为$n-1$的序列都成立时,考虑任何一个长度为$n$且元素和模3余1的序列。

这时可以分类讨论:

  1. 如果序列中每个元素都相等,这时可以构造出一种方法,使得最后恰好剩下一个1。
  2. 如果前两个就相等了,那就找到从前往后第一个不同的元素,并把这个元素前的两个相同元素合并。合并完之后,产生出来的新值就和后面那个一样了,这时满足归纳条件,可以直接归纳到$n-1$的情况。
  3. 如果前面两个不同,就找到从前往后第一个相邻两个元素相同的位置,并把这两个元素合并,这时新的值就与前面的那个值相同了,可以归纳。

证完了这个结论之后,好像并没有什么用。。。?考虑一条不符合这个性质的路径(就是上面的那个反例),前缀和一直在1和0之间切换。那是不是只要前缀和达到过2,就能符合这个性质了呢?事实上这个也是成立的(这个很好证,我这里就不证了)。所以我们从一个点开始,维护一个边权和(初始为0),可以沿着一条边的方向走,也可以逆着一条边的方向走。前者边权和+1(模3意义下),后者-1。只要边权和到达过2,并且最终停在某个点时边权和为1,那么就能拼出一条初始点到这个点的单向边。

这时我们可以把每个点拆成5个点,编号分别是$0,1,2,0',1'$。0号点和$0'$号点代表边权和模3为0的状态,$1、1'、2$同理。0和$0'$的区别在于0的状态不曾到达过2,而$0'$曾经到达过2。这样的话,对于原图中的每条边,分别在$(0,1),(1,2),(0,2),(0',1'),(1',2),(0',2)$之间连上相应的边。只要一个点从对应的0号点出发,能到达另一个点对应的$1'$号点,那么这两个点之间就可以拼出一条有向边。注意到这个图实际上是个无向图,所以处理出所有连通块之后统计一下就行了。注意特判原图中的边的情况,按照这个走法不一定能统计到原图中的边。

感觉这个题还是挺妙的。最后拆5个点那一步一直想不到,想了半天之后突然之间就想出来了,想的过程中还得到了一堆错误结论+错误做法。AC之后看了看题解和别人的AC代码,好像跟我的完全不一样??奥妙重重.jpg

其实比较好奇别人怎么做的。。。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 1000010
#define LL long long

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int p[MAXN][5],nump;
int e2[MAXN][2];
int f[MAXN],visit[MAXN];
int cnt[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
    e[nume]=edge(u,g[v]);
    g[v]=nume++;
}

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

void dfs(int x){
    visit[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            f[getf(e[i].to)]=getf(x);
            dfs(e[i].to);
        }
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(int j=0;j<5;j++)
        for(int i=1;i<=n;i++) 
            p[i][j]=++nump;
    for(int i=1;i<=nump;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&e2[i][0],&e2[i][1]);
        int u=e2[i][0],v=e2[i][1];
        addEdge(p[u][0],p[v][1]);
        addEdge(p[u][1],p[v][2]);
        addEdge(p[u][2],p[v][0]);
        addEdge(p[u][2],p[v][4]);
        addEdge(p[u][3],p[v][2]);
        addEdge(p[u][4],p[v][3]);
    }
    for(int i=1;i<=nump;i++)
        if(!visit[i])
            dfs(i);
    for(int i=1;i<=n;i++) cnt[getf(p[i][3])]++;
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans+=cnt[getf(p[i][0])];
    for(int i=1;i<=m;i++)
        if(getf(p[e2[i][0]][0])!=getf(p[e2[i][1]][3]))
            ans++;
    printf("%lld\n",ans);
    return 0;
}

查看详细内容