NYOJ 631 冬季长跑(逆序数＋单调递增序列个数)

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define N 1000000010
 5 int sum,n,p[50001][21],len[50001],L[21],R[21];
 6 
 7 void merger(int a[],int beg,int mid,int end)
 8 {
 9     int L_len=mid-beg,R_len=end-mid-1;
10     int i,j,k;
11     for(i=0;i<=L_len;i++)
12         L[i]=a[beg+i];
13     for(j=0;j<=R_len;j++)
14         R[j]=a[mid+j+1];
15     L[L_len+1]=R[R_len+1]=N;
16     i=j=0;
17     for(k=beg;k<=end;k++)
18     {
19         if(L[i]<=R[j])
20             a[k]=L[i++];
21         else
22         {
23             a[k]=R[j++];
24             sum+=L_len-i+1;
25         }
26     }
27 }
28 
29 void mergerSort(int a[],int beg,int end)
30 {
31     int mid=(beg+end)>>1;
32     if(beg<end)
33     {
34         mergerSort(a,beg,mid);
35         mergerSort(a,mid+1,end);
36         merger(a,beg,mid,end);
37     }
38 }
39 
40 void slove(int k)
41 {
42     int a = len[k]; len[k] = -1;
43     for(int i = k+1; i < n; ++i)
44     {
45         if(len[i] != -1 && len[i] > a)
46         {
47             a = len[i]; len[i] = -1;
48         }
49     }
50 }
51 
52 int main()
53 {
54    // freopen("in.txt","r",stdin);
55     int t,mi,i,j,ans;
56     cin>>t;
57     while(t--)
58     {
59         cin>>n;
60         for(i=0;i<n;++i)
61         {
62             cin>>mi; sum = 0;
63             for(j=0;j<mi;++j)
64                 cin>>p[i][j];
65             mergerSort(p[i],0,mi-1);
66             len[i] = sum;
67         }
68         ans = 0;
69         for(i=0;i<n;++i)
70         {
71             if(len[i] != -1)
72             {
73                 slove(i);
74                 ++ans;
75             }
76         }
77         cout<<ans<<endl;
78     }
79     return 0;
80 }