bzoj3932 [CQOI2015]任务查询系统

bzoj3932

题意:

给定一个序列(为空),有一些区间覆盖这个序列,并且区间带有一个权值;给定每个区间的起始以及权值,要求支持询问覆盖序列里一个位置的区间中,权值前$k$小的区间权值之和。($n\leq 100000$)强制在线。


题解:

如果离线的话,可以直接用树状数组套主席树来做,把询问按照时间排序,按照时间的顺序perform一下插入和删除,然后顺便更新这个时间上的询问的答案。

但是这题在线啊,怎么做呢,考虑更改一下值域和优先级,把时间当作值域,任务的权值作优先级建主席树。区间有始有终,对于答案的贡献只有区间的个数以及区间的权值,于是可以差分处理任务在每个时间点上的贡献。由于涉及求和,每个节点除了维护有多少个元素以外,还维护权值和。建树时,由于是差分的序列,所以按照前一个时间的$root$为基来建立这个时间的树。

具体实现的话有一些细节,当询问到叶子结点时,需要返回这个结点的权值和,但是由于权值是可以重复的所以这个结点代表的是权值为$l$的所有区间权值之和,而我们只要其中的$k$个,所以返回$\frac{sum}{cnt}\times k$即可。但是由于$k$可能大于要询问的时间点里任务的个数,所以有可能出现$k$没有减到$0$到了一个值域里存在、但是时间点上没有这个权值的结点,此时$cnt$为$0$,显然这个结点对答案也没有贡献,特判即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int)1e5+5;
int n,m,root[maxn<<1];
ll st[maxn<<1];
namespace ftlsgt {
int tot=0,cntv[maxn*50],lson[maxn*50],rson[maxn*50];
ll sumv[maxn*50];
int Newnode(int hav,ll val,int ls,int rs)
{
cntv[++tot]=hav;sumv[tot]=val;
lson[tot]=ls,rson[tot]=rs;
return tot;
}
void Ins(int &rt,int prert,int pos,int l,int r,int hav,ll val)
{
rt=Newnode(cntv[prert]+hav,sumv[prert]+val,lson[prert],rson[prert]);
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) Ins(lson[rt],lson[prert],pos,l,mid,hav,val);
else Ins(rson[rt],rson[prert],pos,mid+1,r,hav,val);
}
ll Qry(int o,int l,int r,int k)
{
if(l==r) return cntv[o]==0?0:sumv[o]/cntv[o]*1ll*k;
int mid=(l+r)>>1,p=cntv[lson[o]];
if(k<=p) return Qry(lson[o],l,mid,k);
else return sumv[lson[o]]+Qry(rson[o],mid+1,r,k-p);
}
}
using namespace ftlsgt;
struct task {
int l,r;
ll c;
task(int l=0,int r=0,ll c=0): l(l),r(r),c(c) {}
};
task q[maxn];
vector<ll > Hav[maxn];
inline int myabs(int x) {return x<0?-x:x;}
inline int pan(int x) {return x<0?-1:1;}
int main()
{
scanf("%d%d",&n,&m);
int sz=0,up=0;
for(int i=1;i<=n;i++) {
scanf("%d%d%lld",&q[i].l,&q[i].r,&q[i].c);
st[++up]=q[i].c;
}
sort(st+1,st+1+up);
sz=unique(st+1,st+1+up)-(st+1);
for(int i=1;i<=n;i++) q[i].c=lower_bound(st+1,st+1+sz,q[i].c)-st;
for(int i=1;i<=n;i++) {
Hav[q[i].l].push_back(q[i].c);
if(q[i].r+1<=n) Hav[q[i].r+1].push_back(-q[i].c);
}
for(int i=1;i<=m;i++) {
root[i]=root[i-1];
for(int j=0;j<(int)Hav[i].size();j++) {
Ins(root[i],root[i],myabs(Hav[i][j]),1,sz,pan(Hav[i][j]),pan(Hav[i][j])*st[myabs(Hav[i][j])]);
}
}
ll pre=1;
int K,tim,a,b,c;
for(int i=1;i<=m;i++) {
scanf("%d%d%d%d",&tim,&a,&b,&c);
K=(pre*a+1ll*b)%c+1;
printf("%lld\n",(pre=Qry(root[tim],1,sz,K)));
}
return 0;
}