思路:这题的思路很容易想到,把所有时间点离散化,然后按时间一步一步来,当到达时间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;elseflower[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;elseflower[Index[i].pos].r=++num;}}elseif(Index[i].type==1){qt[Index[i].pos].val=num;}else{if(Index[i].l)flower[Index[i].pos].l=num;elseflower[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:\n",++Case);for(i=1;i<=m;i++)printf("%d\n",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;elseIndex[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:\n",++Case);for(i=nx+1;i<=mx;i++){// cout<<Index[i]<<endl;printf("%d\n",Sum(Index[i]));}}return 0; }