还教室 CH Round #52 - Thinking Bear #1 (NOIP模拟赛)
【引子】
还记得 NOIP 2012 提高组 Day2 中的借教室吗？时光飞逝，光阴荏苒，两年
过去了，曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于
借教室的另一个问题。
【问题描述】
在接受借教室请求的 n 天中，第 i 天剩余的教室为 a i 个。作为大学借教室服
务的负责人，你需要完成如下三种操作共 m 次：
① 第 l 天到第 r 天，每天被归还 d 个教室。
② 询问第 l 天到第 r 天教室个数的平均数。
③ 询问第 l 天到第 r 天教室个数的方差。
【输入格式】
第一行包括两个正整数 n 和 m，其中 n 为借教室的天数，m 为操作次数。
接下来一行， 共包含 n 个整数， 第 i 个整数表示第 i 天剩余教室数目为 a i 个。
接下来 m 行，每行的第一个整数为操作编号（只能为 1 或 2 或 3） ，接下来
包含两个正整数 l 和 r，若操作编号为 1，则接下来再包含一个正整数 d。
【输出格式】
对于每个操作 2 和操作 3，输出一个既约分数（分子与分母互质）表示询问
的答案（详见样例） 。若答案为 0，请输出“0/1” （不含引号） 。
【样例输入】
5 4
1 2 3 4 5
1 1 2 3
2 2 4
3 2 4
3 1 5
【样例输出】
4/1
2/3
14/25
推导一下方差
D(X)=E(X^2)-E^2(X)
线段树维护区间和和区间平方和
区间平方和 t[o].s2+=d*d*(r-l+1)+2*d*t[o].s
PS：r-l+1的平方爆int了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N=1e5+;
#define m (l+r)/2
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define lc o<<1
#define rc o<<1|1
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,q,flag,l,r; ll d;
struct node{
ll s,s2,lazy;
}t[N<<];
inline void paint(int o,int l,int r,ll d){
t[o].lazy+=d;
t[o].s2+=d*d*(r-l+)+*d*t[o].s;
t[o].s+=d*(r-l+);
}
inline void merge(int o){
t[o].s=t[lc].s+t[rc].s;
t[o].s2=t[lc].s2+t[rc].s2;
}
inline void pushDown(int o,int l,int r){
if(t[o].lazy){
ll d=t[o].lazy;
paint(lson,d);
paint(rson,d);
t[o].lazy=;
}
}
void build(int o,int l,int r){
if(l==r) {ll a=read();t[o].s=a;t[o].s2=a*a;}
else{
build(lson);
build(rson);
merge(o);
}
}
void add(int o,int l,int r,int ql,int qr,ll d){
if(ql<=l&&r<=qr) paint(o,l,r,d);
else{
pushDown(o,l,r);
if(ql<=m) add(lson,ql,qr,d);
if(m<qr) add(rson,ql,qr,d);
merge(o);
}
}
ll query1(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[o].s;
else{
pushDown(o,l,r);
ll ans=;
if(ql<=m) ans+=query1(lson,ql,qr);
if(m<qr) ans+=query1(rson,ql,qr);
return ans;
}
}
ll query2(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[o].s2;
else{
pushDown(o,l,r);
ll ans=;
if(ql<=m) ans+=query2(lson,ql,qr);
if(m<qr) ans+=query2(rson,ql,qr);
return ans;
}
}
inline ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);}
void print(ll x,ll y){
ll g=gcd(x,y);
printf("%lld/%lld\n",x/g,y/g);
}
int main(){
n=read();q=read();
build(,,n);
for(int i=;i<=q;i++){
flag=read();l=read();r=read();
if(flag==){d=read();add(,,n,l,r,d);}
else if(flag==){
ll x=query1(,,n,l,r),len=r-l+;
print(x,len);
}else{
ll x1=query1(,,n,l,r),x2=query2(,,n,l,r),len=r-l+;//printf("hi %lld %lld\n",x1,x2);
print(len*x2-x1*x1,len*len);
}
}
}