当前位置：首页 > news >正文

P3924 康娜的线段树

news 2024/10/22 2:06:55

康娜的线段树 - 洛谷

一般问题转特殊化

发现

$ans=[a1+(a1+a2)+(a1+a2+a3+a4)]*\frac{1}{4}+[a2+(a1+a2)+(a1+a2+a3+a4)]*\frac{1}{4}+[a3+(a3+a4)+(a1+a2+a3+a4)]*\frac{1}{4}+[a4+(a3+a4)+(a1+a2+a3+a4)]*\frac{1}{4}$

化简

$ans=(a1+a2+a3+a4)+\frac{1}{2}*(a1+a2)+\frac{1}{2}*(a3+a4)+\frac{1}{4}*a1+\frac{1}{4}*a2+\frac{1}{4}*a3+\frac{1}{4}*a4$

合并同类项

$ans=(a1+a2+a3+a4)*(\frac{1}{4}+\frac{1}{2}+1)$

发现与深度有关

$ans=\sum_{i=1}^{n} a[i]*(\frac{1}{2^{dep[i]}}+\frac{1}{2^{dep[i]-1}}+...+\frac{1}{2^{0}})$

发现可以化简

$ans=\sum_{i=1}^{n} a[i]*(\frac{1+2+...+2^{dep[i]}}{2^{dep[i]}})$

$ans=\sum_{i=1}^{n} a[i]*\frac{\frac{1*(1-2^{dep[i]})}{1-2}}{2^{dep[i]}}$

$ans=\sum_{i=1}^{n} a[i]*\frac{2^{dep[i]-1}}{2^{dep[i]}}$

$ans=\sum_{i=1}^{n} a[i]*(1-\frac{1}{2^{dep[i]}})$

处理出每个点的深度就可以知道未修改的答案

考虑区间修改后对答案的影响

$ans=\sum_{i=1}^{n} a[i]*(1-\frac{1}{2^{dep[i]}})+x*\sum_{i=l}^{r}(1-\frac{1}{2^{dep[i]}})$

因此我们只需要维护一个前缀和就可以了

因为答案是整数，我们乘一个2^20即可(2^20==1e6)

code

#include <bits/stdc++.h>#define INF (1ll<<60)
#define eps 1e-6
#define tl(id) id<<1
#define tr(id) id<<1|1
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef vector<vector<int> > vii;
typedef vector<vector<vector<int> > > viii;
typedef vector<ll> vl;
typedef vector<vector<ll> > vll;
typedef vector<double> vd;
typedef vector<vector<double> > vdd;
typedef vector<string> vs;
#define time mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());//稳定随机卡牛魔 ull
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int n,m;ll qwq;cin>>n>>m>>qwq;vl a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}vl prefix(n+1),dep(n+1);vl t(30);t[0]=1;for(int i=1;i<=29;i++){t[i]=t[i-1]*2;}ll ans=0;int mxdep=20;auto build=[&](auto &build,int id,int l,int r,int d)->void{if(l==r){dep[l]=d;prefix[l]=2*t[mxdep]-t[mxdep]/t[d];ans+=a[l]*prefix[l];return;}int mid=(l+r)>>1;build(build,tl(id),l,mid,d+1);build(build,tr(id),mid+1,r,d+1);};build(build,1,1,n,0);for(int i=1;i<=n;i++){prefix[i]=prefix[i-1]+prefix[i];}ll g=gcd(qwq,t[mxdep]);qwq/=g,t[mxdep]/=g;for(int i=1;i<=m;i++){int l,r;ll x;cin>>l>>r>>x;ans+=(prefix[r]-prefix[l-1])*x;cout<<ans*qwq/t[mxdep]<<'\n';}return 0;
}

查看全文

http://www.mrgr.cn/news/55649.html