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

· · 题解

Dew~

化简模型，给出m个三元组(s,e,p)

询问(x,k)为满足s \le x \le e的三元组的前k大p值之和，强制在线

一看是一个偏序类题目，我们可以多维数据结构暴力嵌套，这个题最多允许log^2,又有第k大询问，自然的想到主席树降维

使用树状树状套主席树求解

其中树状树状的区间代表从大到小排序的E_i

树状树状的每个区间放对应的一群线段树，我们先对区间按S_i从小到大排序，然后按这个顺序建主席树就行了

主席树的节点存离散（不离散似乎也过了）的p_i值，注意维护一下区间和

查询的时候，在每个树状数组对应的主席树上一起二分即可，注意重复的元素

Code

#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node
{
    int s,t,p;
    bool friend operator <(node n1,node n2){return n1.t>n2.t;}
}rask[N];
struct RT
{
    int s,now;
    RT(){}
    RT(int s,int now){this->s=s,this->now=now;}
    bool friend operator <(RT n1,RT n2){return n1.s<n2.s;}
}rt;
vector <RT> root[N];
int cnt[N*244],ch[N*244][2],tot,n,m,mxx;ll sum[N*244];
int max(int x,int y){return x>y?x:y;}
#define ls ch[now][0]
#define rs ch[now][1]
#define ols ch[las][0]
#define ors ch[las][1]
void update(int now)
{
    sum[now]=sum[ls]+sum[rs];
    cnt[now]=cnt[ls]+cnt[rs];
}
int build(int las,int l,int r,int pos)
{
    int now=++tot;
    if(l==r)
    {
        cnt[now]=cnt[las]+1;
        sum[now]=1ll*cnt[now]*l;
        return now;
    }
    int mid=l+r>>1;
    if(pos<=mid)
    {
        ls=build(ols,l,mid,pos);
        rs=ors;
    }
    else
    {
        ls=ols;
        rs=build(ors,mid+1,r,pos);
    }
    update(now);
    return now;
}
void init()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&rask[i].s,&rask[i].t,&rask[i].p),mxx=max(mxx,rask[i].p);
    sort(rask+1,rask+1+m);
    for(int i=1;i<=m;i++)
    {
        for(int j=i-(i&-i)+1;j<=i;j++)
        {
            rt=RT(rask[j].s,j);
            root[i].push_back(rt);
        }
        sort(root[i].begin(),root[i].end());
        for(int las=0,j=0;j<root[i].size();j++)
            las=root[i][j].now=build(las,1,mxx,rask[root[i][j].now].p);
    }
}
ll query(int x,int pos,int k)//时间，前pos可查，第k值
{
    int now[50],p=0;
    for(int i=pos;i;i-=i&-i)
    {
        RT t=RT(x,0);
        int j=upper_bound(root[i].begin(),root[i].end(),t)-root[i].begin()-1;
        now[++p]=root[i][j].now;
    }
    int l=1,r=mxx;ll ans=0;
    while(l<r)
    {
        int mid=l+r>>1,s=0;
        for(int i=1;i<=p;i++) s+=cnt[ch[now[i]][0]];
        if(s>=k)
        {
            for(int i=1;i<=p;i++) now[i]=ch[now[i]][0];
            r=mid;
        }
        else
        {
            for(int i=1;i<=p;i++) ans+=sum[ch[now[i]][0]],now[i]=ch[now[i]][1];
            l=mid+1,k-=s;
        }
    }
    int cnt0=0;
    for(int i=1;i<=p;i++) cnt0+=cnt[now[i]];
    ans+=1ll*l*min(cnt0,k);
    return ans;
}
void work()
{
    ll pre=1;
    for(int pos,x,a,b,c,k,i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&x,&a,&b,&c);
        k=(a*(int)(pre%(1ll*c))+b)%c+1;
        node t={0,x,0};
        pos=upper_bound(rask+1,rask+1+m,t)-rask-1;
        printf("%lld\n",pre=query(x,pos,k));
    }
}
int main()
{
    init(),work();
    return 0;
}

然而，我们注意到这个问题有这样一个暴力

对操作，我们可以把每个对应位置上都加上这个优先级，并用权值线段树维护

然后查询时，直接进入对应位置的权值线段树查询即可

而事实上，我们发现这是对每个位置有一个区间加，我们可以采用差分数组的思想

把三元组(s,e,p)的s位置的p值+1，把e+1位置p值-1（这里p值在对于位置的权值线段树上）

然后我们查询的时候，就求这些权值线段树的前缀和就可以了

这不就是主席树干的事情吗

于是乎问题就可以直接用主席树做了

Code:

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
struct node{int s,e,p;}rask[N];
int a[N];
int cnt[N*100],ch[N*100][2],root[N],tot,n,m,num;ll sum[N*100];
#define ls ch[now][0]
#define rs ch[now][1]
void updata(int now)
{
    sum[now]=sum[ls]+sum[rs];
    cnt[now]=cnt[ls]+cnt[rs];
}
void build(int &now,int l,int r,int pos,int del)
{
    if(!now) now=++tot;
    if(l==r)
    {
        cnt[now]+=del;
        sum[now]=1ll*cnt[now]*a[l];
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)
        build(ls,l,mid,pos,del);
    else
        build(rs,mid+1,r,pos,del);
    updata(now);
}
int rebuild(int x,int y)
{
    if(!x||!y) return x+y;
    int now=++tot;
    sum[now]=sum[x]+sum[y];
    cnt[now]=cnt[x]+cnt[y];
    ls=rebuild(ch[x][0],ch[y][0]);
    rs=rebuild(ch[x][1],ch[y][1]);
    return now;
}
void init()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&rask[i].s,&rask[i].e,&rask[i].p);
        a[i]=rask[i].p;
    }
    sort(a+1,a+1+m);
    ++n;
    num=unique(a+1,a+1+m)-a-1;
    for(int i=1;i<=m;i++)
    {
        rask[i].p=lower_bound(a+1,a+1+num,rask[i].p)-a;
        build(root[rask[i].s],1,num,rask[i].p,1);
        build(root[rask[i].e+1],1,num,rask[i].p,-1);
    }
    for(int i=1;i<=n;i++)
        root[i]=rebuild(root[i-1],root[i]);
}
ll query(int now,int l,int r,int k)
{
    if(l==r)
        return 1ll*a[l]*min(k,cnt[now]);
    int mid=l+r>>1;
    if(cnt[ls]>=k) return query(ls,l,mid,k);
    else return sum[ls]+query(rs,mid+1,r,k-cnt[ls]);
}
void work()
{
    ll pre=1;
    for(int x,a,b,c,k,i=1;i<n;i++)
    {
        scanf("%d%d%d%d",&x,&a,&b,&c);
        k=(a*(int)(pre%(1ll*c))+b)%c+1;
        printf("%lld\n",pre=query(root[x],1,num,k));
    }
}
int main()
{
    init(),work();
    return 0;
}