题解 P3168 【[CQOI2015]任务查询系统】

· · 题解

[CQOI2015]任务查询系统

一开始受到HNOI2015摘果子的启发写了一发树套树，然后就T了

这题要求求覆盖一个点的前k小区间和。强制在线。

但主席树的解法其实差不多，因为主席树有前缀和的思想，我们把每一个区间拆开，在l处加区间的权值，在r+1处减区间的权值，然后用主席树维护一个前缀和。
我们就可以单点查询了。在主席树上二分就行了。 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
int n,m,num,tot;
int a[N],b[N],root[N<<6];
long long ans=1;
struct tree {
    long long sum; 
    int cnt,l,r;
}t[N<<6];
vector<int>be[N],ed[N];
void update(int &u,int l,int r,int pre,int pos,int v){
    u=++tot; t[u]=t[pre];
    t[u].cnt+=v, t[u].sum+=1ll*v*b[pos];
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) update(t[u].l,l,mid,t[pre].l,pos,v);
    else update(t[u].r,mid+1,r,t[pre].r,pos,v);
}
long long query(int u,int l,int r,int k){
    int num=t[t[u].l].cnt;
    if(l==r) return t[u].sum/(1ll*t[u].cnt)*1ll*k;
    int mid=(l+r)>>1;
    if(k<=num) return query(t[u].l,l,mid,k);
    else return query(t[u].r,mid+1,r,k-num)+t[t[u].l].sum;
}
int main(){
    m=read(),n=read();
    for(int i=1;i<=m;i++) {
        int x=read(),y=read();
        a[i]=read(),b[i]=a[i];
        be[x].push_back(i), ed[y+1].push_back(i);
    }
    sort(b+1,b+1+m); int num=unique(b+1,b+1+m)-b-1;
    for(int i=1;i<=n;i++) {
        root[i]=root[i-1];
        for(int j=0;j<be[i].size();j++) {
            int p=lower_bound(b+1,b+1+num,a[be[i][j]])-b;
            update(root[i],1,num,root[i],p,1);
        }
        for(int j=0;j<ed[i].size();j++) {
            int p=lower_bound(b+1,b+1+num,a[ed[i][j]])-b;
            update(root[i],1,num,root[i],p,-1);
        }
    }
    for(int i=1;i<=n;i++) {
        int x=read(),a=read(),b=read(),c=read(),k=(1ll*a*ans+b)%c+1;
        if(k>t[root[x]].cnt) ans=t[root[x]].sum;
        else ans=query(root[x],1,num,k);
        printf("%lld\n",ans);
    }
    return 0;
}