「Luogu2221」[HAOI2012]高速公路

problem

题目描述

Y901Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。

Y901Y901高速公路是一条由N−1N-1段路以及NN个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为11~NN，从收费站ii行驶到i+1i+1(或从i+1i+1行驶到ii)需要收取ViV_i的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小AA同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r)l,r(l<r),在第ll个到第rr个收费站里等概率随机取出两个不同的收费站aa和bb，那么从aa行驶到bb将期望花费多少费用呢?

输入输出格式

输入格式：

第一行22个正整数N,MN,M，表示有NN个收费站，MM次调整或询问

接下来M行，每行将出现以下两种形式中的一种

C l r v
表示将第ll个收费站到第rr个收费站之间的所有道路的通行费全部增加vv

Q l r
表示对于给定的l,rl,r，要求回答小AA的问题

所有CC与QQ操作中保证1≤l<r≤N1\le l < r\le N

输出格式：

对于每次询问操作回答一行，输出一个既约分数

若答案为整数aa，输出a/1

输入输出样例

输入样例#1：

1
2
3
4
5
6
4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

输出样例#1：

1
2
3
1/1
8/3
17/6

说明

所有CC操作中的vv的绝对值不超过1000010000

在任何时刻任意道路的费用均为不超过1000010000的非负整数

所有测试点的详细情况如下表所示

1
2
3
4
5
6
7
8
9
10
11
Test N M
1    =10       =10
2    =100      =100
3    =1000     =1000
4    =10000    =10000
5    =50000    =50000
6    =60000    =60000
7    =70000    =70000
8    =80000    =80000
9    =90000    =90000
10   =100000   =100000

Solution

首先非常感谢@GoldenPotato先辈和我一起颓柿子

讲真

这个题除了最终计算答案稍微要用一下期望

跟期望基本没有关系（绝望）

首先，对于每次询问，在区间[l,r][l,r]中，任选两个点显然有Cr−l+12C_{r-l+1}^{2}种选法，每种选法的概率都是1Cr−l+12\frac{1}{C_{r-l+1}^{2}}

令所有选法的长度之和为sumsum，那么答案即为

sumCr−l+12\frac{sum}{C_{r-l+1}^{2}}

好了上面就是跟期望有关的部分，现在来看sumsum如何维护

令viv_i表示收费站i,i+1i,i+1之间的的收费

画图可知，对于每次询问l,rl,r，考虑每一段的贡献，有sum=∑i=1r−li∗(r−l−i+1)∗vl+i−1sum=\sum_{i=1}^{r-l}i*(r-l-i+1)*v_{l+i-1}

以l=2,r=6l=2,r=6为例，那么sumsum即为1∗4∗v2+2∗3∗v3+3∗2∗v4+4∗1∗v51*4*v_2+2*3*v_3+3*2*v_4+4*1*v_5

显然这玩意很难维护，我们来颓柿子

∑i=1r−li∗(r−l−i+1)∗vl+i−1\sum_{i=1}^{r-l}i*(r-l-i+1)*v_{l+i-1}

=(r−l+1)∑i=1r−li∗vl+i−1−∑i=1r−li2∗vl+i−1=(r-l+1)\sum_{i=1}^{r-l}i*v_{l+i-1}-\sum_{i=1}^{r-l}i^2*v_{l+i-1}

然而柿子中的各项依然比较难维护，因为每次ll都是不同的，我们来继续变形

∑i=1r−li∗vl+i−1=∑i=1r−l(l+i−1)∗vl+i−1−(l−1)∑i=1r−lvl+i−1\sum_{i=1}^{r-l}i*v_{l+i-1}=\sum_{i=1}^{r-l}(l+i-1)*v_{l+i-1}-(l-1)\sum_{i=1}^{r-l}v_{l+i-1}

这样我们只需要维护i∗vii*v_i和viv_i的区间和即可求出∑i=1r−li∗vl+i−1\sum_{i=1}^{r-l}i*v_{l+i-1}

这不禁令我们想到我们是否可以通过维护i2∗vii^2*v_i的区间和来处理剩下的一项

首先经过变形可得(l+i−1)2=(l−1)2+(2l−2)i+i2(l+i-1)^2=(l-1)^2+(2l-2)i+i^2

于是有

∑i=1r−li2∗vl+i−1=∑i=1r−l(l+i−1)2∗vl+i−1−(l−1)2∑i=1r−lvl+i−1−(2l−2)∑i=1r−li∗vl+i−1\sum_{i=1}^{r-l}i^2*v_{l+i-1}=\sum_{i=1}^{r-l}(l+i-1)^2*v_{l+i-1}-(l-1)^2\sum_{i=1}^{r-l}v_{l+i-1}-(2l-2)\sum_{i=1}^{r-l}i*v_{l+i-1}

这样我们就又可以通过维护i2∗vii^2*v_i的区间和求出∑i=1r−li2∗vl+i−1\sum_{i=1}^{r-l}i^2*v_{l+i-1}推死我了我去

区间修改及区间求和显然可以通过线段树来维护

