Description

 

Input

Output

 

Sample Input

5 51 21 32 33 44 5

Sample Output

5

 

Data Constraint

 

Hint

样例解释

先拓扑排序，从出度为0的点开始搜，连这个点的前一个点以及之前的点都要和这个点连边，这样算出每个点能到达的其他点再减去已有的边就可以了。

然而需要用bitset优化状态，然而还有可能会爆空间，我们需要分几次搜索.....

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define N 1300000 6 using namespace std; 7 bitset<1001>qwq[N]; 8 int du[N/2],n,m,head[N],next[N],to[N],num,q[N/2],t; 9 long long ans;10 void add(int u,int v){11     num++;12     next[num]=head[u];13     to[num]=v;14     head[u]=num;15 }16 int main(){17     freopen("worldline.in","r",stdin);18     freopen("worldline.out","w",stdout);19     scanf("%d%d",&n,&m);20     ans=-m;21     num=0;22     for (int i=1,u=0,v=0;i<=m;i++){23         scanf("%d%d",&u,&v);24         add(u,v);25         du[v]++;26     }27     t=0;28     for (int i=1;i<=n;i++)29         if (!du[i]) q[++t]=i;30     for (int v=0,i=1;i<=t;i++)31         for (int j=head[q[i]];j;j=next[j]){32             v=to[j];33             du[v]--;34             if (!du[v]) q[++t]=v;35         }36     for (int l=1,r=1000;l<=n;l=r+1,r+=1000){37         for (int i=1;i<=n;i++) qwq[i].reset();38         for (int i=t;i>=1;i--){39             for (int j=head[q[i]];j;j=next[j]){40                 qwq[q[i]]|=qwq[to[j]];41             }42             ans+=qwq[q[i]].count();43             if ((q[i]>=l)&&q[i]<=r) qwq[q[i]][q[i]-l]=1; 44         }45     }46     printf("%lld\n",ans);47 }