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

AC Code

``````const int maxn = 1e5   5;
ll a[maxn], n, m;
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;
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;
}
}
}
void build(int id,int l,int r) {
tre[id].tl = l; tre[id].tr = r;
if(l == r) {
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) {
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);
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() {
build(1, 1, n);
while(m--) {
ll op, l, r;