https://ac.nowcoder.com/acm/contest/917/J
两种操作 区间加
还有就是求区间 两两乘积和
作者: water201809070940881
链接:
首先, 我们发现
∑ri=l(ai*∑rj=i+1aj)=∑ri=l∑rj=i+1ai*aj∑i=lr(ai*∑j=i+1raj)=∑i=lr∑j=i+1rai*aj
有没有觉得后面这个东西很熟? 其实这个询问就是求区间的数两两相乘的和.
但是好像还是没法算啊!
我们再观察这个东西, 又可以发现
∑ri=l∑rj=i+1ai*aj=12*((∑ri=lai)2−∑ri=la2i)∑i=lr∑j=i+1rai*aj=12*((∑i=lrai)2−∑i=lrai2)
其实就是区间和的平方减掉区间平方和的 1212.
对于区间加, 线段树维护一下和与平方和就好了, 时间复杂度小到爆炸 O(Qlogn)O(Qlog?n)(实际的话因为数据随机, 后面 77 个点每个点标程跑的不到 100ms100ms, 开 1000ms1000ms 都是出题人良心了).
这个公式的来源其实就是
(a1+a2+...+an)2=a21+a22+...+a2n+2∑ni=1∑nj=i+1ai*aj(a1+a2+...+an)2=a12+a22+...+an2+2∑i=1n∑j=i+1nai*aj
然后移项一下, 提个式子, 分解一下就是这道题了.
其实就是维护区间平方和 和普通的区间和
- #include<bits/stdc++.h>
- using namespace std;
- //input by bxd
- #define rep(i,a,b) for(int i=(a);i<=(b);i++)
- #define repp(i,a,b) for(int i=(a);i>=(b);--i)
- #define RI(n) scanf("%d",&(n))
- #define RII(n,m) scanf("%d%d",&n,&m)
- #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
- #define RS(s) scanf("%s",s);
- #define ll long long
- #define pb push_back
- #define inf 0x3f3f3f3f
- #define CLR(A,v) memset(A,v,sizeof A)
- #define lson l,m,pos<<1
- #define rson m+1,r,pos<<1|1
- //////////////////////////////////
- const int N=1e6+5;
- ll sum1[N<<2],col[N<<2],sum2[N<<2];
- int n,m,op,a,b,c,v;
- void up(int pos)
- {
- sum1[pos]=sum1[pos<<1]+sum1[pos<<1|1];
- sum2[pos]=sum2[pos<<1]+sum2[pos<<1|1];
- }
- void down(int pos,int m)
- {
- if(col[pos])
- {
- sum2[pos<<1]+=(m-(m>>1))*col[pos]*col[pos]+2*sum1[pos<<1]*col[pos];
- sum2[pos<<1|1]+=(m>>1)*col[pos]*col[pos]+2*sum1[pos<<1|1]*col[pos];
- sum1[pos<<1]+=(m-(m>>1))*col[pos];
- sum1[pos<<1|1]+=(m>>1)*col[pos];
- col[pos<<1]+=col[pos];col[pos<<1|1]+=col[pos];
- col[pos]=0;
- }
- }
- void build(int l,int r,int pos)
- {
- col[pos]=0;
- if(r==l)
- {
- scanf("%lld",&sum1[pos]);
- sum2[pos]=sum1[pos]*sum1[pos];
- return ;
- }
- int m=(l+r)>>1;
- build(lson);
- build(rson);
- up(pos);
- }
- void update(int L,int R,ll v,int l,int r,int pos)
- {
- if(L<=l&&r<=R)
- {
- int len=(r-l+1);
- sum2[pos]+=len*v*v+sum1[pos]*2*v;
- sum1[pos]+=len*v;
- col[pos]+=v;
- return ;
- }
- int m=(r+l)>>1;
- down(pos,r-l+1);
- if(L<=m)update(L,R,v,lson);
- if(R>m)update(L,R,v,rson);
- up(pos);
- }
- ll query(int L,int R,int flag,int l,int r,int pos)
- {
- ll ans=0;
- if(L<=l&&r<=R)
- {
- if(flag==1)return sum1[pos];
- if(flag==2)return sum2[pos];
- }
- int m=(l+r)>>1;
- down(pos,r-l+1);
- if(L<=m)ans+=query(L,R,flag,lson);
- if(R>m)ans+=query(L,R,flag,rson);
- up(pos);
- return ans;
- }
- int main()
- {
- RII(n,m);
- build(1,n,1);
- rep(i,1,m)
- {
- RI(op);
- if(op==1)
- {
- RII(a,b);ll c;scanf("%lld",&c);
- update(a,b,c,1,n,1);
- }
- else
- {
- RII(a,b);
- ll temp1=query(a,b,1,1,n,1);
- ll temp2=query(a,b,2,1,n,1);
- cout<< (temp1*temp1-temp2)/2<<endl;
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3093621.html