Skip to content

11395: 【原1395】小Z的难题

题目

题目描述

author: greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1395

Description

“采蘑菇的小姑娘,背着个书包上学堂。”

小Z就是这样一个天资聪颖、刻苦勤奋的女孩。最近,她遇到了这样一道题:

给定一个长度为n的数列,设计一个数据结构,要求:
    (1)支持区间赋值(即给一段区间里的数赋上同一个给定的值)
    (2)支持区间求和

对于这样简单的线段树模板题小Z随手就秒掉了。万恶的MKK当然不会允许这样的事发生,于是他把题目强化为这样:

给定一个长度为n的数列,设计一个数据结构,要求:
    (1)支持区间赋值(即给一段区间里的数赋上同一个给定的值)
    (2)支持区间取绝对值(即把一段区间里面的数变成它们各自的绝对值)
    (3)支持区间求和

小Z眨了下眼睛,又把这题给秒了。

MKK愤怒了,决定在所有的n(n+1)/2个区间中随机抽一个出来,问它的区间和期望多大。

可怜的小Z连期望的定义都不懂,于是寻求你来帮忙。

Input Format

第一行一个整数n表示数列的长度

第二行有n个整数,表示初始时的数列

第三行一个整数Q,表示操作个数

接下来Q行每行表示一个操作,是下面3种格式中的一个:

1 l r x 令\(a_i=x\),其中\(l \leq i \leq r \)

2 l r 令\(a_i=|a_i|\),其中\(l \leq i \leq r \)

3 询问区间和的期望

Output Format

对于每一个询问,输出答案。如果答案的绝对值大于等于10,000,保留4位有效数字并输出前4位,否则四舍五入到整数位。

Sample Input

3
11111111 5140809 7
5
3
1 1 2 -5140309
3
2 1 1
3

Sample Output

8983
-5997
-8567

Limits

对于20%的数据,1≤n,Q≤1,000

对于另外10%的数据,没有1、2操作

对于另外20%的数据,没有2操作

对于100%的数据,1≤n,Q≤100,000且数列中的每个元素的绝对值都不超过100,000,000

数据保证不会有一个询问的答案为0

Hint

样例说明:

初始时序列为[11111111 5140809 7]

有6个区间可供MKK选择,它们的和分别为11111111, 5140809, 7, 16251920, 5140816, 16251927

所以期望为53896590/6=8982765

经过第2步操作后序列为[-5140309 -5140309 7]

经过第4个操作后序列为[5140309 -5140309 7]


那么奇怪的输出格式只是为了降低精度要求

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1395.md
*/
#include <bits/stdc++.h>
#define MAXN 270005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, siz, opr, _a, _b;
double _v, tag[MAXN] = {0};;
double seg[MAXN] = {0}, seg_abs[MAXN] = {0};
double suml[MAXN] = {0}, sumr[MAXN] = {0}, sum[MAXN] = {0};
double suml_abs[MAXN] = {0}, sumr_abs[MAXN] = {0}, sum_abs[MAXN] = {0};
int len[MAXN] = {0};
bool tag_valid[MAXN] = {0}, abs_tag[MAXN] = {0};
void maintain(int id){
    int lch = id << 1, rch = (id << 1 | 1);
    seg[id] = seg[lch] + seg[rch];
    seg_abs[id] = seg_abs[lch] + seg_abs[rch];
    suml[id] = suml[lch] + suml[rch] + len[rch] * seg[lch];
    sumr[id] = sumr[rch] + sumr[lch] + len[lch] * seg[rch];
    sum[id] = sum[lch] + sum[rch] + sumr[lch] * len[rch] + suml[rch] * len[lch];
    suml_abs[id] = suml_abs[lch] + suml_abs[rch] + len[rch] * seg_abs[lch];
    sumr_abs[id] = sumr_abs[rch] + sumr_abs[lch] + len[lch] * seg_abs[rch];
    sum_abs[id] = sum_abs[lch] + sum_abs[rch] + sumr_abs[lch] * len[rch] + suml_abs[rch] * len[lch];
}
void calc(int id, double x){
    seg[id] = x * len[id], seg_abs[id] = abs(seg[id]);
    suml[id] = 0.5 * x * len[id] * (len[id] + 1), suml_abs[id] = abs(suml[id]);
    sumr[id] = suml[id], sumr_abs[id] = suml_abs[id];
    sum[id] = x * len[id] * (len[id] + 1) * (len[id] + 2) / 6.0;
    sum_abs[id] = abs(sum[id]);
}
void calc2(int id){
    seg[id] = seg_abs[id];
    sum[id] = sum_abs[id];
    suml[id] = suml_abs[id];
    sumr[id] = sumr_abs[id];
}
void pushdown(int id){
    int lch = id << 1, rch = (id << 1 | 1);
    if (tag_valid[id]){
        calc(lch, tag[id]);
        calc(rch, tag[id]);
        tag[lch] = tag[rch] = tag[id];
        tag_valid[lch] = tag_valid[rch] = true;
        abs_tag[lch] = abs_tag[rch] = false;
        tag_valid[id] = false;
    }
    if (abs_tag[id]){
        calc2(lch);
        calc2(rch);
        if (tag_valid[lch]) tag[lch] = abs(tag[lch]);
        else abs_tag[lch] = true;
        if (tag_valid[rch]) tag[rch] = abs(tag[rch]);
        else abs_tag[rch] = true;
        abs_tag[id] = false;
    }
}
void update(int id, int l, int r){
    if (l > _b || r < _a) return ;
    if (l >= _a && r <= _b){
        if (opr == 1){
            calc(id, _v);
            tag[id] = _v, tag_valid[id] = true;
            abs_tag[id] = false;
        }else {
            calc2(id);
            if (tag_valid[id]) tag[id] = abs(tag[id]);
            else abs_tag[id] = true;
        }
        return ;
    }
    pushdown(id);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid);
    update(id << 1 | 1, mid + 1, r);
    maintain(id);
}
void init(){
    n = read();
    for (siz = 1; siz < n; siz <<= 1)
        ;
    REP(i, siz, siz + n - 1){
        seg[i] = read(), seg_abs[i] = abs(seg[i]), 
        suml[i] = sumr[i] = sum[i] = seg[i], 
        suml_abs[i] = sumr_abs[i] = sum_abs[i] = seg_abs[i], 
        len[i] = 1;
    }
    REPR(i, siz - 1, 1){
        len[i] = len[i << 1] + len[i << 1 | 1];
        maintain(i);
    }
}
void solve(){
    int q = read();
    while (q--){
        opr = read();
        if (opr == 1){
            _a = read(), _b = read(), _v = read();
            update(1, 1, siz);
        }
        if (opr == 2){
            _a = read(), _b = read();
            update(1, 1, siz);
        }
        if (opr == 3){
            double res = sum[1];
            res /= 0.5 * n * (n + 1);
            while (abs(res) >= 10000.0)
                res /= 10.0;
            printf("%.0lf\n", res);
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}