poj 2528_2

代码：

#include<iostream> #include<fstream>using namespace std;struct e{int l,r;bool isa; };e tree[80001]; int n;struct f{int num,s,l; };f b[20001];int c[10001][2];int cmp(const void *a,const void *b){f *s=(f*)a;f *t=(f*)b;return s->l-t->l; }void build(int s,int t,int p){tree[p].l=s;tree[p].r=t;tree[p].isa=0;if(s==t) return;int k=(s+t)>>1;build(s,k,p*2);build(k+1,t,2*p+1); }int update(int s,int t,int p){int i,j,k;if(s<=tree[p].l&&tree[p].r<=t){if(tree[p].isa==1) return 0;else{tree[p].isa=1;return 1;}}if(tree[p].isa) return 0;if(t<=tree[2*p].r){i= update(s,t,p*2);if(tree[2*p].isa&&tree[2*p+1].isa)tree[p].isa=1;return i;}elseif(s>=tree[2*p+1].l){ i= update(s,t,p*2+1);if(tree[2*p].isa&&tree[2*p+1].isa)tree[p].isa=1;return i; }else{i=update(s,t,p*2);j=update(s,t,p*2+1);if(tree[2*p].isa&&tree[2*p+1].isa)tree[p].isa=1;if(i||j) return 1;return 0;}}void read(){ // ifstream cin("in.txt");int i,j,k;int cas;cin>>cas;while(cas--){cin>>n;for(i=0;i<n;i++){cin>>b[2*i].l>>b[2*i+1].l;b[2*i].num=i+1;b[2*i].s=0;b[2*i+1].num=i+1;b[2*i+1].s=1;}qsort(b,2*n,sizeof(f),cmp);j=1;c[b[0].num][b[0].s]=1;for(i=1;i<2*n;i++){if(b[i].l!=b[i-1].l) j++;c[b[i].num][b[i].s]=j;}build(1,j,1);int ans=0;for(i=n;i>=1;i--){if(c[i][0]>c[i][1]) swap(c[i][0],c[i][1]);ans+=update(c[i][0],c[i][1],1);}cout<<ans<<endl;} }int main(){read();return 0; }

转载于:https://www.cnblogs.com/zhaozhe/archive/2011/05/16/2047509.html

总结

以上是生活随笔为你收集整理的poj 2528_2的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。