题目
给定一个长为n的序列,要求支持区间求和,区间取余,单点修改
题解
首先我们有一个结论:
若(x > p)那么有((x ext{ }mod ext{ }p) <= frac{x}{2})
所以我们在区间取余时利用区间最大值来剪枝后.
由势能分析法易得总体复杂度是(O(nlon^2n))的.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 100010;
ll mx[maxn<<2],sum[maxn<<2],a[maxn];
void build(int rt,int l,int r){
if(l == r){
mx[rt] = sum[rt] = a[l];
return;
}
int mid = l+r >> 1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
ll L,R,val;
ll query(int rt,int l,int r){
if(L <= l && r <= R) return sum[rt];
int mid = l+r >> 1;
if(R <= mid) return query(rt<<1,l,mid);
if(L > mid) return query(rt<<1|1,mid+1,r);
return query(rt<<1,l,mid) + query(rt<<1|1,mid+1,r);
}
void mod(int rt,int l,int r){
if(l == r){
mx[rt] = sum[rt] = sum[rt] % val;
return ;
}
if(mx[rt] < val) return;
int mid = l+r >> 1;
mod(rt<<1,l,mid);mod(rt<<1|1,mid+1,r);
mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void search(int rt,int l,int r){
if(L <= l && r <= R){
mod(rt,l,r);
return ;
}
int mid = l+r >> 1;
if(L <= mid) search(rt<<1,l,mid);
if(R > mid) search(rt<<1|1,mid+1,r);
mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
int pos;
void modify(int rt,int l,int r){
if(l == r){
mx[rt] = sum[rt] = val;
return ;
}
int mid = l+r >> 1;
if(pos <= mid) modify(rt<<1,l,mid);
if(pos > mid) modify(rt<<1|1,mid+1,r);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
}
int main(){
int n,m;read(n);read(m);
for(int i=1;i<=n;++i){
read(a[i]);
}build(1,1,n);
int op;
while(m--){
read(op);
if(op == 1){
read(L);read(R);
printf("%lld
",query(1,1,n));
}else if(op == 2){
read(L);read(R);read(val);
search(1,1,n);
}else if(op == 3){
read(pos);read(val);
modify(1,1,n);
}
}
return 0;
}