列表

详情

NC15936. Stock

描述

There are n stocks in the market, and after researching, the variance of the i-th stock’s price is ai per dollar you devoted.

Master Dong is reluctant to taking risk, so he wants to put the money on hand into n shares in a certain proportion, so that the total amount of total investment in all stocks fluctuates to a minimum.

We use the variance as a measure of volatility. We assume the money Master Dong invested into stocks is a real number. And we just define the unit minimum variance (UMV) as the variance of each dollar Mater Dong invested, under the optimal strategy.

There are m days now. For each day we have a cmd.

cmd = 1 indicates that the market was uniformly regulated on that day, and the stock price was adjusted by x% for the stocks from l to r.

cmd = 2 means if only stocks l to r are considered, what is UMV.

It’s guaranteed the answer is a rational number in the form of .  You only need to output in order to avoid accuracy error and high precision.

, all inputs are integers.

输入描述

The first line contains two intergers : n, m.

The next line contains n integers a1…an

The next m lines: first input cmd if cmd = 1, input
l, r, x, or l ,r.

输出描述

For every cmd = 2, output an integer in a line.

示例1

输入: 

5 4
1 2 3 4 5
2 1 2
2 1 5
1 2 3 2
2 1 5

输出: 

666666672
503649639
24407394

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 427ms, 内存消耗: 16864K, 提交时间: 2019-01-07 18:08:35 

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define rep0(i,r) for(int i=0,rr=(int)r;i<rr;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define maxn 600100
#define maxm
#define LL long long
using namespace std;

typedef struct{
 LL m,sum;
}Tr;
Tr tr[maxn*4];
int n,m;
LL a[maxn];
const LL mm=1e9+7;

LL inv(LL x)
{
 LL now=x,sum=1;
 LL kk=mm-2;
 while (kk) {
  if (kk&1) sum=sum*now%mm;
  now=now*now%mm;
  kk>>=1;
 }
 return sum;
}

void build(int x,int l,int r)
{
 tr[x].m=1;
 if (l==r) {
  tr[x].sum=a[l];
  return;
 }
 int mid=(l+r)>>1;
 build(x<<1 ,l  ,mid);
 build(x<<1|1,mid+1 ,r );
 tr[x].sum=(tr[x<<1].sum+tr[x<<1|1].sum)%mm;
}

void pushdown(int x)
{
 if (tr[x].m==1) return;
 tr[x<<1].sum =tr[x<<1].sum *tr[x].m%mm;
 tr[x<<1|1].sum =tr[x<<1|1].sum *tr[x].m%mm;
 tr[x<<1].m  =tr[x<<1].m  *tr[x].m%mm;
 tr[x<<1|1].m =tr[x<<1|1].m *tr[x].m%mm;
 tr[x].m=1;
}

void change(int x,int l,int r,int ll,int rr,LL y)
{
 if (ll<=l && r<=rr) {
  tr[x].sum=tr[x].sum*y%mm;
  tr[x].m=tr[x].m*y%mm;
  return; 
 }
 pushdown(x);
 int mid=(l+r)>>1;
 if (ll<=mid) change(x<<1,l,mid,ll,rr,y);
 if (rr>mid) change(x<<1|1,mid+1,r,ll,rr,y);
 tr[x].sum=(tr[x<<1].sum+tr[x<<1|1].sum)%mm;
}

LL ask(int x,int l,int r,int ll,int rr)
{
 if (ll<=l && r<=rr) return tr[x].sum;
 pushdown(x);
 int mid=(l+r)>>1;
 LL now=0;
 if (ll<=mid) now+=ask(x<<1,l,mid,ll,rr);
 if (rr>mid) now+=ask(x<<1|1,mid+1,r,ll,rr);
 return now%mm;
}

int main()
{
 scanf("%d %d",&n,&m);
 rep(i,1,n) {
  scanf("%lld",&a[i]);
  a[i]=inv(a[i]);
 }
 build(1,1,n);
 while (m--) {
  int op,l,r;
  LL x;
  scanf("%d",&op);
  if (op==1) {
   scanf("%d %d %lld",&l,&r,&x);
   if (x==1) continue;
   x=inv(x+100LL);
  // printf("%lld %lld\n",x*x%mm,x*x%mm*10000LL%mm);
   x=x*x%mm*10000LL%mm;
   change(1,1,n,l,r,x);
  } 
  else {
   scanf("%d %d",&l,&r);
   printf("%lld\n",inv(ask(1,1,n,l,r)));
  }
 }
 return 0;
}

上一题

© 2024 nowcoder.com