然而这几个量维护起来也挺恶心的

所以这个题其实是披着期望的外皮，实际上是颓柿子和数据结构的题

实际实现中要注意分清楚点和边的编号

Code

非常丑，慎看

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100005
#define maxm 100005
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> void read(T &t)
{
	t=0;ull f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

ull n,m;

ull gcd(ull a,ull b)
{
	return b?gcd(b,a%b):a;
}

inline ull IS(ull l,ull r)//{n}数列区间求和
{
	--l;
	return (r*(r+1)/2)-(l*(l+1)/2);
}

inline ull QS(ull l,ull r)//{n^2}数列区间求和
{
	--l;
	return (r*(r+1)*(2*r+1)/6)-(l*(l+1)*(2*l+1)/6);
}

#define lson (num<<1)
#define rson ((num<<1)|1)
struct sgt
{
	struct node
	{
		ull l,r;
		ull nons,is,qs,lazy;//vi,i*vi,i^2*vi
	}t[maxn<<2];
	void Build(ull l,ull r,ull num=1)
	{
		t[num].l=l;
		t[num].r=r;
		if(l==r)return;
		ull mid=(l+r)>>1;
		Build(l,mid,lson);
		Build(mid+1,r,rson);
	}
	void maintain(ull num)
	{
		t[num].nons=t[lson].nons+t[rson].nons;
		t[num].is=t[lson].is+t[rson].is;
		t[num].qs=t[lson].qs+t[rson].qs;
	}
	void pushdown(ull num)
	{
		ull llen=t[lson].r-t[lson].l+1,rlen=t[rson].r-t[rson].l+1;
		t[lson].lazy+=t[num].lazy,t[rson].lazy+=t[num].lazy;
		t[lson].nons+=llen*t[num].lazy;
		t[rson].nons+=rlen*t[num].lazy;
		t[lson].is+=t[num].lazy*IS(t[lson].l,t[lson].r);
		t[rson].is+=t[num].lazy*IS(t[rson].l,t[rson].r);
		t[lson].qs+=t[num].lazy*QS(t[lson].l,t[lson].r);
		t[rson].qs+=t[num].lazy*QS(t[rson].l,t[rson].r);
		t[num].lazy=0;
	}
	void ADD(ull l,ull r,ull x,ull num=1)
	{
		if(t[num].l>r || t[num].r<l)return;
		if(l<=t[num].l && r>=t[num].r)
		{
			t[num].lazy+=x;
			ull len=t[num].r-t[num].l+1;
			t[num].nons+=len*x;
			t[num].is+=IS(t[num].l,t[num].r)*x;
			t[num].qs+=QS(t[num].l,t[num].r)*x;//更新答案部分，至于为什么是这样可以自己推一下
			return;
		}
		pushdown(num);
		ADD(l,r,x,lson),ADD(l,r,x,rson);
		maintain(num);
	}
	ull nonsQuery(ull l,ull r,ull num=1)
	{
		if(t[num].l>r || t[num].r<l)return 0;
		if(l<=t[num].l && r>=t[num].r)
			return t[num].nons;
		pushdown(num);
		return nonsQuery(l,r,lson)+nonsQuery(l,r,rson);
	}
	ull isQuery(ull l,ull r,ull num=1)
	{
		if(t[num].l>r || t[num].r<l)return 0;
		if(l<=t[num].l && r>=t[num].r)
			return t[num].is;
		pushdown(num);
		return isQuery(l,r,lson)+isQuery(l,r,rson);
	}
	ull qsQuery(ull l,ull r,ull num=1)
	{
		if(t[num].l>r || t[num].r<l)return 0;
		if(l<=t[num].l && r>=t[num].r)
			return t[num].qs;
		pushdown(num);
		return qsQuery(l,r,lson)+qsQuery(l,r,rson);
	}
}t;

int main()
{
	read(n),read(m);
	t.Build(1,n-1);
	while(m--)
	{
		char op=getchar();
		while(op!='C' && op!='Q')op=getchar();
		if(op=='C')
		{
			ull l,r;ull x;
			read(l),read(r),read(x);
			t.ADD(l,r-1,x);
		}
		else
		{
			ull l,r;
			read(l),read(r);
			ull a=t.isQuery(l,r-1)-(l-1)*t.nonsQuery(l,r-1);
			ull b=t.qsQuery(l,r-1)-(l-1)*(l-1)*t.nonsQuery(l,r-1)-(2*l-2)*a;
			ull fz=a*(r-l+1)-b,fm=(r-l+1)*(r-l)/2,g=gcd(fz,fm);
			fz/=g,fm/=g;
			printf("%llu/%llu\n",fz,fm);
		}
	}
	return 0;
}

一点思考

请忽略以下胡言乱语

我发现这样算的话用long longlong\space long是会豹的（捂脸）

所以我干脆把所有变量都改成unsigned long longunsigned\space long\space long

至于为什么在负数存在的情况下是正确的

如果使用ullull，实际上就是在模264−12^{64}-1的意义下做运算，而最终答案是在llll范围内的，并且为正整数

所以就阔以啦