亲宝软件园·资讯

展开

题目分享H 二代目

lin4xu 人气:1

题意:有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+7;

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>>1;
    int p=ya(make_pair(l,r)).first-l;
    bing(make_pair(l,mid),make_pair(l+p,mid+p));
    bing(make_pair(mid+1,r),make_pair(mid+1+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>>1;
    if(left<=mid) dfs(l,mid,left,right,p);
    if(mid>right) dfs(mid+1,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>>1;
    mem(l,mid);mem(mid+1,r);
}

void get_ans(int l,int r)
{
    if(l==r) return;
    down(l,r);
    int mid=l+r>>1;
    get_ans(l,mid);get_ans(mid+1,r);
}

ll pow(int x,int y)
{
    ll now=(ll)x,ans=1ll;
    while(y)
    {
        if(y&1) ans*=now,ans%=(ll)mod;
        y>>=1;now*=now,now%=(ll)mod;
    }
    return ans;
}

int main()
{
    int m,l1,r1,l2,r2;
    scanf("%d%d",&n,&m);
    mem(1,n);
    while(m--)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        dfs(1,n,l1,r1,l2-l1);
    }
    get_ans(1,n);
    int ans=-1;
    for(int i=1;i<=n;i++) if(fa[make_pair(i,i)]==make_pair(i,i)) ans++;
    printf("%d",(int)(pow(10,ans)*9%mod));
    return 0;
}

然鹅,这个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是这个并查集的根节点)

代码:

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

#define ll long long

const int mod=1e9+7;
const int maxn=1e5+1;
const int maxlg=2e1+1;

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-1);
    bing(x+(1<<y-1),nowx+(1<<y-1),y-1);
}

void get_ans()
{
    for(int i=maxlg-1;i;i--) for(int j=1;j<=n;j++) if(j+(1<<i)<=n+1) down(j,i);
}

void mem()
{
    for(int i=0;i<maxlg;i++) for(int j=1;j<=n;j++) if(j+(1<<i)<=n+1) fa[j][i]=j;
}

ll pow(int x,int y)
{
    ll now=(ll)x,ans=1ll;
    while(y)
    {
        if(y&1) ans*=now,ans%=(ll)mod;
        y>>=1;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+1;
        for(int i=maxlg-1;i>=0;i--)
        {
            if((1<<i)<=now)
            {
                bing(l1,l2,i);now-=(1<<i);
                l1+=(1<<i);l2+=(1<<i);
            }
        }
    }
    get_ans();
    int ans=-1;
    for(int i=1;i<=n;i++) if(fa[i][0]==i) ans++;
    printf("%d",(int)(pow(10,ans)*9%mod));
    return 0;
}

 

加载全部内容

相关教程
猜你喜欢
用户评论