(题目链接)

题意

　　给出$m$个区间，每个区间有一个权值，$n$组询问，每次询问在位置$x$权值前$k$大的区间的权值和。

Solution

　　扫描线搞一下然后主席树维护即可。

细节

　　查询的时候注意叶子节的情况

代码

// bzoj3932#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define lim 10000000#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=200010;int n,m,sz,rt[maxn];struct data { int pos,w,op; friend bool operator < (data a,data b) {return a.pos
           
            >1; if (val<=mid) insert(tr[u][0],tr[v][0],l,mid,val,op),tr[u][1]=tr[v][1]; else insert(tr[u][1],tr[v][1],mid+1,r,val,op),tr[u][0]=tr[v][0]; tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s; tr[u].val=tr[tr[u][0]].val+tr[tr[u][1]].val; } LL query(int k,int l,int r,int x) { if (!k) return 0; if (l==r) return (LL)l*x; int mid=(l+r)>>1,c=tr[tr[k][0]].s; if (x==c) return tr[tr[k][0]].val; else if (x