首页 > 代码库 > CH Round #52 还教室[线段树 方差]
CH Round #52 还教室[线段树 方差]
还教室 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+5;#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|1typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,q,flag,l,r; ll d;struct node{ ll s,s2,lazy;}t[N<<2];inline void paint(int o,int l,int r,ll d){ t[o].lazy+=d; t[o].s2+=d*d*(r-l+1)+2*d*t[o].s; t[o].s+=d*(r-l+1);}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=0; }}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=0; 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=0; 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==0?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(1,1,n); for(int i=1;i<=q;i++){ flag=read();l=read();r=read(); if(flag==1){d=read();add(1,1,n,l,r,d);} else if(flag==2){ ll x=query1(1,1,n,l,r),len=r-l+1; print(x,len); }else{ ll x1=query1(1,1,n,l,r),x2=query2(1,1,n,l,r),len=r-l+1;//printf("hi %lld %lld\n",x1,x2); print(len*x2-x1*x1,len*len); } }}
CH Round #52 还教室[线段树 方差]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。