牛客编程巅峰赛S2赛季第4场代码
#define LL long long
#define DB double
#define pb push_back
#define pii pair<int,int>
#define mpt make_pair
#define fr first
#define sc second
#define M 200020//Size
#define INF 1000000000
#define INFLL 1000000000000000000
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define mod 1000000007//About
inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
inline int mul(LL x,LL y){return x*y%mod;}
inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
inline int qpow(int x,LL sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
class Solution {
public:
int sum[M],sqr[M],A[M],l[M],r[M];
#define Inv2 500000004
vector<int> getSum(vector<int>& a, vector<int>& query) {
// write code here
int top=0;
for(auto x:a) A[++top]=x;
int now=0,Q=0;
for(auto x:query){
now^=1;
if(now&1) l[++Q]=x;
else r[Q]=x;
}
vector<int>ans;ans.clear();
for(int i=1;i<=top;i++)
sum[i]=add(sum[i-1],A[i]),sqr[i]=add(sqr[i-1],mul(A[i],A[i]));
for(int i=1;i<=Q;i++){
int L=l[i],R=r[i];
int ret=mns(sum[R],sum[L-1]);
ret=mul(ret,ret),dec(ret,mns(sqr[R],sqr[L-1]));
ans.pb(mul(ret,Inv2));
}return ans;
}
}t; #牛客编程巅峰赛#
