LibreOJ 2097 「CQOI2015」任务查询系统

发表于 | 分类于 |

考虑把各个任务在时间上差分，问题转化为求前 \(k\) 大的数之和，
那么主席树同时维护一个总和 \(sum\) 即可。

所以建立 \(n\) 棵主席树，第 \(i\) 棵表示前 \(i\) 个时刻的信息。
因此建树的时候可以复用上一个时刻的主席树，直接修改并开新点。
注意离散化，以及空间大小。

此外由于题目中有可能出现主席树上查询的结点子树大小 \(< k\) 的情况，另外处理一下即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <algorithm>
#define ls seg[p].lson
#define rs seg[p].rson
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    while(ch < '0' || ch > '9')
        w |= ch == '-',ch = gc();
    while(ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc();
    w ? x = -x : x;
}

const int N = 1e5;
int m,n,len,rt[N + 10];
long long ind[N + 10];
long long lastans = 1;
struct segnode
{
    long long sum;
    int cnt,lson,rson;
} seg[(N << 7) + 10];
int insert(int x,int k,int last,int tl,int tr)
{
    static int tot = 0;
    int p = ++tot;
    seg[p] = seg[last];
    if(tl == tr)
    {
        seg[p].cnt += k;
        seg[p].sum += k * ind[tl];
        return p;
    }
    int mid = tl + tr >> 1;
    if(x <= mid)
        ls = insert(x,k,ls,tl,mid);
    else
        rs = insert(x,k,rs,mid + 1,tr);
    seg[p].cnt = seg[ls].cnt + seg[rs].cnt;
    seg[p].sum = seg[ls].sum + seg[rs].sum;
    return p;
}
long long query(int k,int p,int tl,int tr)
{
    if(tl == tr)
        return seg[p].sum / seg[p].cnt * k;
    if(seg[p].cnt <= k)
        return seg[p].sum;
    int mid = tl + tr >> 1;
    if(k <= seg[ls].cnt)
        return query(k,ls,tl,mid);
    else
        return seg[ls].sum + query(k - seg[ls].cnt,rs,mid + 1,tr);
}
struct note
{
    int x,op;
    long long k;
    inline bool operator<(const note &a) const
    {
        return x < a.x;
    }
} item[(N << 1) + 10];
int main()
{
    read(m),read(n);
    for(register int i = 1;i <= m;++i)
    {
        int l,r,k;
        read(l),read(r),read(k);
        ind[i] = k;
        item[(i << 1) - 1] = (note){l,1,k};
        item[i << 1] = (note){r + 1,-1,k};
    }
    sort(item + 1,item + (m << 1) + 1);
    sort(ind + 1,ind + m + 1);
    len = unique(ind + 1,ind + m + 1) - ind - 1;
    for(register int i = 1;i <= (m << 1);++i)
        item[i].k = lower_bound(ind + 1,ind + len + 1,item[i].k) - ind;
    for(register int i = 1,j = 1;i <= n;++i)
    {
        rt[i] = rt[i - 1];
        for(;item[j].x == i;++j)
            rt[i] = insert(item[j].k,item[j].op,rt[i],1,len);
    }
    int x,a,b,c,k;
    while(n--)
    {
        read(x),read(a),read(b),read(c);
        k = 1 + (a * lastans + b) % c;
        printf("%lld\n",lastans = query(k,rt[x],1,len));
    }
}