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;
}