To spice it up, Petya and Gena choose new numbers s and t before every match. Besides, for the sake of history they keep a record of each match: that is, for each serve they write down the winner. Serve winners are recorded in the chronological order. In a record the set is over as soon as one of the players scores t points and the match is over as soon as one of the players wins s sets.
Petya and Gena have found a record of an old match. Unfortunately, the sequence of serves in the record isn't divided into sets and numbers s and t for the given match are also lost. The players now wonder what values of s and t might be. Can you determine all the possible options?
The first line contains a single integer n — the length of the sequence of games (1 ≤ n ≤ 105).
The second line contains n space-separated integers ai. If ai = 1, then the i-th serve was won by Petya, if ai = 2, then the i-th serve was won by Gena.
It is not guaranteed that at least one option for numbers s and t corresponds to the given record.
In the first line print a single number k — the number of options for numbers s and t.
In each of the following k lines print two integers si and ti — the option for numbers s and t. Print the options in the order of increasing si, and for equal si — in the order of increasing ti.
5
1 2 1 2 1
2
1 3
3 1
4
1 1 1 1
3
1 4
2 2
4 1
4
1 2 1 2
0
8
2 1 2 1 1 1 1 1
3
1 6
2 3
6 1
题意：给出比赛情况，输出所有满足条件的s,t，使得这场比赛有结果。
题目连接：http://codeforces.com/contest/496/problem/D
枚举t，然后二分找得分为t的下界，并更新每局的边界，判断谁获得当前局的胜利。最后的时候要注意判断最后一局的赢家是否是整场比赛的赢家。
#include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <set> #include <bitset> #include <queue> #include <stack> #include <string> #include <iostream> #include <cmath> #include <climits> using namespace std; const int maxn = 111111; const int INF = 0xfffffff; int sum1[maxn]; int sum2[maxn]; int n; int a[maxn]; int erfen1(int l,int r,int key) { int ans = INF; int k = l; while(l<=r){ int mid=(l+r)>>1; if(sum1[mid]-sum1[k-1] == key) ans=mid; if(sum1[mid]-sum1[k-1] >= key) r = mid-1; else l = mid+1; } return ans; } int erfen2(int l,int r,int key) { int ans = INF; int k = l; while(l<=r){ int mid=(l+r)>>1; if(sum2[mid] - sum2[k-1]==key) ans = mid; if(sum2[mid] - sum2[k-1]>=key) r = mid-1; else l = mid+1; } return ans; } int judge(int t) { int ans1 = 0;int ans2 = 0; int l = 1; while(l<=n){ int t1 = erfen1(l,n,t); int t2 = erfen2(l,n,t); l = min(t1,t2) + 1; if(l>n+1) return 0; if(t1==t2&&t1==INF) continue; if(t1<t2) ans1++; else ans2++; if(l-1==n){ if(ans1>ans2&&t1>t2) return 0; if(ans2>ans1&&t2>t1) return 0; } } if(ans1==ans2) return 0; return ans1>ans2? ans1:ans2; } struct Node { int x;int y; }; int cmp(const Node &a,const Node & b) { return a.x<b.x; } vector<Node > q; int main() { cin>>n; memset(sum2,0,sizeof(sum2)); memset(sum1,0,sizeof(sum1)); for(int i = 1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]==1) sum1[i] = 1; else sum2[i] = 1; } for(int i =1;i<=n;i++) sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1]; for(int t = 1;t<=n;t++){ int gg = judge(t); if(gg==0) continue; Node k ; k.x = gg; k.y = t; q.push_back(k); } sort(q.begin(),q.end(),cmp); printf("%d ",q.size()); for(int i = 0;i<q.size();i++) printf("%d %d ",q[i].x,q[i].y); return 0; }