Codeforces438D 线段树取模

2019-04-13 14:10发布

站内文章 / 模拟电子
9726 0 1335

题意

单点修改， 区间求和， 区间模(不对整体和模， 对每一个数模).

题解

考虑每一个数被模， 如果模数大于它， 就不管. 如果模数p小于它， 则这个数每次被模过一次就缩小至少一半. 证明: 设数为x， 模数p > x/2， 则模一次肯定小于x之后肯定x/2.  若p < x/2， 那么模p后x < p， 所以后来x < x/2. 那么一个数最多被有效模log次. 一共nlogn次即可. 单点修改和全歼求和就很简单了. 区间要多存一个区间最大值. 因为有效模最多模log次， 如果模数大于自己的话就不用再去模了.  #include #include using namespace std; const int maxn = 100005; typedef long long dnt; int a[maxn], n, m; inline const int read(){ register int x = 0; register char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x; } struct node{ node *ls, *rs; dnt sum; int cmax; void update(){ cmax = max(ls->cmax, rs->cmax); sum = ls->sum + rs->sum; } }pool[maxn* 4], *tail = pool, *root; node* build(int lf, int rg){ node *bt = ++tail; if(lf == rg) {bt->sum = bt->cmax = a[lf]; return bt;} int mid = (lf + rg) >> 1; bt->ls = build(lf, mid), bt->rs = build(mid + 1, rg); bt->update(); return bt; } void modify(node *bt, int lf, int rg, int L, int R, int delta){ if(lf == rg){ bt->sum %= delta, bt->cmax %= delta; return; } int mid = (lf + rg) >> 1; if(L <= mid && delta <= bt->ls->cmax) modify(bt->ls, lf, mid, L, R, delta); if(R > mid && delta <= bt->rs->cmax) modify(bt->rs, mid + 1, rg, L, R, delta); bt->update(); } void modipoint(node *bt, int lf, int rg, int pos, int delta){ if(lf == rg){ bt->sum = delta, bt->cmax = delta; return; } int mid = (lf + rg) >> 1; if(pos <= mid) modipoint(bt->ls, lf, mid, pos, delta); else modipoint(bt->rs, mid + 1, rg, pos, delta); bt->update(); } dnt query(node *bt, int lf, int rg, int L, int R){ if(L <= lf && rg <= R) return bt->sum; int mid = (lf + rg) >> 1; dnt rt = 0; if(L <= mid) rt += query(bt->ls, lf, mid, L, R); if(R > mid) rt += query(bt->rs, mid + 1, rg, L, R); bt->update(); return rt; } int main(){ freopen("mod.in", "r", stdin); freopen("mod.out", "w", stdout); n = read(), m = read(); for(register int i = 1; i <= n; ++i) a[i] = read(); root = build(1, n); for(register int i = 1; i <= m; ++i){ int opt = read(), l = read(), r = read(), x; if(opt == 1) printf("%I64d ", query(root, 1, n, l, r)); if(opt == 2) x = read(), modify(root, 1, n, l, r, x); if(opt == 3) modipoint(root, 1, n, l, r); } } /* 5 5 1 2 3 4 5 2 3 5 4 3 3 5 1 2 5 2 1 3 3 1 1 3 */

热门文章