K. Topological Sort
题面
Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.
Your task is to find the lexicographically largest topological sort of the graph after removing a given list of edges.
A topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it.
Input
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.
Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.
No edge will appear in the list more than once.
Output
For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.
题意
给出N个点，每个对于每个对（u,v）若u<v，那么连一条边，给出m条边，先删除他们，问拓扑序字典序最大是多少。
考场上想了半天，大概最后想用最长路做，但是搞不定。。然后看题解嘛、。。 用线段树维护，操作有：区间修改 单点修改 查询最靠右0的位置。
代码
#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int m;
int x,y;
vector<int> g[100010];
int a[4000010];
int lazy[4000010];
void build(int l,int r,int o)
{
if (l==r)
{
a[o]=l-1;
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid+1,r,o<<1|1);
a[o]=min(a[o<<1],a[o<<1|1]);
return;
}
void push_down(int o)
{
lazy[o<<1]+=lazy[o];
lazy[o<<1|1]+=lazy[o];
a[o<<1]+=lazy[o];
a[o<<1|1]+=lazy[o];
lazy[o]=0;
}
void add(int L,int R,int l,int r,int o,int dlt)
{
if (L<=l && R>=r)
{
lazy[o]+=dlt;
a[o]+=dlt;
return;
}
push_down(o);
int mid=(l+r)>>1;
if (L<=mid) add(L,R,l,mid,o<<1,dlt);
if (R>mid) add(L,R,mid+1,r,o<<1|1,dlt);
a[o]=min(a[o<<1],a[o<<1|1]);
}
int query(int l,int r,int o)
{
if (l==r) return l;
push_down(o);
int mid=(l+r)>>1;
if (a[o<<1|1]==0) return query(mid+1,r,o<<1|1);
else return query(l,mid,o<<1);
}
int main()
{
ios::sync_with_stdio(false);
cin>>T;
while (T--)
{
cin>>n>>m;
memset(a,0,sizeof a);
memset(lazy,0,sizeof lazy);
build(1,n,1);
for (int i=1;i<=m;i++)
{
cin>>x>>y;
g[x].push_back(y);
add(y,y,1,n,1,-1);
}
for (int i=1;i<n;i++)
{
int find=query(1,n,1);
cout<<find<<" ";
if (find+1<=n) add(find+1,n,1,n,1,-1);
for (int o=0;o<g[find].size();o++) add(g[find][o],g[find][o],1,n,1,1);
add(find,find,1,n,1,2*n);
}
int find=query(1,n,1);
cout<<find<<endl;
for (int i=1;i<=n;i++) g[i].clear();
}
}