|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2706
  /**//*
 題意：
給定一個(gè)長(zhǎng)度為N(N <= 30000)的數(shù)列Si，緊接著Q條區(qū)間處理，每一條處理的要
求是將給定的區(qū)間內(nèi)的數(shù)字替換成他們的平均值，替換時(shí)如果當(dāng)前數(shù)列的總和比原先
數(shù)列的總和小或者相等時(shí)，平均值向上取整，否則向下取整，最后要求輸出處理完的
數(shù)組的每一個(gè)元素。
解法：
線(xiàn)段樹(shù)
思路：
一看到數(shù)據(jù)量就可以首先確定是線(xiàn)段樹(shù)了，然后我們來(lái)把這題需要求的東西分解
一下，題目中提到當(dāng)前數(shù)列和和原數(shù)列和比較大小，所以首先一個(gè)操作就是區(qū)間求和
，然后將區(qū)間內(nèi)的數(shù)替換成另外一個(gè)數(shù)，這就用到了區(qū)間修改，和線(xiàn)段樹(shù)的操作完全
吻合。接下來(lái)就可以開(kāi)始設(shè)計(jì)線(xiàn)段樹(shù)結(jié)點(diǎn)的域了。其實(shí)這題的思想和pku 3468是大同
小異的，還是lazy思想。每次插入的時(shí)候不更新到葉子結(jié)點(diǎn)，在插入?yún)^(qū)間完全覆蓋當(dāng)
前區(qū)間時(shí)就返回，否則將當(dāng)前結(jié)點(diǎn)的lazy標(biāo)記傳遞給左右兒子，并且更新左右兒子的
sum值，注意，這里每次不是累加，因?yàn)槭切薷模灾苯訉?nbsp;sum*左右兒子的區(qū)間長(zhǎng)
度 分別賦值給左右兒子即可。遞歸結(jié)束時(shí)更新當(dāng)前結(jié)點(diǎn)的sum值。詢(xún)問(wèn)時(shí)也是相同，
每次傳遞lazy標(biāo)記給兒子。這樣就可以做到詢(xún)問(wèn)和插入都是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;
}
|