这题有点难度，自己目前理解不是很透彻，待填坑。%%% http://blog.csdn.net/u011542204/article/details/50769451
考虑暴力做法：每次从大的数向小的数连一条边，权值为1。然后跑一下拓扑，就可以知道所有数的大小关系了。 优化也是利用延迟修改：每次把一个区间拆成k段，然后找出线段树中每一段对应的标记，让这些标记去连边。最后也是跑一下拓扑序。 先开个坑：
#include<cmath> #include<cstdio> #include<vector> #include <queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 400010 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; int etr[N],tar[N*5],len[N*5],nxt[N*5],head[N],pos[N],ch[N][2],a[N],list[N],f[N]; int edgetot,tot,n,s,m,rt,i,x,l,r,h,t,nt; void add(int x,int y,int w) {etr[y]++; tar[++edgetot]=y; len[edgetot]=w; nxt[edgetot]=head[x]; head[x]=edgetot;} void build(int &x,int l,int r) { x = ++tot; if (l == r) {pos[l] = x; return;} int mid = (l + r) >> 1; build(ch[x][0],l,mid); build(ch[x][1],mid+1,r); add(ch[x][0],x,0); add(ch[x][1],x,0); } void ins(int rt,int l,int r,int L,int R) { if (L <= l && r <= R) {add(rt,tot,1); return;} int mid = (l + r) >> 1; if (L <= mid) ins(ch[rt][0],l,mid,L,R); if (mid < R) ins(ch[rt][1],mid+1,r,L,R); } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { scanf("%d%d%d",&n,&s,&m); build(rt,1,n); fo(i,1,s) {scanf("%d",&x); scanf("%d",&a[pos[x]]);} fo(i,1,m) { scanf("%d%d%d",&l,&r,&t); l--; tot++; while (t--) { scanf("%d",&x); add(tot,pos[x],0); if (l+1<x) ins(rt,1,n,l+1,x-1); l = x; } if (x < r) ins(rt,1,n,x+1,r); } h = t = 0; fo(i,1,tot) if (!etr[i]) {list[++t] = i; f[i] = 1;} while (h < t) { x = list[++h]; if (f[x] > inf) {puts("NIE"); return 0;} if (a[x] && f[x] > a[x]) {puts("NIE"); return 0;} else f[x] = max(f[x],a[x]); for (i = head[x]; i ; i = nxt[i]) { nt = tar[i]; f[nt] = max(f[nt],f[x]+len[i]); etr[nt]--; if (!etr[nt]) list[++t] = nt; } } if (tot > t) {puts("NIE"); return 0;} puts("TAK"); fo(i,1,n) printf("%d ",f[pos[i]]); printf("\n"); return 0; }