80不知道错在哪
查看原帖
80不知道错在哪
234582
zpl__hhd楼主2021/3/21 15:52
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010,maxm=100010;
int n,m;
int a[maxn];
int ans;
struct node
{
	int l,r;
	ll w,f;
}tree[maxn*4];
inline void build(int k,int ll,int rr)
{
	tree[k].l=ll;
	tree[k].r=rr;
	if(ll==rr)
	{
		tree[k].w=a[ll];
		return ;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	build(k<<1,ll,mid);
	build((k<<1)+1,mid+1,rr);
	tree[k].w=tree[k<<1].w+tree[(k<<1)+1].w;
}
inline void down(int k)
{
	tree[k<<1].w+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].f;
	tree[k<<1].f+=tree[k].f;
	tree[(k<<1)+1].w+=(tree[(k<<1)+1].r-tree[(k<<1)+1].l+1)*tree[k].f;
	tree[(k<<1)+1].f+=tree[k].f;
	tree[k].f=0;
}
inline void add1(int k,int x,int y)
{
	if(tree[k].l==tree[k].r)
	{
		tree[k].w+=x;
		return;
	}
	down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(mid>=y)add1(k<<1,x,y);
	else add1(k<<1|1,x,y);
	tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
}
inline void add2(int k,int x,int a,int b)
{
	if(tree[k].l>=a&&tree[k].r<=b)
	{
		tree[k].w+=(tree[k].r-tree[k].l+1)*x;
		tree[k].f+=x;
		return;
	}
	down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(mid>=a)add2((k<<1),x,a,b);
	if(mid<b)add2(k<<1|1,x,a,b);
	tree[k].w=tree[k<<1].w+tree[(k<<1)+1].w;
}
inline void check(int k,int a,int b)
{
	if(tree[k].r<=b&&tree[k].l>=a)
	{
		ans+=tree[k].w;
		return ;
	}
	if(tree[k].f)down(k);
	int mid=tree[k].l+tree[k].r>>1;
	if(mid>=a)check((k<<1),a,b);
	if(mid<b)check((k<<1)+1,a,b);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=n;i;i--)
	a[i]-=a[i-1];
	//for(int i=1;i<=n;i++)
	//cout<<a[i]<<" ";
	int tot=0;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int g;
		scanf("%d",&g);
		if(g==1)
		{
			int a,b,x,y;
			scanf("%d%d%d%d",&a,&b,&x,&y);
			add1(1,x,a);
			add2(1,y,a+1,b);
			add1(1,-(x+(b-a)*y),b+1);
		}	
		else
		{
			tot++;
			ans=0;
			int b;
			scanf("%d",&b);
			
			check(1,1,b);
			//if(b==n)ans=tree[1].w;
			printf("%d %d\n",tot,ans); 
		}
	}
}
2021/3/21 15:52
加载中...