简单题

简单题

时间： 2ms        内存：128M

描述：

如题，已知一个数列有n个数，m次操作，你需要进行下面两种操作：
1. 將某个位置的数平均分给一个区间，不能平均分的留下
2. 求出某个位置的值

输入：

第一行两个正整数n、m(1<=n,m<=500,000); n表示数字个数,m表示操作的个数
第二行n个整数，a1,a2,a3,...,an代表数列的初始值 (ai<=10^9)
接下来m行，每行2或4个整数，表示一个操作，具体如下：
操作1：1 p,x,y 将第p个数平均分给区间[x,y] (1<=p,x,y<=n)
操作2：2 p        输出第p个数的值
输入数据过大，建议使用scanf输入

输出：

对于每个操作2，输出一个整数

示例输入：

5 6
1 2 3 4 8
1 5 1 5
2 1 
2 2 
2 3 
2 4
2 5

示例输出：

2
3
4
5
4

提示：

参考答案（内存最优[5924]）：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<string>
#define ms(arr) memset(arr,0,sizeof(arr))
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int inf=2147483647;
const int MAX=5e5+5;
ll treenum[MAX];
int n,m;

int Lowbit(int i)
{
    return i&-i;
}

void fix(int x,ll v)
{
    while(x<=n){
        treenum[x]+=v;
        x+=Lowbit(x);
    }
}

ll query(int x)
{
    ll ans=0;
    while(x){
        ans+=treenum[x];
        x-=Lowbit(x);
    }
    return ans;
}

int main()
{
    int i,j,c,p,x,y;
    scanf("%d %d",&n,&m);
    ll now=0,pre=0;
    rep(i,1,n){
        cin>>now;
        fix(i,now-pre);
        pre=now;
    }
    while(m--){
        scanf("%d",&c);
        if(c==1){
            scanf("%d %d %d",&p,&x,&y);
            ll v=query(p)/(y-x+1);
            if(v==0)continue;
            fix(p,-v*(y-x+1));
            fix(p+1,v*(y-x+1));
            fix(x,v);
            fix(y+1,-v);
        }else{
            scanf("%d",&p);
            printf("%lld\n",query(p));
        }
    }
    return 0;
}

参考答案（时间最优[456]）：

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int maxn=5e5+7;
ll a[maxn],c[maxn];
ll n,m;
ll lowbit(ll x)
{
    return x&(-x);
}
void update(ll i,ll k)
{
    while(i<=n)
    {
        c[i]+=k;
        i+=lowbit(i);
    }
    return ;
}
ll query(ll i)
{
    ll ans=0;
    while(i>0)
    {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    a[0]=0;
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        update(i,a[i]-a[i-1]);
    }
    while(m--)
    {
        ll p,x,y,num,add,z;
        scanf("%lld",&z);
        if(z==1)
        {
            scanf("%lld %lld %lld",&p,&x,&y);
            add=query(p)/(y-x+1);
           // cout<<query(p)<<" ---- "<<add<<endl;
            update(x,add);
            update(y+1,-add);
            update(p,-(y-x+1)*add);
            update(p+1,(y-x+1)*add);
        }
        else
        {
            scanf("%lld",&num);
            printf("%lld\n",query(num));
        }
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。