Description
Y901高速公路是一条重要的交通纽带，*部门建设初期的投入以及使用期间的养护费用都不低，因此*在这条高速公路上设立了许多收费站。
Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。
*部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b，那么从a行驶到b将期望花费多少费用呢?
Input
第一行2个正整数N,M，表示有N个收费站，M次调整或询问
接下来M行，每行将出现以下两种形式中的一种
C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v
Q l r 表示对于给定的l,r，要求回答小A的问题
所有C与Q操作中保证1<=l<r<=N
Output
对于每次询问操作回答一行，输出一个既约分数
若答案为整数a，输出a/1
Sample Input
4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
Sample Output
1/1
8/3
17/6
8/3
17/6
HINT
数据规模
所有C操作中的v的绝对值不超过10000
在任何时刻任意道路的费用均为不超过10000的非负整数
所有测试点的详细情况如下表所示
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
Source
【分析】
比较简单的题目，推一下就知道要维护的值。
但是细节比较多，并且要维护好几个值，容易写错，建议在草稿纸上对着公式打。
明明超内存被bzoj说成TLE，你让我情何以堪...
/*
宋代志南
《绝句》
古木阴中系短篷，杖藜扶我过桥东。
沾衣欲湿杏花雨，吹面不寒杨柳风。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int MAXN = + ;
const int MAXM = + ;
const int INF = ;
const int SIZE = ;
const int maxnode = + ;
using namespace std;
long long add(long long val, long long len){
return val * (((len * (len + )) / ) * len + (len * (len + )) / - (len * (len + ) * ( * len + )) / );
}
long long n, m;
struct SEGTREE{
struct Node{
long long l, r;
long long sum, sum2, sum3;//代表总段和和带权和后面是反向的
long long addn, val;//val值代表整个区间的值
Node *ch[];
bool delta;//标记 void pushdown(){//标记下传
if (l == r) return;
if (delta){
ch[]->addn += addn;
ch[]->addn += addn;
ch[]->delta = ;ch[]->sum += add(addn, ch[]->r - ch[]->l + );ch[]->val += addn * (ch[]->r - ch[]->l + );
ch[]->delta = ;ch[]->sum += add(addn, ch[]->r - ch[]->l + );ch[]->val += addn * (ch[]->r - ch[]->l + );
long long len = ch[]->r - ch[]->l + ;
ch[]->sum2 += addn * ((len * (len + )) / );
ch[]->sum3 += addn * ((len * (len + )) / );
len = ch[]->r - ch[]->l + ;
ch[]->sum2 += addn * ((len * (len + )) / );
ch[]->sum3 += addn * ((len * (len + )) / );
delta = ;
addn = ;
}
return;
}
void update(){
if (l == r) return;
val = ch[]->val + ch[]->val;
//正反向
sum2 = ch[]->sum2 + ch[]->sum2 + ch[]->val * (ch[]->r - ch[]->l + );
sum3 = ch[]->sum3 + ch[]->sum3 + ch[]->val * (ch[]->r - ch[]->l + );
sum = ;
sum += ch[]->sum + ch[]->sum2 * (ch[]->r - ch[]->l + );
sum += ch[]->sum + ch[]->sum3 * (ch[]->r - ch[]->l + );
return;
}
}*root, mem[maxnode];
long long tot; void init(){
root = NULL;
tot = ;
build(root, , n - );//n个点n-1条边
}
Node *NEW(long long l, long long r){
Node *p = &mem[tot++];
p->l = l;
p->r = r;
p->addn = p->delta = p->val = p->sum2 = ;
return p;
}
void build(Node *&t, long long l, long long r){
if (t == NULL){
t = NEW(l, r);
}
if (l == r) return;
long long mid = (l + r) >> ;
build(t->ch[], l, mid);
build(t->ch[], mid + , r);
return;
}
//lr一段的值全部加val
void insert(Node *&t, long long l, long long r, long long val){
t->pushdown();
if (l <= t->l && t->r <= r){
t->delta = ;
t->addn += val;
t->sum += add(val, t->r - t->l + );
t->val += val * (t->r - t->l + );
long long len = t->r - t->l + ;
t->sum2 += val * ((len * (len + )) / );
t->sum3 += val * ((len * (len + )) / );
return;
}
long long mid = (t->l + t->r) >> ;
if (l <= mid) insert(t->ch[], l, r, val);
if (r > mid) insert(t->ch[], l, r, val);
t->update();
}
long long query(Node *&t, long long l, long long r){
t->pushdown();
if (l <= t->l && t->r <= r){
long long Ans = t->sum;
//先朝右边扩张
Ans += (t->sum2 * (r - t->r));
Ans += ((t->sum3 + t->val * (r - t->r)) * (t->l - l));
return Ans;
}
long long mid = (t->l + t->r) >> ;
long long tmp = ;
if (l <= mid) tmp += query(t->ch[], l, r);
if (r > mid) tmp += query(t->ch[], l, r);
t->update();
return tmp;
}
}A; void init(){
scanf("%lld%lld", &n, &m);
A.init();
}
long long gcd(long long a, long long b){return b == ? a: gcd(b, a % b);}
void work(){
for (long long i = ; i <= m; i++){
char str[];
scanf("%s", str);
if (str[] == 'C'){
long long l, r;
long long val;
scanf("%lld%lld%lld", &l, &r, &val);
r--;
A.insert(A.root, l, r, val);
}else if (str[] == 'Q'){
long long l, r;
scanf("%lld%lld", &l, &r);
long long tmp = r - l + ;
r--;
if (l == && r == )
printf("");
long long a = A.query(A.root, l, r), b = (tmp * (tmp - )) / ;
long long c = gcd(a, b);
printf("%lld/%lld\n", a / c, b / c);
}
}
} int main(){ init();
work();
return ;
}