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

· · 题解

Description

有 m 个区间，每个区间有一个权值，n 次询问，求覆盖一个点的前 k 小区间和，强制在线。

n,m\leq 10^5

Solution

给出一个不需要差分的主席树 + 二分的想法，应该更好想一点？

首先它要求前 k 小区间和，那我们应该可以很自然想出先把区间按照权值从小到大排序。然后我们就可以把这些区间想成一个个版本，加入到主席树中。主席树维护两个东西：一个是区间被覆盖的次数，另一个是被覆盖的权值，由于是区间操作，我们可以标记永久化；并且由于是单点查询，所以我们其实只关心叶子节点被覆盖的次数或者被覆盖的权值，因此我们只需要在修改时对于被完全包含的区间打上标记即可。

查询的时候，我们先二分覆盖次数，找到 x 被覆盖 \leq k 次的最大版本，那么这个版本 x 被覆盖的权值就是我们的答案，时间复杂度就是 O(n\log^2n)，也不需要离散化，注意被覆盖权值开 long long 即可。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e5 + 5;
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}

int m,n,sec,ai,bi,ci,ki;
ll ans;
int root[N],idx;
struct Mission{
    int s,e,p;
    bool operator < (Mission &t) { return p < t.p; }
}a[N];
struct Tree{
    int l,r,siz;//覆盖次数
    ll sum;//覆盖权值
}tree[N*100];

il int read()
{
    int f=0,s=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
    for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
    return f ? -s : s;
}

#define lc(x) tree[x].l
#define rc(x) tree[x].r

il void Modify(int x,int &y,int l,int r,int nl,int nr,int k)
{
    y = ++idx;
    tree[y] = tree[x];
    if(nl <= l && r <= nr)
    {
        tree[y].sum += k , tree[y].siz++;//被完全覆盖的打上标记即可
        return ;
    }
    int mid = (l+r) >> 1;
    if(nl <= mid) Modify(lc(x),lc(y),l,mid,nl,nr,k);
    if(nr > mid) Modify(rc(x),rc(y),mid+1,r,nl,nr,k);
}

il int QueryCnt(int p,int l,int r,int pos,int tag)//tag就是一路处理标记
{
    int res = 0;
    if(l == pos && r == pos) return tree[p].siz + tag;//叶子节点
    int mid = (l+r) >> 1;
    if(pos <= mid) res = QueryCnt(lc(p),l,mid,pos,tag+tree[p].siz);
    if(pos > mid) res = QueryCnt(rc(p),mid+1,r,pos,tag+tree[p].siz);
    return res;
}

il ll QuerySum(int p,int l,int r,int pos,ll tag)
{
    ll res = 0;
    if(l == pos && r == pos) return tree[p].sum + tag;
    int mid = (l+r) >> 1;
    if(pos <= mid) res = QuerySum(lc(p),l,mid,pos,tag+tree[p].sum);
    if(pos > mid) res = QuerySum(rc(p),mid+1,r,pos,tag+tree[p].sum);
    return res;
}

il ll Um_nik(int x,int k)//第x秒被覆盖k次
{
    int l = 1 , r = m , tot = m+1;
    if(k >= m) return QuerySum(root[m],1,n,x,0);
    while(l <= r)//二分被覆盖次数
    {
        int mid = (l+r) >> 1;
        if(QueryCnt(root[mid],1,n,x,0) <= k) tot = mid , l = mid + 1;
        else r = mid - 1;
    }
    return QuerySum(root[tot],1,n,x,0);//返回那个版本的被覆盖权值
}

signed main()
{
    m = read() , n = read();
    for(re int i=1;i<=m;i++) a[i].s = read() , a[i].e = read() , a[i].p = read();
    sort(a+1,a+m+1);//按照权值排序
    for(re int i=1;i<=m;i++) Modify(root[i-1],root[i],1,n,a[i].s,a[i].e,a[i].p);//建立版本
    ans = 1;
    for(re int i=1;i<=n;i++)
    {
        sec = read() , ai = read() , bi = read() , ci = read();
        ki = 1ll * ((ans % ci * ai % ci + bi % ci) % ci + 1);
        ans = Um_nik(sec,ki);
        cout << ans << "\n";
    }
    return 0;
}