CodeForces 438D

description： 长度为n的非负整数数列，3种操作
1. 求[L,R]所有数的和。
2. 将[L,R]中所有数都mod x。
3. 将a[i]修改为v。
n,m≤100000 input 第一行两个整数n，m，表示数列元素个数和操作数
接下来n个数，表示序列
接下来m行，每行开头一个整数表示操作 output 对于每一个询问操作，输出一个整数表示答案 思路：
摘自 < berrykanry >
链接
如果没有2操作的话，还是很简单的线段树裸题，单点修改，区间查询
现在考虑怎么处理这个取模的问题
对于一段区间，如果取模的数比这段区间所有的数都大，那取模就是没有意义的，就是说，如果取模的数比区间最大的数还大，那么就不用取模了，所以我们在线段树里再记录一个区间最大值
考虑每次取模，对于每一个数x，取模y，x mod y的值必然比y小，如果y小于x/2，那x就变得小于x/2，如果y大于x/2，x剩下的部分也比x/2少，x也会变得比x/2小
那么就是说x每次取模都会变得比x/2小，就是说，对于一个数x，有效的取mod最多进行logx次，一共只会进行nlogn次取模，那么就算对所有的数取模，这个时间复杂度都是可以接受的
分析一波之后，发现，直接暴力去取模是可行的。
那么我们对于每个区间记录一个最大值，如果取模的数大于最大值，就不管，如果小于最大值，就暴力取模 #include #include #include #define LL long long #define N 100010 using namespace std; int n, m; LL a[N]; struct node{ LL sum, flag; node *ls,*rs; void update(){ sum = ls->sum + rs->sum; flag = max(ls->flag, rs->flag); } }pool[N << 4], *tail = pool, *root, *null; void init(){ null = ++tail; null->sum = null->flag = 0; null->ls = null->rs = null; } node *newnode(){ node *nd = ++tail; nd->ls = nd->rs = null; nd->sum = nd->flag = 0; return nd; } node *build(int lf, int rg){ node *nd = newnode(); if(lf == rg){ nd->flag = nd->sum = a[lf]; return nd; } int mid = (lf + rg) >> 1; nd->ls = build(lf, mid); nd->rs = build(mid+1, rg); nd->update(); return nd; } void modify(node *nd, int lf, int rg, int pos, LL val){ if(lf == rg){ nd->sum = nd->flag = val; return ; } int mid = (lf + rg) >> 1; if(pos <= mid) modify(nd->ls, lf, mid, pos, val); else modify(nd->rs, mid+1, rg, pos, val); nd->update(); } void modify_mod(node *nd, int lf, int rg, int L, int R, LL val){ if(nd->flag < val) return; if(lf == rg){ nd->sum %= val; nd->flag %= val; return ; } int mid = (lf + rg) >> 1; if(L <= mid) modify_mod(nd->ls, lf, mid, L, R, val); if(R > mid) modify_mod(nd->rs, mid+1, rg, L, R, val); nd->update(); } LL query(node *nd, int lf, int rg, int L, int R){ if(L<=lf && rg<=R) return nd->sum; int mid = (lf + rg) >> 1; LL rt = 0; if(L <= mid) rt += query(nd->ls, lf, mid, L, R); if(R > mid) rt += query(nd->rs, mid+1, rg, L, R); return rt; } int main(){ freopen ("mod.in", "r", stdin); freopen ("mod.out", "w", stdout); init(); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%I64d", &a[i]); root = build(1, n); while( m-- ){ int opt; LL val; scanf("%d", &opt); if(opt == 3){ int x; scanf("%d%I64d", &x, &val); modify(root, 1, n, x, val); } else if(opt == 2){ int x, y; scanf("%d%d%I64d", &x, &y, &val); modify_mod(root, 1, n, x, y, val); } else if(opt == 1){ int x, y; scanf("%d%d", &x, &y); printf("%I64d ", query(root, 1, n, x, y)); } } return 0; }