P3588 [POI2015] PUS

~~~~~      P3588 [POI2015] PUS ~~~~~      总题单链接

思路

~~~~~      这道题的关键点在于线段树优化建图。

~~~~~      对每条限制新建一个虚电 $p$，将输入的 $x_{1\sim k}$ 连向 $p$，再将 $p$ 连向区间内单的其他点，建完图后拓扑排序即可。

~~~~~      但如果每个区间都是 $[1,100000]$ 且 $k=1$，那么就会连 $\sum k\times n$ 条边。

~~~~~      怎么办，发挥想象力，用线段树优化建图。

~~~~~      每个限制的区间最多会被拆分成 $k+1$ 个区间，暴力枚举区间，用线段树建图即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;vector<ll>eg[500005];ll n,s,m,tot,usr;
ll vis[500005],din[500005],mx[500005];class{
public:struct Point{ll L,R,id;}po[400005];void build(ll x,ll y,ll p=1){po[p]={x,y,++tot};if(x==y){eg[po[p].id].push_back(x),din[x]++;return;}ll mid=(x+y)>>1;build(x,mid,p<<1);build(mid+1,y,p<<1|1);eg[po[p].id].push_back(po[p<<1].id),din[po[p<<1].id]++;eg[po[p].id].push_back(po[p<<1|1].id),din[po[p<<1|1].id]++;}void query(ll wc,ll x,ll y,ll p=1){if(po[p].R<x||po[p].L>y)return;if(po[p].L>=x&&po[p].R<=y){eg[wc].push_back(po[p].id);din[po[p].id]++;return;}query(wc,x,y,p<<1);query(wc,x,y,p<<1|1);}
}tr;queue<ll>que;
void tupo(){for(ll i=1;i<=tot;i++)if(!din[i])que.push(i);while(!que.empty()){ll u=que.front();que.pop();usr++;if(mx[u]<1||vis[u]>mx[u]){cout<<"NIE";exit(0);}for(ll v:eg[u]){din[v]--;if(u<=n)mx[v]=min(mx[v],mx[u]-1);else mx[v]=min(mx[v],mx[u]);if(din[v]==0)que.push(v);}}if(usr!=tot){cout<<"NIE";exit(0);}
}vector<ll>now;
signed main(){ios::sync_with_stdio(false);cin>>n>>s>>m;tot=n;for(ll i=1;i<=s;i++){ll x,y;cin>>x>>y;vis[x]=y;}tr.build(1,n);for(ll q=1;q<=m;q++){ll x,y,k;cin>>x>>y>>k;now.clear();for(ll i=1;i<=k;i++){ll g;cin>>g;now.push_back(g);}tot++;if(now[0]-1>=x)tr.query(tot,x,now[0]-1);for(ll i=1;i<now.size();i++){if(now[i-1]+1>now[i]-1)continue;tr.query(tot,now[i-1]+1,now[i]-1);}for(ll it:now)eg[it].push_back(tot),din[tot]++;if(y>=now[now.size()-1]+1)tr.query(tot,now[now.size()-1]+1,y);}for(ll i=1;i<=tot;i++){if(vis[i])mx[i]=vis[i];else mx[i]=1000000000;}tupo();cout<<"TAK"<<endl;for(ll i=1;i<=n;i++)cout<<mx[i]<<" ";return 0;
}