解題區/解題區 - Zerojudge

b492. 史蒂芙的外交序列

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

背景

史蒂芙為了人類國家決定出遠門外交，在一條神秘谷徑中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙依照自己的能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪，並且這次遠門的滿意程度是所有走訪國家的權重相乘。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對某個區間內的城市策劃行程，現在請你算出所有計畫的預期滿意程度以及走訪個數，由於滿意程度會很大，輸出 $\mod 1000000007$ 的結果。

題目描述

給定 $N$ 個整數序列 $A[]$ 以及 $Q$ 個詢問，每一個詢問 $[L, R]$ 以及 $K$，請計算 $\sum_{L \le i \le R } [A_i \le K]$ 以及 $\prod_{L \le i \le R, \; A_i \le K } A_i$

Sample Input

1
2
3
4
5
6
7 4
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
4 6 6

Sample Output

1
2
3
4
2 6
0 0
3 6
2 18

Solution

詢問一個區間內，元素小於等於 $K$ 的元素個數，並且把這些數字相乘輸出。

這裡使用函數式線段樹來完成操作，時間複雜度 $O(Q \log N)$ 空間複雜度 $O(N \log N)$。但若模數不是大質數，相乘結果無法利用區間加減法的性質計算，要使用別的資料結構完成，函數式線段樹將沒辦法支持這個計算。

特別小心實作反元素計算時，要分開計算比較好，儘管歐基里德輾轉相除法複雜度 $O(\log N)$ 且常數非常小，詢問時避免兩個版本好同時計算，寫法如下

1
2
3
4
5
6
7
void find(Node *v1, Node *v2, int x, int l, int r) {
    if (1 <= l && r <= x) {
    	QV = QV * v1->prod %MOD * inverse(v2->prod, MOD) % MOD;
    	QD += v1->sum - v2->sum;
    	return ;
    }
...

單筆詢問時間複雜度會掉回 $O(\log^2 N)$。

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
117
118
119
120
121
122
123
#include <bits/stdc++.h> 
using namespace std;
const int MOD = 1000000007;
void exgcd(int x, int y, int &g, int &a, int &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int inverse(int x, int p) {
    int g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)	r = -r;
    return (r%p + p)%p;
}
class SegementTree {
public:
    static const int MAXN = 1000000;
    struct Node {
        Node *lson, *rson;
        int sum, prod;
        Node() {
        	lson = rson = NULL;
        	prod = 1, sum = 0;
        }
    } nodes[MAXN];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        Node *u = &nodes[nodesize++];
        *u = Node();
        return u;
    }
    Node* cloneNode(Node *p) {
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, long long val, int l, int r) {
        Node *u = cloneNode(p);
        u->prod = (u->prod * val)%MOD, u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, val, l, mid);
        	else
         		u->rson = change(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, long long val) {
        return change(p, x, val, L, R);
    }
    
    int QV, QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QV = (long long)QV * v1->prod % MOD;
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    pair<int, int> find(Node *v1, int x) {
        QV = 1, QD = 0;
        find(v1, x, L, R);
        return {QD, QV};
    }
} tree;
const int MAXN = 65536;
SegementTree::Node *root[MAXN];
int main() {
    int N, Q, A[MAXN];
    int L, R, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        root[0] = tree.init(1, N);
        for (int i = 1; i <= N; i++)
            root[i] = tree.change(root[i-1], A[i], A[i]);
        
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &L, &R, &K);
            int a, b;
            pair<int, int> r;
            r = tree.find(root[R], K);
            a = r.first, b = r.second;
            r = tree.find(root[L-1], K);
            a -= r.first, b = (long long) b * inverse(r.second, MOD)%MOD;
            if (a == 0) {
                printf("0 0\n");
            } else {
                printf("%d %d\n", a, b);
            }
        }
    }
    return 0;
}