求前 $K$ 小的数的和,考虑主席树
但是如果每个时间都暴力插入显然会GG
发现每个任务都是区间,查询是单点查询
所以考虑维护差分数组
直接用主席树维护差分数组,因为同一时间差分可能有多次修改,所以要把当前修改全部搞完才算当前时间的线段树
询问就在相应时间点的线段树上走
具体看代码理解吧
#include#include #include #include #include #include using namespace std;typedef long long ll;inline ll read(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=2e5+7,M=2e7+7;int n,m;int rt[N],L[M],R[M],sz[M],cnt;ll S[M];//注意long long!int val,K;ll res;//long long !void ins(int &o,int l,int r,int pre)//插入{ o=++cnt; S[o]=S[pre]+val; sz[o]=sz[pre]+(val>0 ? 1 : -1); //注意我们维护的是差分数组,要根据val的正负来判断加还是删 if(l==r) return; int mid=l+r>>1; if(abs(val)<=mid) ins(L[o],l,mid,L[pre]),R[o]=R[pre];//注意val要取绝对值 else ins(R[o],mid+1,r,R[pre]),L[o]=L[pre];}void query(int o,int l,int r){ if(l==r) { res+=l*K; return; } int mid=l+r>>1; if(sz[L[o]]