题意：
给定一个二进制的字符串，有 M次询问
问是否存在含有 a个 0 ，b个 1的区间
题解：
我们可以n2处理出每个区间，然后我们可以发现每个区间是一个矩形。
现在问题就转换成了有多少个点在这些矩形内。
然后就可以离散化后扫描线一下。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=2e6+7; 6 7 struct node 8 { 9 int op,x,a,b; 10 node(int _a=0,int _b=0,int _c=0,int _d=0):op(_a),x(_b),a(_c),b(_d){} 11 bool operator <(const node &B)const{return x!=B.x?x<B.x:op<B.op;} 12 }A[N]; 13 14 int t,n,m,x,y,a[2000],ed,cnt[2],tp[2]; 15 int hsh[N*2],h_ed,C[N]; 16 char ans[N]; 17 18 inline void add(int x,int c){while(x<=h_ed)C[x]+=c,x+=x&-x;} 19 inline int ask(int x){int an=0;while(x)an+=C[x],x-=x&-x;return an;} 20 int idx(int x){return lower_bound(hsh+1,hsh+1+h_ed,x)-hsh;} 21 22 23 int main(){ 24 scanf("%d",&t); 25 while(t--) 26 { 27 ed=0,scanf("%d%d",&n,&m); 28 F(i,1,n)scanf("%d",a+i); 29 F(i,1,n) 30 { 31 cnt[0]=cnt[1]=0; 32 cnt[!(i&1)]+=a[i]; 33 tp[0]=tp[1]=0; 34 tp[!(i&1)]+=a[i]; 35 A[++ed]=node(-1,cnt[0]-tp[0],cnt[1]-tp[1],cnt[1]); 36 A[++ed]=node(1,cnt[0],cnt[1]-tp[1],cnt[1]); 37 F(j,i+1,n) 38 { 39 cnt[!(j&1)]+=a[j]; 40 tp[0]=tp[1]=0; 41 tp[!(i&1)]+=a[i]; 42 tp[!(j&1)]+=a[j]; 43 A[++ed]=node(-1,cnt[0]-tp[0],cnt[1]-tp[1],cnt[1]); 44 A[++ed]=node(1,cnt[0],cnt[1]-tp[1],cnt[1]); 45 } 46 } 47 F(i,1,m) 48 { 49 scanf("%d%d",&x,&y); 50 A[++ed]=node(0,x,y,i); 51 } 52 sort(A+1,A+1+ed),h_ed=0; 53 F(i,1,ed) 54 { 55 if(A[i].op!=0)hsh[++h_ed]=A[i].a,hsh[++h_ed]=A[i].b; 56 else hsh[++h_ed]=A[i].a; 57 } 58 sort(hsh+1,hsh+1+h_ed),h_ed=unique(hsh+1,hsh+1+h_ed)-hsh-1; 59 F(i,1,ed) 60 { 61 if(A[i].op!=0)A[i].a=idx(A[i].a),A[i].b=idx(A[i].b); 62 else A[i].a=idx(A[i].a); 63 } 64 F(i,1,ed) 65 { 66 if(A[i].op) 67 { 68 add(A[i].a,-1*A[i].op); 69 add(A[i].b+1,A[i].op); 70 }else 71 { 72 int now=ask(A[i].a); 73 ans[A[i].b]=(now!=0)+'0'; 74 } 75 } 76 ans[m+1]=0; 77 printf("%s ",ans+1); 78 F(i,0,h_ed)C[i]=0; 79 } 80 return 0; 81 }