|
|
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2706
  /**//*
 题意：
给定一个长度为N(N <= 30000)的数列Si，紧接着Q条区间处理，每一条处理的要
求是将给定的区间内的数字替换成他们的平均值，替换时如果当前数列的总和比原先
数列的总和小或者相等时，平均值向上取整，否则向下取整，最后要求输出处理完的
数组的每一个元素。
解法：
线段树
思路：
一看到数据量就可以首先确定是线段树了，然后我们来把这题需要求的东西分解
一下，题目中提到当前数列和和原数列和比较大小，所以首先一个操作就是区间求和
，然后将区间内的数替换成另外一个数，这就用到了区间修改，和线段树的操作完全
吻合。接下来就可以开始设计线段树结点的域了。其实这题的思想和pku 3468是大同
小异的，还是lazy思想。每次插入的时候不更新到叶子结点，在插入区间完全覆盖当
前区间时就返回，否则将当前结点的lazy标记传递给左右儿子，并且更新左右儿子的
sum值，注意，这里每次不是累加，因为是修改，所以直接将 sum*左右儿子的区间长
度 分别赋值给左右儿子即可。递归结束时更新当前结点的sum值。询问时也是相同，
每次传递lazy标记给儿子。这样就可以做到询问和插入都是log(n)。
 */
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 30010
#define inf INT_MIN
#define ll long long
struct Tree  {
int p, l, r;
ll sum;
ll lazy_tag;
void ClearTag();
  int GetMid() {
return (l + r) >> 1;
 }
int GetLen() {
return r - l + 1;
}
}T[4*maxn];
void Tree::ClearTag() {
if(lazy_tag) {
T[p<<1].lazy_tag = lazy_tag;
T[p<<1|1].lazy_tag = lazy_tag;
T[p<<1].sum = lazy_tag * T[p<<1].GetLen();
T[p<<1|1].sum = lazy_tag * T[p<<1|1].GetLen();
lazy_tag = 0;
}
}
int n, m;
int val[maxn];
void Build(int p, int l, int r) {
T[p].l = l;
T[p].r = r;
T[p].p = p;
T[p].lazy_tag = 0;
if(l == r) {
T[p].sum = val[l];
return ;
}
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].sum = T[p<<1].sum + T[p<<1|1].sum;
}
ll Query(int p, int l, int r) {
if(l <= T[p].l && T[p].r <= r) {
return T[p].sum;
}
T[p].ClearTag();
int mid = T[p].GetMid();
ll v = 0;
if(l <= mid) {
v += Query(p<<1, l, r);
}
if(r >= mid + 1) {
v += Query(p<<1|1, l, r);
}
return v;
}
void Modify(int p, int l, int r, ll val) {
if(l <= T[p].l && T[p].r <= r) {
T[p].lazy_tag = val;
T[p].sum = val * T[p].GetLen();
return ;
}
T[p].ClearTag();
int mid = T[p].GetMid();
if(l <= mid) {
Modify(p<<1, l, r, val);
}
if(r >= mid + 1) {
Modify(p<<1|1, l, r, val);
}
T[p].sum = T[p<<1].sum + T[p<<1|1].sum;
}
ll Calc(ll val, int dn, bool bRoundUp) {
if(val >= 0) {
if(bRoundUp) {
return (val + dn - 1) / dn;
}else
return val / dn;
}else {
val = -val;
if(bRoundUp) {
return -(val / dn);
}else {
return -((val + dn - 1) / dn);
}
}
}
int main() {
int i;
int x, y;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
Build(1, 1, n);
ll ans = T[1].sum;
while(m--) {
scanf("%d %d", &x, &y);
ll Sum = Query(1, x, y);
ll all = Query(1, 1, n);
Sum = Calc(Sum, y-x+1, all <= ans);
Modify(1, x, y, Sum);
}
for(i = 1; i <= n; i++) {
if(i != 1)
printf(" ");
printf("%lld", Query(1, i, i));
}
puts("\n");
}
return 0;
}
|