题目分享H 二代目

题意：有m个限制，每个限制l1,r1,l2,r2四个数，限制了一个长度为n的数第l1到r1位要与第l2到r2相同，保证r1-l1=r2-l2，求在限制下一共有多少种数

分析：

暴力的话肯定是从l1-r1扫一遍用并查集，但显然时间和空间都是不允许的

但再一想，这是不是相当于区间并？操作

看到区间的东西，我直接就往线段树去想了

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

#define pii pair<int,int>

#define ll long long

const int mod=1e9+;

map<pii,pii> fa;

int n;

pii find(pii x)

{

    while(x!=fa[x]) x=fa[x];

    return x;

}

pii ya(pii x)

{

    pii fax=find(x),nowfa;

    while(x!=fax)

    {

        nowfa=fa[x];

        fa[x]=fax;

        x=nowfa;

    }

    return fax;

}

void bing(pii x,pii y)

{

    pii fax=ya(x),fay=ya(y);

    fa[fay]=fax;

}

void down(int l,int r)

{

    int mid=l+r>>;

    int p=ya(make_pair(l,r)).first-l;

    bing(make_pair(l,mid),make_pair(l+p,mid+p));

    bing(make_pair(mid+,r),make_pair(mid++p,r+p));

}

void dfs(int l,int r,int left,int right,int p)

{

    if(l>=left&&r<=right)

    {

        bing(make_pair(l,r),make_pair(l+p,r+p));

        return;

    }

    down(l,r);

    int mid=l+r>>;

    if(left<=mid) dfs(l,mid,left,right,p);

    if(mid>right) dfs(mid+,r,left,right,p);

}

void mem(int l,int r)

{

    fa[make_pair(l,r)]=make_pair(l,r);

    if(l==r) return;

    int mid=l+r>>;

    mem(l,mid);mem(mid+,r);

}

void get_ans(int l,int r)

{

    if(l==r) return;

    down(l,r);

    int mid=l+r>>;

    get_ans(l,mid);get_ans(mid+,r);

}

ll pow(int x,int y)

{

    ll now=(ll)x,ans=1ll;

    while(y)

    {

        if(y&) ans*=now,ans%=(ll)mod;

        y>>=;now*=now,now%=(ll)mod;

    }

    return ans;

}

int main()

{

    int m,l1,r1,l2,r2;

    scanf("%d%d",&n,&m);

    mem(,n);

    while(m--)

    {

        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

        dfs(,n,l1,r1,l2-l1);

    }

    get_ans(,n);

    int ans=-;

    for(int i=;i<=n;i++) if(fa[make_pair(i,i)]==make_pair(i,i)) ans++;

    printf("%d",(int)(pow(,ans)*%mod));

    return ;

}

然鹅，这个pair可能有点不好开，导致全员MLE

不过处理区间的东西，ST表也是有地位的

于是就能往ST表那里去想

首先ST表传统艺能肯定是f[x][k]表示x到x+(1<<k)左闭右开怎么怎么样，

那么这里就应该表示x到x+(1<<k)左闭右开的父亲是谁（因为要搞并查集）

而这里的父亲应该对应另一个y到y+(1<<k)的区间，因为我们的k是已知的，所以其实f[x][k]只需要记录这个y即可，也就是对应区间的左端点

而这m组将两个区间并起来的操作时，也应该像lca向上跳一样，从maxlg往下慢慢找符合的k，然后再讲x跳到其对应的x+(1<<k)位置上

这里有一点值得注意，其实我们这里也可以按照平日ST表那样只将l到l+(1<<k)与 r-(1<<k)+1,r+1这两个区间与对应的区间合并（这里k应该是小于等于r-l的最大的k）

但我认为这样不如像lca那样快，如果有和我意见不相同的可以讨论一波

但你肯定马上就会想，这只合并两个，而lca合并很多个区间，但这些合并其实都要下放的

为了方便统计，最后要干的是将所有的结果下传，达到每个单个的位置对应一个位置的效果，

这又类似线段树了，下传标记

这应该很好理解，ya（）后得到的是f[x][y]所对应的根节点区间的左端点，这里bing传的三个参数分别为l1，l2，k，也就是把l1到l1+(1<<k)左闭右开与l2到l2+(1<<k)左闭右开合并

最后得到每个单个位置对应的位置，只需要数数有多少个f[x][0]=x即可（f[x][0]=x表示这个x是这个并查集的根节点）

对了，还有一个小问题，你统计出来的这个值是指能自由取数的个数，但显然这其中一定有一个位置与首位相关，这个位置只能取1-9，别的位置则能取0-9

所以最后结果应该是9*10^(count-1)

代码：

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

#define ll long long

const int mod=1e9+;

const int maxn=1e5+;

const int maxlg=2e1+;

int fa[maxn][maxlg];

int n;

int find(int x,int y)

{

    while(x!=fa[x][y]) x=fa[x][y];

    return x;

}

int ya(int x,int y)

{

    int fax=find(x,y),nowfa;

    while(x!=fax)

    {

        nowfa=fa[x][y];

        fa[x][y]=fax;

        x=nowfa;

    }

    return fax;

}

void bing(int x1,int x2,int y)

{

    int fax=ya(x1,y),fay=ya(x2,y);

    fa[fay][y]=fax;

}

void down(int x,int y)

{

    int nowx=ya(x,y);

    bing(x,nowx,y-);

    bing(x+(<<y-),nowx+(<<y-),y-);

}

void get_ans()

{

    for(int i=maxlg-;i;i--) for(int j=;j<=n;j++) if(j+(<<i)<=n+) down(j,i);

}

void mem()

{

    for(int i=;i<maxlg;i++) for(int j=;j<=n;j++) if(j+(<<i)<=n+) fa[j][i]=j;

}

ll pow(int x,int y)

{

    ll now=(ll)x,ans=1ll;

    while(y)

    {

        if(y&) ans*=now,ans%=(ll)mod;

        y>>=;now*=now,now%=(ll)mod;

    }

    return ans;

}

int main()

{

    int m,l1,r1,l2,r2;

    scanf("%d%d",&n,&m);

    mem();

    while(m--)

    {

        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

        int now=r1-l1+;

        for(int i=maxlg-;i>=;i--)

        {

            if((<<i)<=now)

            {

                bing(l1,l2,i);now-=(<<i);

                l1+=(<<i);l2+=(<<i);

            }

        }

    }

    get_ans();

    int ans=-;

    for(int i=;i<=n;i++) if(fa[i][]==i) ans++;

    printf("%d",(int)(pow(,ans)*%mod));

    return ;

}

巴特西

题目分享H 二代目

最新文章

热门文章