帕秋莉的魔导书
龙之吻—水货
2018-10-03 12:50:14
# 题外话
想到大家被$T5$折磨了那么久，就应该用一道水题结束这场比赛~~其实还是因为我太菜不会出难题~~。
# Solution
考虑暴力
暴力的话是要求出$[l,r]$这个区间每种情况的知识程度和的总和，然后再除以区间长度。
似乎可以直接维护一棵资瓷区间修改，区间查询的权值线段树，不过当时我没想到，就用了下面这种做法。
思考查询$[l,r]$这个区间,等级小于等于$l$的所有书都是可以看的所以直接加入答案，等级大于$r$的书是不可能看到的，就直接不管了，然后我们就会发现，能看等级为$l + 1$的书的情况有$r - l$种，能看等级为$l + 2$的书的情况有$r - l - 1$种......
之后，实际上就是要求在较短的时间内求出$\sum_{i=l}^ra[i] \times (r - i)$再和前面的加起来就好了。
我的方法是维护两棵权值动态开点线段树，第一棵维护原序列，第二棵维护$a[i] \times (MAX\_INT - i)$。之后加加减减就能得出总和，再除一下就能得到答案了。
```cpp
#include<cstdio>
typedef long long ll;
typedef double ld;
class Node{
private :
public :
Node *leftchild, *rightchild;
int left, right;
ll sum;
Node(int left, int right) :
left(left),
right(right),
leftchild(NULL),
rightchild(NULL),
sum(0) {}
};
class SegmentTree{
private :
Node *root;
void Update(Node *now) {
now->sum = 0;
if (now->leftchild) {
now->sum += now->leftchild->sum;
}
if (now->rightchild) {
now->sum += now->rightchild->sum;
}
}
void AddVal(Node *now, int pos, ll val) {
if (now->left == now->right) {
now->sum += val;
return;
}
int mid = now->left + now->right >> 1;
if (pos <= mid) {
if (!now->leftchild) {
now->leftchild = new Node(now->left, mid);
}
AddVal(now->leftchild, pos, val);
} else {
if (!now->rightchild) {
now->rightchild = new Node(mid + 1, now->right);
}
AddVal(now->rightchild, pos, val);
}
Update(now);
}
ll Query(Node *now, int l, int r) {
if (!now || now->right < l || now->left > r) {
return 0;
}
if (now->left >= l && now->right <= r) {
return now->sum;
}
return Query(now->leftchild, l, r) + Query(now->rightchild, l, r);
}
public :
void Init(int l, int r) {
root = new Node(l, r);
}
void AddVal(int pos, ll val) {
AddVal(root, pos, val);
}
ll Query(int l, int r) {
return Query(root, l, r);
}
};
SegmentTree a, b;
int n, m;
int main() {
freopen("in10.in", "r", stdin);
freopen("out10.out", "w", stdout);
ll k = (1ll << 31) - 1;
scanf("%d %d", &n, &m);
a.Init(1, k);
b.Init(1, k);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
a.AddVal(x, (k - x + 1) * y);
b.AddVal(x, y);
}
for (int i = 1; i <= m; i++) {
int op, x, y;
scanf("%d %d %d", &op, &x, &y);
if (op == 1) {
int res = b.Query(1, x);
if (x == y) {
printf("%.4lf\n", res);
continue;
}
ll sum = a.Query(x + 1, y) - b.Query(x + 1, y) * (k - y);
ld ans = (ld)res;
ans += (ld)sum / (ld)(y - x + 1);
printf("%.4lf\n", ans);
} else {
a.AddVal(x, (k - x + 1) * y);
b.AddVal(x, y);
}
}
return 0;
}
```