P1438 无聊的数列 0pts 求调
  • 板块灌水区
  • 楼主yueluoxingchen
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/9/14 22:44
  • 上次更新2024/9/15 11:07:06
查看原帖
P1438 无聊的数列 0pts 求调
554576
yueluoxingchen楼主2024/9/14 22:44

rt,玄关

听灌多,就来了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
#define debug() cout<<"qwq"<<endl
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;

const int N=1e5+10;
int n,m;
int input[N];

struct node{
	int l,r,sum,lztag;
}tr[N<<2];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline void write(int x)
{
	
	if (!x)
	{
		putchar('0');
		return;
	}
	int len = 0, k1 = x, c[40];
	if (k1 < 0) k1 = -k1, putchar('-');
	while (k1) c[len ++ ] = k1 % 10 ^ 48, k1 /= 10;
	while (len -- ) putchar(c[len]);
}

void pushup(int p)
{
	tr[p].sum=tr[ls].sum+tr[rs].sum;
}

void pushdown(int p)
{
	tr[ls].lztag+=tr[p].lztag;
	tr[rs].lztag+=tr[p].lztag;
	tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[p].lztag;
	tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[p].lztag;
	tr[p].lztag=0;
}

void build(int p,int l,int r)
{
	tr[p].l=l,tr[p].r=r;
	if(l==r)
	{
		tr[p].sum=input[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

void add(int p,int l,int r,int k)
{
	if(tr[p].l>=l && tr[p].r<=r)
	{
		tr[p].lztag+=k;
		tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
		return;
	}
	pushdown(p);
	if(tr[p].r<l || tr[p].l>r) return;
	if(l<=tr[ls].r) add(ls,l,r,k);
	if(r>=tr[rs].l) add(rs,l,r,k);
	pushup(p);
}

int query(int p,int l,int r)
{
	int ans=0;
	if(tr[p].l>=l && tr[p].r<=r)
	{
		ans+=tr[p].sum;
		return ans;
	}
	if(tr[p].l>r || tr[p].r<l) return 0;
	pushdown(p);
	if(l<=tr[ls].r) ans+=query(ls,l,r);
	if(r>=tr[rs].l) ans+=query(rs,l,r);
	return ans;
}


signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) input[i]=read();
	build(1,1,n);
	int opt;
	int L,R,K,D;
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			L=read(),R=read(),K=read(),D=read();
			add(1,L,L,K);
			if(L+1<=R) add(1,L+1,R,D);
			if(R+1<=n) add(1,R+1,R+1,-(K+D*(R-L)));
		}else{
			L=read();
			write(query(1,1,L));
			cout<<endl;
		}
	}
	return 0;
}
2024/9/14 22:44
加载中...