?
【題目鏈接】?http://acm.hdu.edu.cn/showproblem.php?pid=5741
?
【題目大意】
一個01相間的串，以0開頭，給出的序列每個數字表示連續的0的個數或者1的個數，現在有m個詢問，求0的個數為a且1的個數為b的串是否存在。
?
【題解】
我們發現形如11001這樣子以1為開頭結尾的串是包含1001這樣子的串的，同理以0為開頭結尾的串也是包含了一些開頭結尾數字相同的子串。
可以發現，當0的個數固定，1的個數是數軸上的一個區間，而且在0的個數相差1時，必定可以取到相同的1的個數，因此可行域在二維平面內是一個實心的聯通圖，且上邊界和下邊界的點坐標單調非減。
那么我們首先計算出上下邊界的點，可以發現在0的個數固定的情況下，1的個數的上界一定是由1開始，1結尾的子串產生的，下界是由0開始，0結尾的子串產生的，那么保存這些點。
然而在圖形中兩個橫縱坐標都不相同的點就能夠確定一個矩形可行區域，因此，只要保留上下邊界坐標均單調遞增的點即可，二分查詢(a,b)是否在連通塊區域內，就能夠判斷是否存在這樣子的子串
?
【代碼】
#include <cstdio>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;
const int N=1010,M=N*N;
typedef pair<int,int> PII;
char ans[M];
int T,n,m,a,b,t[N],cntd,cntu,cnt;
PII D[M],U[M];
int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&t[i]);cntd=cntu=cnt=0;for(int i=0;i<n;i++){int x=0,y=0;for(int j=i;j<n;j++){if(j%2)y+=t[j];else x+=t[j];if(i%2==0&&j%2==0)D[cntd++]=PII(x,y);if(i%2&&j%2)U[cntu++]=PII(x,y);}}sort(D,D+cntd);for(int i=0,j;i<cntd;i=j){for(j=i;j<cntd&&D[i].first==D[j].first;j++);while(cnt&&D[cnt-1].second>=D[i].second)cnt--;D[cnt++]=D[i]; }cntd=cnt;sort(U,U+cntu); cnt=0;for(int i=0,j;i<cntu;i=j){for(j=i;j<cntu&&U[i].first==U[j].first;j++);if(!n||U[cnt-1].second<U[j-1].second)U[cnt++]=U[j-1];}cntu=cnt;for(int i=0;i<m;i++){scanf("%d%d",&a,&b);int x=upper_bound(U,U+cntu,PII(a,INT_MAX))-U;int y=upper_bound(D,D+cntd,PII(a,INT_MIN))-D;ans[i]='0'+(y<cntd&&U[x-1].second>=b&&D[y].second<=b);}ans[m]=0; puts(ans);}return 0;
}
?
?
)
