[線分樹+区間加算]LightOJ 1183-Computting Fast Average

テーマリンク:
http://lightoj.com/volume_showproblem.php？problem=1183
1183-Computting Fast Average

PDF(English)
Statistics
Forum
Time Limit:2 second(s)
メモリLimit:64 MB
Gven an array of integers(0 indexed)、you have to perform two types of queries in the array.
1.1 i j v-change the value of the elemens froomithindex tojthindex tov.
2.2 i i-find the average value of the integers froomithindex tojthindex.
You can asome that initially all the values in the array are 0.
Input
Input starts with an integerT(≦5)、denoting the number of test cases.
Each case contains two integers:n(1≦n≦105)、q(1≦q≦50000)、whereendenotes the size of the array.Each of the nextqline s will contain a query of the form:
1 i j v(0≦i≦j＜n,0≦v≦10000)
2 i j(0≦i≦j＜n)
Output
For each case,print the case number first.The n for each query of the form'2 i i i i i i i i'prininininininentthe average value of the integers froomitj.If the rereult is is an integer,print itititititititit. Othethethetherwise prisisprisprininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininin
Sample Input
Output for Sample Input
1 10 6 1 0 6 2 0 1 1 1 2 0 5 1 0 3 7 2 0 1
Case 1:6 6/3 7
ノート
Dataset is huge.Use faster i/o methods.
列を指定すると、区間の平均数が更新されます.
分析:少し変化をしました.出力を簡単にしてください.gcdで約分すればいいです.
線分樹:点樹-段更新-区間問い合わせ.
コード:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 111111;
int sum[MAXN<<2],cov[MAXN<<2],t,n,q;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void build(){
    memset(sum,0,sizeof(sum));
    memset(cov,-1,sizeof(cov));
}
void pushDOWN(int rt,int l,int r){
    if(cov[rt]!=-1){
        int m = (l+r)>>1;
        sum[rt<<1] = (m-l+1)*cov[rt];
        sum[rt<<1|1] = (r-m)*cov[rt];
        cov[rt<<1] = cov[rt<<1|1] = cov[rt];
        cov[rt] = -1;
    }
}
void pushUP(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&R>=r){
        cov[rt] = c;
        sum[rt] = (r-l+1)*c;
        return;
    }
    pushDOWN(rt,l,r);
    int m = (l+r)>>1;
    if(m>=L)update(L,R,c,lson);
    if(m<R)update(L,R,c,rson);
    pushUP(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return sum[rt];
    }
    pushDOWN(rt,l,r);
    int m = (l+r)>>1,ret = 0;
    if(m>=L)ret+=query(L,R,lson);
    if(m<R)ret+=query(L,R,rson);
    pushUP(rt);
    return ret;
}
int gcd(int a,int b){
    return ((a%b)==0)?b:gcd(b,a%b);
}
void print(int cas,int mo,int so){
    int div = gcd(mo,so);
    mo/=div;so/=div;
    if(so==1){
        printf("%d
",mo);
    }else if(mo!=0){
        printf("%d/%d
",mo,so);
    }else{
        printf("%d
",0);
    }
}
int main(){
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        scanf("%d%d",&n,&q);
        build();
        printf("Case %d:
",cas);
        while(q--){
            int a,b,c,d;
            scanf("%d",&a);
            if(a==1){
                scanf("%d%d%d",&b,&c,&d);
                update(b,c,d,0,n-1,1);
            }else{
                scanf("%d%d",&b,&c);
                int mo = query(b,c,0,n-1,1);
                print(cas,mo,(c-b+1));
            }
        }
    }
    return 0;
}