cqoi2015任务查询系统（bzoj3932洛谷P2015）

题目分析

看到“前k小”，有没有想到主席树？

我们可以对每个时间点为根来建立主席树，然后可以差分。就是每个任务开始的时间+pos（优先级），每个任务结束的时间-pos，最后求存在k个元素的时候的前缀和。

提醒

这是我写的第二个主席树的题目，所以我真是弱爆了......因为没想到差分，这题只打了暴力......我可以退役了......

一定注意，求前缀和的时候，左半边子树的前缀要加起来！！！

然后就是，假如这个时间点i是没有任务开始也没有任务结束的，注意root[i]=root[i-1]。

然后就是，如果在查询时l==r，可能元素个数还是大于k，所以.....看代码

然后就是，要开long long,还要开40倍空间（我问同机房的jar形主席树要开多大空间，他说开到MLE为止.....）

代码

#include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<map> #include<climits> using namespace std; struct node{ int ti;long long p;int zf; }a[200005]; struct noo{ int ls,rs;long long add,sum; }tree[4000005]; long long b[200005]; int root[400005]; long long ans; int m,n,tot=0,ll,cur=0; bool cmp(node a,node b){ return a.ti<b.ti; } void updata(int l,int r,int &x,int y,int k,long long pos,int zzf){ cur++;x=cur;tree[cur]=tree[y];tree[cur].sum+=zzf;tree[cur].add+=(long long)zzf*pos; if(l==r)return; int mid=(l+r)>>1; if(k<=mid)updata(l,mid,tree[cur].ls,tree[y].ls,k,pos,zzf); else updata(mid+1,r,tree[cur].rs,tree[y].rs,k,pos,zzf); } void find(int l,int r,int x,long long k){ if(k>=tree[x].sum){ans+=tree[x].add;return;} if(l==r){ans=ans+(long long)(tree[x].add/tree[x].sum*k);return;}//可能l==r时，tree[x].sum还是大于k int mid=(l+r)>>1,kl=tree[tree[x].ls].sum; if(kl>=k){find(l,mid,tree[x].ls,k);} else { ans+=tree[tree[x].ls].add;//注意！左半边也要加上，前缀和嘛 find(mid+1,r,tree[x].rs,k-kl);//k-kl还是小心不要写错 } } int main() { int i,j,x,y,wz; long long z,aa,bb,cc,k,pre=1; scanf("%d%d",&m,&n); for(i=1;i<=m;i++){ scanf("%d%d%lld",&x,&y,&z); tot++;a[tot].ti=x;a[tot].p=z;a[tot].zf=1; tot++;a[tot].ti=y+1;a[tot].p=z;a[tot].zf=-1;//差分 b[i]=z; } ll=1; for(i=2;i<=m;i++) if(b[ll]!=b[i])b[++ll]=b[i]; sort(b+1,b+1+ll);sort(a+1,a+1+tot,cmp); j=1; for(i=1;i<=n;i++){ root[i]=root[i-1];//注意，以每个时间建立一棵树，构成主席树 while(j<=tot&&a[j].ti==i){ wz=lower_bound(b+1,b+1+ll,a[j].p)-b; updata(1,ll,root[i],root[i],wz,a[j].p,a[j].zf); j++; } } for(i=1;i<=n;i++){ scanf("%d%lld%lld%lld",&x,&aa,&bb,&cc); k=1+(long long)(aa*pre+bb)