CF837G Functions On The Segments

CF837G Functions On The Segments

Functions On The Segments - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意

你有 $n$ 个函数，第 $i$ 个函数 $f_i$ 为：

$$f_i(x)=\{\begin{array}{ll}{y}_1,& x\le x_1\\ ax+b,& x_1\le x\le x_2\\ y_2,& x>x_2\end{array}$$

$m$ 次询问，每次询问给出 $l,r,x$，求 $\sum _{i=l}^r{f}_i(x)$。强制在线。

思路

主席树

转化一下式子就是：
$$f_i(x)=\{\begin{array}{ll}0x+y_1,& x\le x_1\\ ax+b,& x_1\le x\le x_2\\ 0x+y_2,& x>x_2\end{array}$$
所以答案就是：
$$\sum _{i=l}^r{a}_{i}x+\sum _{i=l}^r{b}_i$$
把 $x_1,x_1+1,x_2,x_2+1$ 离散化一下，然后开一棵主席树维护 $a$ 和 $b$ 的差分数组。

用差分是因为强制在线

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 75005;
const LL maxx = INT_MAX;
int x[N] , xx[N] , a[N] , b[N] , n , cnt , rt[N * 2] , re[N * 8];
LL y[N] , yy[N];
struct Tr {
    int lp , rp , flg1 , flg2;
    LL v1 , v2;
} tr[N * 200];
void copy_tr (int p , int lst) {
    tr[p].v1 = tr[lst].v1;
    tr[p].v2 = tr[lst].v2;
    tr[p].lp = tr[lst].lp;
    tr[p].rp = tr[lst].rp;
}
void glp (int p) {
    if (tr[p].flg1 == 0) {
        int lst = tr[p].lp;
        tr[p].lp = ++cnt;
        copy_tr (cnt , lst);
    }
    tr[p].flg1 = 1;
}
void grp (int p) {
    if (tr[p].flg2 == 0) {
        int lst = tr[p].rp;
        tr[p].rp = ++cnt;
        copy_tr (cnt , lst);
    }
    tr[p].flg2 = 1;
}
void change (int p , int l , int r , int X , LL val , int flg) {
    if (flg == 1) tr[p].v1 += val;
    else tr[p].v2 += val;
    if (l == r)
        return;
    else {
        int mid = l + r >> 1;
        if (X <= mid) {
            glp(p);
            change (tr[p].lp , l , mid , X , val , flg);
        }
        else {
            grp (p);
            change (tr[p].rp , mid + 1 , r , X , val , flg);
        }
    }
}
struct node {
    LL a , b;
};
node query (int p , int l , int r , int L , int R) {
    if (L <= l && R >= r) return (node){tr[p].v1 , tr[p].v2};
    else {
        int mid = l + r >> 1;
        node ans1 = (node){0 , 0} , ans2 = (node){0 , 0};
        if (L <= mid && tr[p].lp)
            ans1 = query (tr[p].lp , l , mid , L , R);
        if (mid < R && tr[p].rp)
            ans2 = query (tr[p].rp , mid + 1 , r , L , R);
        return (node){ans1.a + ans2.a , ans1.b + ans2.b};
    }
}
int main () {
    scanf ("%d" , &n);
    int n1 = 0;
    re[++n1] = 0;
    re[++n1] = maxx;
    fu (i , 1 , n) {
        scanf ("%d%d%lld%d%d%lld" , &x[i] , &xx[i] , &y[i] , &a[i] , &b[i] , &yy[i]);
        re[++n1] = x[i];
        re[++n1] = xx[i];
        re[++n1] = xx[i] + 1;
        re[++n1] = x[i] + 1;
    }
    int T;
    sort (re + 1 , re + n1 + 1);
    int m = unique (re + 1 , re + n1 + 1) - re - 1;
    int aa , bb;
    fu (i , 1 , n) {
        rt[i] = ++cnt;
        copy_tr (rt[i] , rt[i - 1]); 
        change (rt[i] , 1 , m , 1 , y[i] , 2);
        aa = upper_bound(re + 1 , re + m + 1 , x[i]) - re;
        change (rt[i] , 1 , m , aa , -y[i] , 2);

        aa = upper_bound(re + 1 , re + m + 1 , x[i]) - re , bb = upper_bound(re + 1 , re + m + 1 , xx[i]) - re;
        change (rt[i] , 1 , m , aa , a[i] , 1);
        change (rt[i] , 1 , m , aa , b[i] , 2);
        
        change (rt[i] , 1 , m , bb , -a[i] , 1);
        change (rt[i] , 1 , m , bb , -b[i] , 2);

        aa = upper_bound(re + 1 , re + m + 1 , xx[i]) - re;
        change (rt[i] , 1 , m , aa , yy[i] , 2);
    }
    node ans1 , ans2;
    LL ans3 , ans4 , lst = 0;
    int u , ll , rr;
    scanf ("%d" , &T);
    while (T --) {  
        scanf ("%d%d%d" , &ll , &rr , &u);        
        u = (u + lst) % 1000000000;
        aa = upper_bound(re + 1 , re + m + 1 , u) - re - 1;
        ans1 = query (rt[ll - 1] , 1 , m , 1 , aa);
        ans2 = query (rt[rr] , 1 , m , 1 , aa);
        ans3 = ans1.a * u + ans1.b;
        ans4 = ans2.a * u + ans2.b;
        lst = ans4 - ans3;
        printf ("%lld\n" , lst);
    }
    return 0;
}
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116