网站图片优化,科学小制作,代理平台注册网站建设,为什么要做网站题意:有一个序列a[]#xff0c;描述的是另一个序列ans[]每个位置单位时间的增量。每个单位时间每个位置都会增加一个单位对应增量。时间总长m#xff0c;每个单位时间包含有两种操作中的一个#xff1a;1.询问ans[]在[l,r]区间的和#xff1b;2.修改#xff1a;a[]在[l,r]… 题意:有一个序列a[]描述的是另一个序列ans[]每个位置单位时间的增量。每个单位时间每个位置都会增加一个单位对应增量。时间总长m每个单位时间包含有两种操作中的一个1.询问ans[]在[l,r]区间的和2.修改a[]在[l,r]区间1即[l,r]区间的ans[]增量1a[i], n,m ≤ 10^5 题解当时脑抽没想出来现在觉得好简单。。。考虑对每个位置维护一个关于时间的一次函数ya*xby是这个位置的答案x是时间然后就维护两个系数ab就可以了。维护的方法就是开两颗线段树分别维护a,b这就是个裸的区间加区间求和。位置i系数的表达式a (ai 修改次数)b - (修改的时间和)。随机跑了跑没啥大问题发现问题欢迎评论区指出。大概一辈子都是桶排选手吧。 #include bits/stdc.h
typedef long long ll;
const int N 1e5 100;
using namespace std;
int n,m;
ll a[N];
struct seg{int l,r;ll sum,tag;}tree[2][N2];
void push_up(int p,seg* tree) {tree[p].sum tree[p1].sum tree[p1|1].sum;
}
void push_down(int p,seg* tree) {if(tree[p].tag) {tree[p1].sum 1LL*(tree[p1].r - tree[p1].l 1)*tree[p].tag;tree[p1|1].sum 1LL*(tree[p1|1].r - tree[p1|1].l 1)*tree[p].tag;tree[p1].tag tree[p].tag;tree[p1|1].tag tree[p].tag;tree[p].tag 0;}
}
void build(int p, int l, int r, seg* tree) {tree[p].l l; tree[p].r r;tree[p].sum tree[p].tag 0;if(l r) {tree[p].sum a[l]; return;}int mid (l r) 1;build(p1, l, mid, tree), build(p1|1, mid1, r, tree);push_up(p, tree);
}
void buildb(int p, int l, int r, seg* tree) {tree[p].l l; tree[p].r r;tree[p].sum tree[p].tag 0;if(l r) return;int mid (l r) 1;buildb(p1, l, mid, tree), buildb(p1|1, mid1, r, tree);push_up(p, tree);
}
void add(int p, int l, int r, ll x,seg* tree) {if(tree[p].l l tree[p].r r) {tree[p].sum 1LL*(r-l1)*x;tree[p].tag x;return;}int mid (tree[p].l tree[p].r) 1;push_down(p, tree);if(r mid) add(p1, l, r, x, tree);else if(l mid) add(p1|1, l, r, x, tree);else add(p1, l, mid, x, tree), add(p1|1, mid1, r, x, tree);push_up(p, tree);
}
ll ask(int p, int l, int r,seg* tree) {if(tree[p].l l tree[p].r r) return tree[p].sum;push_down(p, tree);int mid (tree[p].l tree[p].r) 1;if(r mid) return ask(p1, l, r, tree);else if(l mid) return ask(p1|1, l, r, tree);else return ask(p1, l, mid, tree) ask(p1|1, mid1, r, tree);
}
//ll ans[N];
//void update(int l,int r){
// for(int i1;in;i)ans[i]a[i];
// for(int il;ir;i)a[i];
//}
//ll ask2(int l,int r){ll res0;
// for(int i1;in;i)ans[i]a[i];
// for(int il;ir;i)resans[i];
// return res;
//}
int main() {while(scanf(%d,n)) {for(int i1;in;i)scanf(%lld,a[i]);//,ans[i]0;build(1,1,n,tree[0]);buildb(1,1,n,tree[1]);scanf(%d,m);for(int i1;im;i) {char opt;int l,r;scanf( %c %d %d,opt,l,r);//optrand()%2;lrand()%n1,rrand()%n1;if(lr)swap(l,r);//printf(%d : [%d,%d]\n,opt,l,r);if(optQ){ll ans ask(1,l,r,tree[0])*i-ask(1,l,r,tree[1]);//ll ans2ask2(l,r);printf(%lld\n,ans);
// if(ans!ans2){
// printf(_______________________\n);
// }}else {add(1,l,r,1,tree[0]);add(1,l,r,i,tree[1]);
// update(l,r);}}}return 0;
} 转载于:https://www.cnblogs.com/RRRR-wys/p/9074789.html
