题解 [CQOI2015]任务查询系统

题面

解析

首先,我们考虑下暴力的做法:

每次将一个任务的重要度加入到它的区间中,

询问的时候就直接加前\(k\)大.

然而,这样肯会炸的(都说了是暴力了).

其实,我们可以转化一下区间修改(因为区间修改似乎并不好做哈qwq)

利用前缀和与差分的思想(不会的请自行百度下),

将要修改的区间转化为单点修改,

于是,通过前缀和,我们就能知道一个点插入了哪些任务了.

然而怎么查询呢?

我们先考虑下对于一个点\(x\)的情况:

首先,我们对\(x\)建一棵区间为\([1,x]\)的权值线段树,

那么在插入点时,重复的就会被抵消掉(这一点看代码吧),

因此,在权值线段树上插入的都是包含了\(x\)的任务.

另外,因为\(x\)与\(x+1\)只修改了一个点,

我们可以直接用可持久化线段树.

最后,我们只需要记一下权值区间的和,

再按照主席树的板子走就行啦!

上代码吧:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

using namespace std;

inline int read(){

    int sum=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

    while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}

    return sum*f;

}

struct tree{int l,r,sum,cnt;}t[4000001];

struct node{int x,y;}a[1000001];//x是位置,y是值

int n,m,tot,c[1000001],sz;

int rt[1000001],pp;

ll pre=1;

bool cmp(node a,node b){return a.x<b.x;}

inline void pushup(int p){

    t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;

    t[p].sum=t[t[p].l].sum+t[t[p].r].sum;

}

int update(int p,int l,int r,int k){

    int x=++sz;t[x]=t[p];

    if(l==r){

        t[x].sum+=k*c[l];t[x].cnt+=k;

        return x;

    }

    int mid=(l+r)>>1;

    if(pp<=mid) t[x].l=update(t[p].l,l,mid,k);

    else t[x].r=update(t[p].r,mid+1,r,k);

    pushup(x);return x;

}

int ask(int p,int l,int r,int k){

    if(l==r) return t[p].sum/t[p].cnt*k;

    int mid=(l+r)>>1;

    if(t[t[p].l].cnt>=k) return ask(t[p].l,l,mid,k);

    return t[t[p].l].sum+ask(t[p].r,mid+1,r,k-t[t[p].l].cnt);

}

int main(){

    n=read();m=read();

    for(int i=1;i<=n;i++){

        int x=read(),y=read(),z=read();

        a[++tot].x=x;a[tot].y=z;

        a[++tot].x=y+1;a[tot].y=-z;

        c[i]=z;

    }

    sort(a+1,a+tot+1,cmp);//按照修改的点排下序,不然会出锅qwq

    sort(c+1,c+n+1);int q=unique(c+1,c+n+1)-c-1;//离散化一下

    int ff=1;

    for(int i=1;i<=tot;i++){

        while(ff<a[i].x) rt[ff+1]=rt[ff],ff++;//有些点可能没有修改,就直接沿用上一个点

        pp=lower_bound(c+1,c+q+1,abs(a[i].y))-c;

        rt[ff]=update(rt[ff],1,q,(a[i].y>0? 1:-1));//插入还是删除

    }

    for(int i=1;i<=m;i++){

        int x=read(),ai=read(),bi=read(),ci=read();

        ll ki=(ll)(((ll)(ai*pre+bi))%ci+1);

        if(t[rt[x]].cnt<=ki) printf("%lld\n",(pre=t[rt[x]].sum));//如果任务数小于k就直接输出

        else printf("%lld\n",(pre=ask(rt[x],1,q,ki)));

    }

    return 0;

}

巴特西

题解 [CQOI2015]任务查询系统

解析

最新文章

热门文章