题意：bc round 74
分析：
参考下普通的用堆维护求字典序最小拓扑序, 用某种数据结构维护入度小于等于k的所有点, 每次找出编号最小的, 并相应的减少k即可.
这个数据结构可以用线段树, 建立一个线段树每个节点[l,r]维护编号从ll到rr的所有节点的最小入度, 查询的时候只需要在线段树上二分,
找到最小的x满足入度小于等于k.
复杂度O((n+m)logn)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
typedef long long LL;
const int mod=1e9+;
const int INF=0x3f3f3f3f;
const int N=1e5+;
int d[N],o[N<<],head[N],p;
struct Edge
{
int v,next;
}edge[N*];
void add(int u,int v)
{
edge[p].v=v;
edge[p].next=head[u];
head[u]=p++;
}
void pushup(int rt)
{
o[rt]=min(o[rt*],o[rt*+]);
}
void build(int rt,int l,int r)
{
if(l==r)
{
o[rt]=d[l];
return;
}
int mid=(l+r)>>;
build(rt*,l,mid);
build(rt*+,mid+,r);
pushup(rt);
}
void update(int rt,int l,int r,int pos)
{
if(l==r)
{
o[rt]=d[l];
return;
}
int mid=(l+r)>>;
if(pos<=mid)update(rt*,l,mid,pos);
else update(rt*+,mid+,r,pos);
pushup(rt);
}
int query(int rt,int l,int r,int c)
{
if(l==r)
return l;
int mid=(l+r)>>;
if(o[rt*]<=c)return query(rt*,l,mid,c);
else return query(rt*+,mid+,r,c);
}
int main()
{
int T,n,m,k;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-,sizeof(head));
memset(d,,sizeof(d));
p=;
for(int i=;i<m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
++d[v];
}
build(,,n);
LL ans=;
for(int i=;i<=n;++i)
{
LL x=query(,,n,k),y=i;
ans=(ans+x*y%mod)%mod;
k-=d[x];
d[x]=INF;
update(,,n,x);
for(int j=head[x];~j;j=edge[j].next)
{
int v=edge[j].v;
if(d[v]==INF)continue;
--d[v];
update(,,n,v);
}
}
printf("%I64d\n",ans);
}
return ;
}