P4915 帕秋莉的魔导书（动态开点线段树）

题目背景

帕秋莉有一个巨大的图书馆，里面有数以万计的书，其中大部分为魔导书。

题目描述

魔导书是一种需要钥匙才能看得懂的书，然而只有和书写者同等或更高熟练度的人才能看得见钥匙。因此，每本魔导书都有它自己的等级 ai，同时它也有自己的知识程度为 wi，现在我们想要知道，一个等级为 bi的生物(...)，可以从这些魔导书中得到多少知识。

然而不幸的是，每个生物并不知道自己确切的等级，只有一个等级的大致范围，你需要计算出这个生物获得知识程度的期望值。

输入格式

第一行两个正整数 n,m 代表起始书的个数，以及操作的个数。

以下 n 行，每行两个正整数 ai 和 wi，代表每本书的等级以及知识程度。

接下来的 m 行，每行 2 或 3 个正整数。

操作 1：格式：1 x y。含义：求等级为 [x,y] 的生物能获得的期望知识程度。

操作 2：格式：2 x y。含义：图书馆又收入了一本等级为 x，知识程度为 y 的魔导书。

输出格式

输出包含若干行实数，即为所有操作 1 的结果，答案保留四位小数。

输入输出样例

输入 #1

5 5

1 1

2 1

3 1

4 1

5 1

1 2 5

1 1 5

1 3 5

2 1 5

1 1 2

输出 #1

3.5000

3.0000

4.0000

6.5000

说明/提示

对于 30% 的数据，保证 1 <=所有输入的数字 ≤10^3。

对于 100% 的数据，保证 1≤n,m≤10^5，对于其他数字，保证在 32 位带符号整数范围内（保证运算中所有的数均在 −2^63∼2^63−1 内）。

分析

首先，题目让我们求的是这个柿子

$\displaystyle\sum_{i=x}^{y} tot[i] $ /（y-x+1）

即 $\displaystyle\sum_{i=x}^{y} tot[i] \over y-x+1$

tot[i]为i这个等级能看到的知识程度的总和。

我们可以以等级为区间，知识程度为权值。

那不就是区间和除以区间长度了吗？

看到区间和，我们就可以想到用线段树来维护。

但等级可能会达到2^32-1，所以我们考虑一下动态开点或者离散化（蒟蒻我不会写）

当新添一本书后，等级大于他的都可以看到，就相当于从这本书的等级到inf的区间，加上这本书的知识程度。

查询操作，就是区间和除以区间长度就OK了。

一定要注意开 long long(不开long long 见祖宗)

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

const int inf = 2147483536;

int n,m,x,y,opt,root,tot;

inline int read()

{

	int s = 0, w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w =  -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s  = s * 10+ch -'0'; ch = getchar();}

	return s * w;

}

struct Tree

{

	struct node{

		int lc,rc;

		LL sum,add;

	}tr[10000010];

	void down(int o,int l,int r)//下放操作

	{

		if(tr[o].add)

		{

			int mid = (l+r)>>1;

			if(!tr[o].lc) tr[o].lc = build();//如果没有子节点就新建一个

			if(!tr[o].rc) tr[o].rc = build();

			tr[tr[o].lc].add += tr[o].add;//正常的下放操作

			tr[tr[o].rc].add += tr[o].add;

			tr[tr[o].lc].sum += 1LL * tr[o].add * (mid-l+1);

			tr[tr[o].rc].sum += 1LL * tr[o].add * (r-mid);

			tr[o].add = 0;

		}

	}

	int build()//新建一个节点

	{

		tot++;

		tr[tot].lc = tr[tot].rc = tr[tot].sum = 0;

		return tot;

	}

	void insert(int root,int L,int R,int x,int y,int val)//区间修改

	{

		if(x <= L && y >= R)

		{

			tr[root].add += val;

			tr[root].sum +=1LL * val * (R-L+1);

			return;

		}

		int mid = (L+R)>>1;

		down(root,L,R);//下放标记

		if(x <= mid)

		{

			if(!tr[root].lc) tr[root].lc = build();//一定要新开节点，不然就会RE

			insert(tr[root].lc,L,mid,x,y,val);

		}

		if(y > mid)

		{

			if(!tr[root].rc) tr[root].rc = build();

			insert(tr[root].rc,mid+1,R,x,y,val);

		}

		tr[root].sum = tr[tr[root].lc].sum + tr[tr[root].rc].sum;//up操作

	}

	LL ask(int root,int L,int R,int x,int y)//区间和

	{

		LL ans = 0;

		if(x <= L && y >= R){return tr[root].sum;}

		int mid = (L+R)>>1;

		down(root,L,R);

		if(!tr[root].lc) tr[root].lc = build();

		if(!tr[root].rc) tr[root].rc = build();

		if(x <= mid) ans += ask(tr[root].lc,L,mid,x,y);

		if(y > mid) ans += ask(tr[root].rc,mid+1,R,x,y);

		return ans;

	}

}tree;

int main()

{

	n = read(); m = read();

	root = tree.build();

	for(int i = 1; i <= n; i++)

	{

		x = read(); y = read();

		tree.insert(root,1,inf,x,inf,y);//从x到inf区间加y

	}

	for(int i = 1; i <= m; i++)

	{

		opt = read(); x = read(); y = read();

		if(opt == 1)

		{

			LL tmp = tree.ask(root,1,inf,x,y);

			double ans = (double) tmp / (double)(y-x+1);

			printf("%.4lf\n",ans);

		}

		if(opt == 2)

		{

			tree.insert(root,1,inf,x,inf,y);

		}

	}

	return 0;

}

巴特西