首页 > 代码库 > 洛谷OJ P2846 LJJ的数学课
洛谷OJ P2846 LJJ的数学课
题目链接：传送门
题目大意：略
题目思路：线段树or树状数组
我们可以将区间值做一些调整。a*3+b*2+c=a+(a+b)+(a+b+c)
也就是利用前缀和建树。然后单点更新也就转换成了区间更新。修改一个点x时，需要修改 x~n 的值（因为是按前缀和建树
查询时也很简单，查询 x~y，则直接返回 x~y的值，再减去 （x-1的值）*（y-x+1），要把（1~x）的前缀和减去。
用线段树时要注意一个坑点，若查询时 x==1，则不用减去任何值直接输出即可，否则有可能RE（别问我怎么知道的
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>#include <stack>#include <cctype> #include <queue>#include <string>#include <vector>#include <set>#include <map>#include <climits>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r ///宏#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 1000005#define maxn 100005typedef pair<int,int> PII;typedef long long LL;int n,m,k,cnt,L,R;LL a[maxn],mrk[maxn<<2],v;struct Node{ int l,r; LL v;}node[maxn<<2];void build(int rt,int l,int r){ node[rt].l=l;node[rt].r=r; if(l==r){ node[rt].v=a[l]; return; } int mid=l+r>>1; build(lson); build(rson); node[rt].v=node[rt<<1].v+node[rt<<1|1].v;}inline void pushup(int rt){ int t=rt<<1; mrk[t]+=mrk[rt]; mrk[t|1]+=mrk[rt]; node[t].v+=mrk[rt]*(node[t].r-node[t].l+1); node[t|1].v+=mrk[rt]*(node[t|1].r-node[t|1].l+1); mrk[rt]=0;}void add(int rt,int l,int r){ if(L<=l&&r<=R){ node[rt].v+=v*(r-l+1); mrk[rt]+=v; return; } if(mrk[rt])pushup(rt); int mid=l+r>>1; if(R<=mid)add(lson); else if(L>mid)add(rson); else add(lson),add(rson); node[rt].v=node[rt<<1].v+node[rt<<1|1].v;}LL get(int rt,int l,int r){ if(L<=l&&r<=R) return node[rt].v; int mid=l+r>>1; if(mrk[rt])pushup(rt); if(R<=mid)return get(lson); else if(L>mid)return get(rson); else return get(lson)+get(rson);}int main(){ int i,j,x,y; scanf("%d%d",&n,&m); for(i=1;i<=n;++i){ scanf("%lld",&a[i]); a[i]+=a[i-1]; } build(1,1,n); while(m--){ scanf("%d%d%lld",&y,&x,&v); if(y==1){ L=x;R=n; add(1,1,n); } else{ L=x;R=(int)v; LL ans=get(1,1,n); if(x>1){ L=x-1;R=x-1; ans-=get(1,1,n)*(v-x+1); } printf("%lld\n",ans); } } return 0;}
洛谷OJ P2846 LJJ的数学课
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。