树状数组求调
查看原帖
树状数组求调
1046158
A_897MIDSAM楼主2024/11/22 17:39

样例都过不了

#include<bits/stdc++.h>
using namespace std;
long long a[500005],c[500005];long long n,m;
long long lowbit(long long x)
{
	return x&(x^x-1);
}
void add(long long x,long long k)
{
	while(x<=n)
	{
		c[x]+=k;
		x+=lowbit(x);
	}
}
void aee(long long x,long long k)
{
	while(x<=n)
	{
		c[x]-=k;
		x+=lowbit(x);
	}
}
long long getsum(long long x)
{
	long long t=0;
	while(x>0)
	{
		t+=c[x],x-=lowbit(x);
	}
	return t;
}
void build(long long s,long long num){
	for(long long i=s;i<=n;i+=lowbit(i)) c[i]+=num;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		add(i,a[i]);
	} 
	for(long long i=1;i<=m;i++)
	{
		char x;
		cin>>x;
		if(x=='1')
		{
			long long o,p,q;
			cin>>o>>p>>q;
			build(o,q);
			build(p+1,-q);
			cout<<c[1]<<' '<<c[2]<<' '<<c[3]<<' '<<c[4]<<' '<<c[5]<<endl;
		}
		if(x=='2')
		{
			long long y;
			cin>>y;
			add(1,y);
			cout<<c[1]<<' '<<c[2]<<' '<<c[3]<<' '<<c[4]<<' '<<c[5]<<endl;
		}
		if(x=='3')
		{
			long long y;
			cin>>y;
			aee(1,y);
			cout<<c[1]<<' '<<c[2]<<' '<<c[3]<<' '<<c[4]<<' '<<c[5]<<endl;
		}
		if(x=='4'){
			long long y,z;
			cin>>y>>z;
			cout<<c[1]<<' '<<c[2]<<' '<<c[3]<<' '<<c[4]<<' '<<c[5]<<endl;
			cout<<getsum(z)-getsum(y-1)<<endl;
		}
		if(x=='5')
		{
			cout<<c[1]<<' '<<c[2]<<' '<<c[3]<<' '<<c[4]<<' '<<c[5]<<endl;
			cout<<getsum(1)<<endl;
		}
	}
	return 0;
}
2024/11/22 17:39
加载中...