思路：这题的思路很容易想到，把所有时间点离散化，然后按时间一步一步来，当到达时间i的时候处理所有在i处的查询。
这个代码怎一个挫字了得
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define Maxn 100010 #define lowbit(x) (x&(-x)) using namespace std; int C[Maxn*3],n,ans[Maxn]; struct Flower{ int l,r; }flower[Maxn]; struct Lisan{ int val,type,l; int pos; int operator <(const Lisan &temp) const { return val<temp.val; } }Index[Maxn*4]; struct QT{ int val,i; int operator <(const QT &temp) const { return val<temp.val; } }qt[Maxn]; int Sum(int pos) { int sum=0; while(pos) { sum+=C[pos]; pos-=lowbit(pos); } return sum; } void update(int pos,int val) { while(pos<=n) { C[pos]+=val; pos+=lowbit(pos); } } vector<int> q[Maxn*3]; int main() { int i,j,m,t,Case=0; scanf("%d",&t); while(t--) { memset(C,0,sizeof(C)); scanf("%d%d",&n,&m); int cnt=0; for(i=1;i<=n;i++) { scanf("%d%d",&flower[i].l,&flower[i].r); Index[++cnt].val=flower[i].l,Index[cnt].pos=i,Index[cnt].type=0,Index[cnt].l=1,Index[++cnt].val=flower[i].r,Index[cnt].type=0,Index[cnt].pos=i,Index[cnt].l=0; } for(i=1;i<=m;i++) { scanf("%d",&qt[i].val); qt[i].i=i; Index[++cnt].val=qt[i].val; Index[cnt].type=1; Index[cnt].pos=i; } sort(Index+1,Index+1+cnt); //cout<<"ok"<<endl; int num=0; if(Index[1].type==1) { qt[Index[1].pos].val=++num; } else { if(Index[1].l) flower[Index[1].pos].l=++num; else flower[Index[1].pos].r=++num; } for(i=2;i<=cnt;i++) { if(Index[i].val>Index[i-1].val) { if(Index[i].type==1) { qt[Index[i].pos].val=++num; } else { if(Index[i].l) flower[Index[i].pos].l=++num; else flower[Index[i].pos].r=++num; } } else if(Index[i].type==1) { qt[Index[i].pos].val=num; } else { if(Index[i].l) flower[Index[i].pos].l=num; else flower[Index[i].pos].r=num; } } for(i=1;i<=num;i++) q[i].clear(); for(i=1;i<=n;i++) { q[flower[i].l].push_back(1); q[flower[i].r].push_back(-1); } sort(qt+1,qt+m+1); int r=1; n=num+1; for(i=1;i<=num;i++) { cnt=0; if(r>m) break; int size=q[i].size(); for(j=0;j<size;j++) { update(i,q[i][j]); if(q[i][j]<0) cnt++; } while(qt[r].val==i&&r<=m) { ans[qt[r].i]=Sum(qt[r].val)+cnt; r++; } } printf("Case #%d: ",++Case); for(i=1;i<=m;i++) printf("%d ",ans[i]); } return 0; }
这个代码就简洁多了：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define Maxn 100010 #define lowbit(x) (x&(-x)) using namespace std; int C[Maxn*2],n,Index[Maxn*3]; struct Node{ int val,pos; int operator <(const Node &temp) const { return val<temp.val; } }node[Maxn*3]; int Sum(int pos) { int sum=0; while(pos) { sum+=C[pos]; pos-=lowbit(pos); } return sum; } void update(int pos,int val) { while(pos<=n) { C[pos]+=val; pos+=lowbit(pos); } } int main() { int t,m,i,j,Case=0; scanf("%d",&t); while(t--) { memset(C,0,sizeof(C)); scanf("%d%d",&n,&m); int nx=n<<1; int mx=nx+m; for(i=1;i<=mx;i++) { scanf("%d",&node[i].val); node[i].pos=i; } sort(node+1,node+mx+1); int cnt=0; Index[node[1].pos]=++cnt; for(i=2;i<=mx;i++) { if(node[i].val==node[i-1].val) Index[node[i].pos]=cnt; else Index[node[i].pos]=++cnt; } n=cnt+10; for(i=1;i<=nx;i++) { //cout<<Index[i]<<" * "; update(Index[i++],1); update(Index[i]+1,-1); // cout<<Index[i]+1<<endl; } printf("Case #%d: ",++Case); for(i=nx+1;i<=mx;i++) { // cout<<Index[i]<<endl; printf("%d ",Sum(Index[i])); } } return 0; }