首页 > 代码库 > hdu 5741 Helter Skelter(扫描线)
hdu 5741 Helter Skelter(扫描线)
题目链接:hdu 5741 Helter Skelter
题意:
给定一个二进制的字符串,有 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\n",ans+1); 78 F(i,0,h_ed)C[i]=0; 79 } 80 return 0; 81 }
hdu 5741 Helter Skelter(扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。