网址：https://www.luogu.com.cn/problem/P3588
给一个长度是$n$的正整数序列，范围$[1,1e9]$，给出了其中的$s$个数和$m$条信息，每条信息包含$l,r,k$和$k$个数，表示$a_l,a_l+1......a_r-1,a_r$里这$k$个数任意一个都比剩下的$r-l+1-k$个数严格大。构造一个合法的序列或者判断无解。
我们把严格大定义成有向图中从起点到终点的一条有向边，但是现在是一段连向一段，并且序列的长度达到$1e5$，所以普通方法建图，空间大小达不到要求。所以我们用线段树优化建图。把这个序列建成一棵线段树，然后对于每一个区间$[l,r]$，可以分割成$k+1$个小区间（区间内可以没有元素），然后因为这$r-l+1-k$个点都小于给出的$k$个点，则需要连接$k*(r-l+k-1)$条边，我们可以考虑连接超级结点，再连接到那$k$个点上。这样子每一次需要连接$r-l+1$条边，这样子仍然不能通过题目。考虑使用线段树，就只需要建立$k+log(r-l+1)$条边，线段树上有$nlogn$条边，总边数是$(\sum k)+klogn+nlogn$条边，可以通过。
对于每个提问，连向$k+1$个点连向超级结点的边边权是$1$，超级结点连向这$k$个点的边边权是$0$。为什么不能反过来呢？其实可以。然后线段树上显然是子节点向父节点连一条权值为$0$的边，连完边之后拓扑排序即可，如果发现整数的值大于$1e9$或者有环，则无解。
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1e6 + 5);
struct node
{
int l, r;
};
node tr[MAXN];
struct edge
{
int to, w;
edge() {}
edge(int _to, int _w) :to(_to), w(_w) {}
bool operator<(const edge& a)const
{
return w > a.w;
}
};
vector<edge>G[MAXN];
int cnt;
int deg[MAXN];
void build(int& rt, int l, int r)
{
if (l == r)
{
rt = l;
return;
}
rt = ++cnt;
int m = (l + r) >> 1;
build(tr[rt].l, l, m);
build(tr[rt].r, m + 1, r);
G[tr[rt].l].push_back(edge(rt, 0));
G[tr[rt].r].push_back(edge(rt, 0));
deg[rt] += 2;
}
void update(int rt, int l, int r, int ql, int qr, int v)
{
if (l > r)
return;
if (l <= ql && r >= qr)
{
G[rt].push_back(edge(v, 1));
++deg[v];
return;
}
int m = (ql + qr) >> 1;
if (l <= m)
update(tr[rt].l, l, r, ql, m, v);
if (r > m)
update(tr[rt].r, l, r, m + 1, qr, v);
}
queue<int>Q;
long long dis[MAXN];
int val[MAXN];
bool vis[MAXN];
bool toposort()
{
for (int i = 1; i <= cnt; ++i)
if (!deg[i])
{
Q.push(i);
dis[i] = val[i] ? val[i] : 1;
}
while (Q.size())
{
int u = Q.front();
Q.pop();
vis[u] = 1;
for (auto i : G[u])
{
int v = i.to, w = i.w;
--deg[v];
dis[v] = max(dis[v], dis[u] + w);
if (!vis[v] && !deg[v])
{
if (val[v])
{
if (dis[v] > val[v])
return false;
dis[v] = val[v];
}
Q.push(v);
}
}
}
for (int i = 1; i <= cnt; ++i)
if (!vis[i] || dis[i] > 1e9)
return false;
return true;
}
int rt;
int main()
{
int n, s, m;
scanf("%d%d%d", &n, &s, &m);
cnt = n;
int a, p;
while (s--)
{
scanf("%d%d", &a, &p);
val[a] = p;
}
int las, x, k, l, r;
build(rt, 1, n);
while (m--)
{
scanf("%d%d%d", &l, &r, &k);
las = l;
++cnt;
while (k--)
{
scanf("%d", &x);
update(rt, las, x - 1, 1, n, cnt);
G[cnt].push_back(edge(x, 0));
++deg[x];
las = x + 1;
}
update(rt, las, r, 1, n, cnt);
}
if (!toposort())
printf("NIE\n");
else
{
printf("TAK\n");
for (int i = 1; i <= n; ++i)
printf("%lld%c", dis[i], i == n ? ‘\n‘ : ‘ ‘);
}
return 0;
}
原文：https://www.cnblogs.com/Aya-Uchida/p/12324108.html