问题描述

Gob和Michael常在一起打乒乓球。他们是这样决定比赛的输赢的：比赛由若干大局组成；谁最先赢下s大局谁就获得比赛的胜利；在每一大局中，谁先得t分就获得本大局的胜利。

在一次比赛中，他们只记录了比赛中的每一分是谁得的，但忘记了记录s和t。现在给出比赛的每一分的得分情况，求出所有可能的s和t。Gob保证，得分表是完整的，也就是在比赛恰好在最后一人，得到最后一分后结束。

输入格式(game.in)

第一行一个整数N，代表比赛一共得到了多少分。

第二行N个整数，代表比赛中每一分是谁得到的；1代表Gob，2代表Michael。

输出格式(game.out)

第一行一个整数M，代表共有多少种可能的s,t情况。

接下来M行每行两个整数si, ti，代表一种可能的s,t情况。M种情况按照s从小到大输出；在s相等时按照t从小到大输出。

样例输入1

5

1 2 1 2 1

样例输出1

2

1 3

3 1

样例输入2

5

1 2 2 2 1

样例输出2

0

样例输入3

10

1 1 2 1 1 1 2 2 1 1

样例输出3

3

1 7

3 2

7 1

数据范围与约束

对于50%的数据，N<=1000；

对于100%的数据，1<=N<=100,000。

这是一道好题。

解法：

我们可以枚举 t，对于某个t的值，那么s的值也就确定了。

但是需要注意一些细节：

1.赢得比赛的人必须是赢得最后一局的人。

2.比赛必须进行到最后，即计分要记到n。

3.两个人赢得局数不能相等。不能平局。

如果直接枚举，时间复杂度大概是个O(n^2)。这样可以得到70分。

N<=100000，可以联想到时间复杂度应该是O(n*logn)，是二分吧！

我们可以用两个数组分别记到某个位置Gob和Michael的得分前缀和。

每一局，如果要赢的这一局，就要在上一局得分的基础上在得t分，那就分别用二分在前缀和上查找这个得分，那显然是查找到的位置靠前的那个赢得这一局，那么不断更新得分，变换下标，一直到最后n。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define MOD 1000000007#define LL long longusing namespace std;int n,maxn;int G[100009],M[100009];struct H{ int s,t;}ans[100009];int cnt; bool cmp(H x,H y){ if(x.s