HDU 5828 Rikka with Sequence 【線段樹區間更新中單點更新】 好題!!!

NO IMAGE

傳送門
題目大意:
有三種操作: 1. 區間開根 2.區間加 3.詢問區間和

思路: 如果沒有第二種操作, 就非常簡單了, BZOJ上面有一道就是這種題, 因為開根的話每個數會下降的很快, 所以暴力的搞也不會搞太久, 但是有了區間加就不一樣了.. 比如 3 4 3 4 3 4 3 4 …. 這段區間暴力搞的話, 會變成 1 2 1 2 1 2 1 2 …. 但是如果在區間加2, 有變成3 4 3 4 3 4 3 4 …. 了, 這樣不斷搞就會把你卡超時.. 所以我們需要轉化. 當這個區間的max – min == 1時並且開完根後的max – min == 1的話, 那麼我們就可以做區間減法, 而不是暴力的修改. 像剛才那個就是區間-2即可. 或者是區間max == min 在開根前後, 那麼我們就可以是做區間覆蓋…

這道題非常卡時. 所以還是加一個外掛吧.
AC Code

const int maxn = 1e5   5;
ll a[maxn], n, m;
inline void read(ll &x) {
static char c;
while(!isdigit(c = getchar()));
x = c - '0';
while( isdigit(c = getchar()))
x = x * 10   (c - '0');
}
struct Tree {
int tl, tr; ll val, lazyadd, lazyset, mx, mi;
void funadd(ll tmp) {
lazyadd  = tmp;
val  = (tr - tl   1) * tmp;
mx  = tmp; mi  = tmp;
}
void funset(ll tmp) {
lazyset = tmp; lazyadd = 0;
val = (tr - tl   1) * tmp;
mx = mi = tmp;
}
}tre[maxn<<2];
void pushup(int id) {
tre[id].val = tre[id<<1].val tre[id<<1|1].val;
tre[id].mx = max(tre[id<<1].mx, tre[id<<1|1].mx);
tre[id].mi = min(tre[id<<1].mi, tre[id<<1|1].mi);
}
void pushdown(int id) {
if(tre[id].lazyset != 0) {
tre[id<<1].funset(tre[id].lazyset);
tre[id<<1|1].funset(tre[id].lazyset);
tre[id].lazyset = 0;
}
if(tre[id].lazyadd != 0) {
tre[id<<1].funadd(tre[id].lazyadd);
tre[id<<1|1].funadd(tre[id].lazyadd);
tre[id].lazyadd = 0;
}
}
void build(int id,int l,int r) {
tre[id].tl = l; tre[id].tr = r;
tre[id].lazyadd = tre[id].lazyset = 0;
if(l == r) {
read(a[l]);
tre[id].val = tre[id].mx = tre[id].mi = a[l];
return ;
}
int mid = (l r) >> 1;
build(id<<1, l, mid);
build(id<<1|1, mid 1, r);
pushup(id);
}
void update(int id, int ul, int ur, ll val) {
int l = tre[id].tl, r = tre[id].tr;
if(ul <= l && r <= ur) {
tre[id].funadd(val);
return ;
}
pushdown(id);
int mid = (l r) >> 1;
if(ul <= mid) update(id<<1, ul, ur, val);
if(ur > mid) update(id<<1|1, ul, ur, val);
pushup(id);
}
bool check(int id) {
if(tre[id].mx - tre[id].mi <= 1)
return true;
return false;
}
void ok(int id, int ul, int ur) {
int l = tre[id].tl, r = tre[id].tr;
if (tre[id].mx <= 1) return ;
if(ul <= l && r <= ur && check(id)) {
ll t1 = sqrt(tre[id].mx 0.1);
ll t2 = sqrt(tre[id].mi 0.1);
if (t1 == t2) tre[id].funset(t1);
else tre[id].funadd(t1 - tre[id].mx);
return ;
}
pushdown(id);
int mid = (l r) >> 1;
if(ul <= mid) ok(id<<1, ul, ur);
if(ur > mid) ok(id<<1|1, ul, ur);
pushup(id);
}
ll query_sum(int id, int ql, int qr) {
int l = tre[id].tl , r = tre[id].tr;
if(ql <= l && r <= qr) {
return tre[id].val;
}
pushdown(id);
int mid = (l r) >> 1 ;
if(qr <= mid) return query_sum(id<<1, ql, qr);
else if(ql > mid) return query_sum(id<<1|1, ql, qr);
else return query_sum(id<<1, ql, mid)   query_sum(id<<1|1, mid 1, qr);
}
void out(ll a) {
if(a > 9) out(a / 10);
putchar(a % 10   '0');
}
void solve() {
read(n); read(m);
build(1, 1, n);
while(m--) {
ll op, l, r;
read(op); read(l); read(r);
if (op == 1) {
ll x; read(x);
update(1, l, r, x);
}
else if (op == 2) ok(1, l, r);
else {
out(query_sum(1, l, r)); putchar('\n');
}
}
}