分块80分求助
  • 板块P2357 守墓人
  • 楼主_Give_up_
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/9/8 19:41
  • 上次更新2023/10/27 12:16:10
查看原帖
分块80分求助
516468
_Give_up_楼主2022/9/8 19:41
#include<bits/stdc++.h>
#define int long long
#define N 200010

using namespace std;

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

int id[N],a[N],b[N],s[N],len;

void add(int l,int r,int x)
{
	int start=id[l],end=id[r];
	if (start==end)
	{
		for (int i=l;i<=r;i++)
			a[i] += x,s[start] += x;
		return ;
	}
	for (int i=l;id[i]==start;i++)
		a[i] += x,s[start] += x;
	for (int i=start+1;i<end;i++)
		b[i] += x,s[i] += len*x;
	for (int i=r;id[i]==end;i--)
		a[i] += x,s[end] += x;
}

int query(int l,int r)
{
	int start=id[l],end=id[r],ans=0;
	if (start==end)
	{
		for (int i=l;i<=r;i++)
			ans = (ans+a[i]+b[start]);
		return ans;
	}
	for (int i=l;id[i]==start;i++)
		ans = (ans+a[i]+b[start]);
	for (int i=start+1;i<end;i++)
		ans = (ans+s[i]);
	for (int i=r;id[i]==end;i--)
		ans = (ans+a[i]+b[end]);
	return ans;
}

signed main()
{
	int n=read(),t=read();
	len = sqrt(n);
	for (int i=1;i<=n;i++)
		a[i]=read();
	while(t--)
	{
		int opt=read();
		if (opt==1)
		{
			int l=read(),r=read(),k=read();
			add(l,r,k);
		}
		else if (opt==2)
		{
			int k=read();
			a[1] += k;
			s[id[1]] += k;
		}
		else if (opt==3)
		{
			int k=read();
			a[1] -= k;
			s[id[1]] -= k;
		}
		else if (opt==4)
		{
			int l=read(),r=read();
			cout << query(l,r) << endl;
		}
		else cout << a[1] << endl;
	}
	return 0; 
}

这是怎么肥四?

2022/9/8 19:41
加载中...