分块求卡常
  • 板块P2357 守墓人
  • 楼主Resonate
  • 当前回复9
  • 已保存回复9
  • 发布时间2024/12/7 11:15
  • 上次更新2024/12/7 14:56:44
查看原帖
分块求卡常
753553
Resonate楼主2024/12/7 11:15

进来就帮我卡卡代码吧,谢谢

8s卡到1s

TLE on #21

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline 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*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m;
int a[222222];
int sum[222222],id;
int kuai[222222],gs;
signed main()
{
	// cin>>n>>m;
	n=read();
	m=read();
	gs=ceil(sqrt(n));
	for(int i=1;i<=n;i++)
	{
		// cin>>a[i];
		a[i]=read();
		sum[(i-1)/gs]+=a[i];
	}
	for(int i=1,op,l,r,c;i<=m;i++)
	{
		// cin>>op;
		op=read();
		if(op<=3)
		{
			l=r=1;
			if(op==1)
			{
				// cin>>l>>r>>c;
				l=read();
				r=read();
				c=read();
			}
			else if(op==2)
			{
				// cin>>c;
				c=read();
			}
			else if(op==3)
			{
				// cin>>c;
				c=read();
				// c=-c;
				c=~c+1;
			}
			if(l%gs!=1)
			{
				id=(l-1)/gs;
				int rr=(l-1)/gs*gs+gs;
				while(l<=r and l<=rr)
				{
					sum[id]+=c;
					a[l]+=c;
					l++;
				}
			}
			while(l/gs<=r/gs and r-l+1>=gs)
			{
				id=(l-1)/gs;
				kuai[id]+=c;
				l+=gs;
			}
			id=(l-1)/gs;
			while(l<=r)
			{
				sum[id]+=c;
				a[l]+=c;
				l++;
			}
		}
		else
		{
			if(op==4)
			{
				// cin>>l>>r;
				l=read();
				r=read();
			}
			else if(op==5)
			{
				l=r=1;
			}
			int s=0;
			if(l%gs!=1)
			{
				id=(l-1)/gs;
				int rr=(l-1)/gs*gs+gs;
				while(l<=r and l<=rr)
				{
					s+=a[l];
					s+=kuai[id];
					l++;
				}
			}
			while(l/gs<=r/gs and r-l+1>=gs)
			{
				id=(l-1)/gs;
				s+=kuai[id]*gs;
				s+=sum[id];
				l+=gs;
			}
			id=(l-1)/gs;
			while(l<=r)
			{
				s+=a[l];
				s+=kuai[id];
				l++;
			}
			cout<<s<<'\n';
		}
	}
}

为了找分块卡过的大佬,竟然找到了一堆超tj的。。。

2024/12/7 11:15
加载中...