~~~~~ ?????P3588 [POI2015] PUS ~~~~~ ?????總題單鏈接

思路

~~~~~ ?????這道題的關(guān)鍵點(diǎn)在于線段樹優(yōu)化建圖。

~~~~~ ?????對(duì)每條限制新建一個(gè)虛電 $p$，將輸入的 $x_{1～k}$ 連向 $p$，再將 $p$ 連向區(qū)間內(nèi)單的其他點(diǎn)，建完圖后拓?fù)渑判蚣纯伞?/p>

~~~~~ ?????但如果每個(gè)區(qū)間都是 $[1,100000]$ 且 $k=1$，那么就會(huì)連 $\sum k\times n$ 條邊。

~~~~~ ?????怎么辦，發(fā)揮想象力，用線段樹優(yōu)化建圖。

~~~~~ ?????每個(gè)限制的區(qū)間最多會(huì)被拆分成 $k+1$ 個(gè)區(qū)間，暴力枚舉區(qū)間，用線段樹建圖即可。

代碼

#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;
}