题意

有一个\(n\)个数的序列，已知其中的\(k\)个数，然后有\(m\)个信息，每个信息给出区间\([l,r]\)，和\(k\)个数，表示区间\([l,r]\)中这\(k\)个数大于剩下的\(r-l+1-k\)个数，求出一个方案。

分析

抄做的第一题线段树优化建图的题目，很巧妙。
大小关系我们可以看成是一条有向边，由小数连向大数，而两数之差就是边权，最后跑一遍拓扑排序，从最小的值更新，判断是否有环或者数值超过范围即可。
对于每一个信息，如果将大的数和小的数暴力两两连边，显然不行。
第一个优化是在两个数集之间加一个虚点，小数连向虚点，虚点连向大数，就相当于两两连边了，不过这样还是不够。
第二个优化就是用线段树来优化建图，因为给定的\(k\)个数其实是将区间\([l,r]\)分成\(k+1\)个小区间，这些小数集合，其实并不需要一一连边，只需要整个区间连向虚点即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define ls i<<1

#define rs i<<1|1

#define mid (l+r)/2

const int N=5e5+50;

const int INF=1e9;

struct Edge{

    int v,w,next;

}e[N*10];

int cnt,head[N],ind[N];

int n,s,m,l,r,k,x,a[N];

void init(){

    cnt=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v,int w){

    e[cnt]=Edge{v,w,head[u]};

    head[u]=cnt++;

    ind[v]++;

}

//记录每个线段树节点的实际编号(图论中的节点)

int pt[N],tot;

void build(int i,int l,int r){

    if(l==r){

        pt[i]=l;

        return;

    }

    pt[i]=++tot;

    build(ls,l,mid);

    build(rs,mid+1,r);

    add(pt[ls],pt[i],0);

    add(pt[rs],pt[i],0);

}

//线段树区间[ql,qr]对应的节点连向x(图)

void link(int i,int l,int r,int ql,int qr,int x){

    if(ql<=l && qr>=r){

        add(pt[i],x,0);

        return;

    }

    if(ql<=mid){

        link(ls,l,mid,ql,qr,x);

    }

    if(qr>mid){

        link(rs,mid+1,r,ql,qr,x);

    }

}

int ans[N],vis[N];

bool topo(){

    queue<int> q;

    int c=0;

    for(int i=1;i<=tot;i++){

        if(!ind[i]){

            q.push(i);

        }

        if(!ans[i]){

            //还不确定的数

            ans[i]=1;

        }

    }

    while(!q.empty()){

        int u=q.front();

        q.pop();

        c++;

        for(int i=head[u];i!=-1;i=e[i].next){

            int v=e[i].v;

            int w=e[i].w;

            ans[v]=max(ans[v],ans[u]+w);

            if(a[v] && ans[v]>a[v]){

                return false;

            }

            --ind[v];

            if(!ind[v]){

                q.push(v);

            }

        }

    }

    return c==tot;

}

int main(){

//    freopen("in.txt","r",stdin);

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

    init();

    //线段树n个叶子节点1-n，然后其他父节点就++tot

    tot=n;

    build(1,1,n);

    for(int i=1;i<=s;i++){

        scanf("%d%d",&k,&x);

        a[k]=ans[k]=x;

    }

    //对于给定的k个数也就是集合S1，都大于等于[l,r]剩下的数S2，因此需要两两连边

    //优化1 建立虚点，S2连向虚点，虚点连向S1

    //优化2 S2都是一些连续区间，可以用线段树来优化建图，让线段树区间连向虚点

    for(int i=1;i<=m;i++){

        scanf("%d%d%d",&l,&r,&k);

        tot++;

        int p=l-1;

        //k个数将区间分为k+1段，对应的线段树区间分别连向虚点

        for(int j=1;j<=k;j++){

            scanf("%d",&x);

            //虚点连向S1

            add(tot,x,1);

            //连续区间连向虚点

            if(x>p+1){

                //和上一个点之间有一段连续区间

                link(1,1,n,p+1,x-1,tot);

            }

            p=x;

        }

        if(x<r){

            link(1,1,n,x+1,r,tot);

        }

    }

    //拓扑排序求出方案

    bool flag=topo();

    if(!flag){

        printf("NIE\n");

        return 0;

    }

    for(int i=1;i<=n;i++){

        if(ans[i]>INF){

            printf("NIE\n");

            return 0;

        }

    }

    printf("TAK\n");

    for(int i=1;i<=n;i++){

        printf("%d%c",ans[i],i==n?'\n':' ');

    }

    return 0;

}

巴特西

luoguP3588_[POI2015]PUS

题意

分析

代码

最新文章

热门文章