题目描述
如题,已知一个数列有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
参考代码
#include<stdio.h>
typedef struct
{
long long int flag;
long long int date;
}
stu;
stu a[1100000];
long long int n,m;
//
long long int max(long long int x,long long int y)
{
return x>y?x:y;
}
long long int min(long long int x,long long int y)
{
return x<y?x:y;
}
long long int inint(long long int wei,long long int l,long long int r)
{
long long int mid=(l+r)/2;
if(a[wei].flag)
{
if(l!=r)
{
a[wei*2].flag+=a[wei].flag;
a[wei*2+1].flag+=a[wei].flag;
}
a[wei].date+=a[wei].flag*(r-l+1);
//Ãüμ???êy
a[wei].flag=0;
}
}
long long int insert(long long int wei,long long int date,long long int l,long long int r,long long int x,long long int y)//μ±?°??,DT??μ?êy?μ,??±ê????,μ±?°????
{
inint(wei,x,y);
long long int mid=(x+y)/2;
if(x>=l&&y<=r)//?ú?a??????à ?±?
{
a[wei].flag+=date;
return 0;
} else
{
long long int dl,dr;
dl=max(l,x);
dr=min(r,y);
//·??ò
a[wei].date+=(dr-dl+1)*date;
long long int mid=(x+y)/2;
if(!(l>mid||r<x))
{
insert(wei*2,date,l,r,x,mid);
}
if(!(l>y||r<(mid+1)))
{
insert(wei*2+1,date,l,r,mid+1,y);
}
}
}
long long int search(long long int wei,long long int font,long long int x,long long int y)//μ±?°????,òa?ì?÷μ?????
{
inint(wei,x,y);
if(x==y&&x==font)
{
return a[wei].date;
} else
{
long long int mid=(x+y)/2;
if(font>=x&&font<=mid)
{
return search(wei*2,font,x,mid);
} else
{
return search(wei*2+1,font,mid+1,y);
}
}
}
int main()
{
scanf("%lld %lld",&n,&m);
for (long long int i=1;i<=n;i++)
{
long long int temp;
scanf("%lld",&temp);
insert(1,temp,i,i,1,n);
}
for (long long int i=0;i<m;i++)
{
long long int u,p,x,y;
scanf("%lld",&u);
if(u==1)
{
scanf("%lld %lld %lld",&p,&x,&y);
long long int tel=search(1,p,1,n);
//
long long int del=tel-(tel)%(y-x+1);
//é?3yμ?êy?μ
long long int add=tel/(y-x+1);
insert(1,-1*del,p,p,1,n);
insert(1,add,x,y,1,n);
} else
{
scanf("%lld",&p);
long long int tel=search(1,p,1,n);
printf("%lldn",tel);
}
}
}
解析
暂无