P3168 题解

· · 题解

这题不一定要差分啊。

读完题不难想到覆盖了 x 处的任务应当满足：在 x 之前（含 x）开始，在 x 之后（含 x）结束。

直接取这两部分的交集是不好做的，考虑逆向：这一部分实际上就是所有任务减去在 x 之前结束的，再减去在 x 之后开始的。

“在 x 之前结束的”和“在 x 之后开始的”排序之后用两棵可持久化线段树维护即可，在 n 之前开始的或在 1 之后结束的都是我们需要的“所有任务”。

代码：（这里写的并非传统的可持久化线段树，细节见代码。）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<random>
#include<unordered_map>
using namespace std;

namespace code{
    using ll=long long;
    using ull=unsigned long long;
    using uint=unsigned int;
#define F(i,x,y) for(int i=(x),__tt2__=(y);i<=__tt2__;i++)
#define R(i,x,y) for(int i=(x),__tt2__=(y);i>=__tt2__;i--)
#define _F(i,x,y) for(int i=(x),__tt2__=(y);i<__tt2__;i++)
#define _R(i,x,y) for(int i=(x),__tt2__=(y);i>__tt2__;i--)
#define debug(x) cout<<#x<<'='<<(x)<<endl
    constexpr int N=100005,M=10000005;
    int c[N];
    struct node{
        ll tot;
        int sum,cnt,ls,rs;
        constexpr node(const ll& t=0,const int& s=0,const int& c=0,const int& l=0,const int& r=0):tot(t),sum(s),cnt(c),ls(l),rs(r){}
    }tree[N*32];
    int root1[N],root2[N],top=1;
#define newnode(x) (tree[++top]=tree[x],top)
    void add(const int& ind,const int& x,const int& nl=1,const int& nr=N){
        tree[ind].sum++;
        tree[ind].tot+=c[x];
        const int mid=(nl+nr)>>1;
        if(x==mid)tree[ind].cnt++;
        else if(x<mid){
            tree[ind].ls=newnode(tree[ind].ls);
            add(tree[ind].ls,x,nl,mid-1);
        }
        else {
            tree[ind].rs=newnode(tree[ind].rs);
            add(tree[ind].rs,x,mid+1,nr);
        }
    }
    ll query(const int& k,const int& x1,const int& x2,const int& x3,const int& nl=1,const int& nr=N){
        if(k==0)return 0;
        const int mid=(nl+nr)>>1,lsum=tree[tree[x1].ls].sum-tree[tree[x2].ls].sum-tree[tree[x3].ls].sum;
        const ll ltot=tree[tree[x1].ls].tot-tree[tree[x2].ls].tot-tree[tree[x3].ls].tot;
        if(lsum>=k)return query(k,tree[x1].ls,tree[x2].ls,tree[x3].ls,nl,mid-1);
        else if(lsum+tree[x1].cnt-tree[x2].cnt-tree[x3].cnt>=k){
            return ltot+(k-lsum)*c[mid];
        }
        else return ltot+((ll)(c[mid]))*(tree[x1].cnt-tree[x2].cnt-tree[x3].cnt)+query(k-lsum-tree[x1].cnt+tree[x2].cnt+tree[x3].cnt,tree[x1].rs,tree[x2].rs,tree[x3].rs,mid+1,nr);
    }
    struct task{
        int l,r,p;
        constexpr task(const int& x=0,const int& y=0,const int& z=0):l(x),r(y),p(z){}
    }a[N];
    char tmp[100000],*p=0,*top1=0;
#define getchar() ((p==top1)&&(top1=(p=tmp)+fread(tmp,1,100000,stdin)),*p++)
    void read(int& x){
        char c;
        while((c=getchar())<'0');
        x=c^'0';
        while((c=getchar())>='0')x=x*10+(c^'0');
    }
    int main(){
        cin.tie(0)->sync_with_stdio(0);
        int m,n;
        read(m);
        read(n);
        F(i,1,m){
            read(a[i].l);
            read(a[i].r);
            read(a[i].p);
            c[i]=a[i].p;
        }
        sort(c+1,c+1+m);
        F(i,1,m)a[i].p=lower_bound(c+1,c+1+m,a[i].p)-c;
        sort(a+1,a+1+m,[](const task& x,const task& y)->bool{return x.r<y.r;});
        for(int i=1,j=1;i<=n;i++){
            root1[i]=newnode(root1[i-1]);
            while(j<=m&&a[j].r<=i)add(root1[i],a[j++].p);
        }
        sort(a+1,a+1+m,[](const task& x,const task& y)->bool{return x.l<y.l;});
        for(int i=n,j=m;i>=1;i--){
            root2[i]=newnode(root2[i+1]);
            while(j>=1&&a[j].l>=i)add(root2[i],a[j--].p);
        }
        ll last=1;
        F(i,1,n){
            int x,a,b,c;
            read(x);
            read(a);
            read(b);
            read(c);
            int k=(((ll)(a))*last+b)%c+1;
            if(k>tree[root1[n]].sum-tree[root1[x-1]].sum-tree[root2[x+1]].sum)
                k=tree[root1[n]].sum-tree[root1[x-1]].sum-tree[root2[x+1]].sum;
            printf("%lld\n",last=query(k,root1[n],root1[x-1],root2[x+1]));
        }
        return 0;
    }
}
signed main(){return code::main();}