站外题求调
  • 板块学术版
  • 楼主普通的壹佰
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/20 13:09
  • 上次更新2023/10/27 14:28:06
查看原帖
站外题求调
457768
普通的壹佰楼主2022/8/20 13:09

有没有人帮我调线段树啊,一直没调出来,不知道哪里错了。。

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll mo=19260817;
ll n,m,D,sum,aa[N],pow[N],sn[N],fi[N];
ll tr0[N<<2],las0[N<<2],tr1[N<<2],las1[N<<2];
ll tr2[N<<2],las2[N<<2],tr3[N<<2],f1[N<<2],f2[N<<2];

ll num(ll qwq){return (qwq%mo+mo)%mo;}
ll dc(ll a,ll b){return num(b*(b+1)/2-a*(a+1)/2);}
ll qpow(ll a,ll k){
	ll ans=1;
	while(k){
		if(k&1) ans=ans*a%mo;
		a=a*a%mo;
		k>>=1;
	}
	return ans;
}

void build(int node,int l,int r){
	if(l==r){
		scanf("%lld",&tr0[node]);
		return;
	}
	int mid=l+r>>1;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
	tr0[node]=tr0[node<<1]+tr0[node<<1|1];
	tr0[node]%=mo;
}

void pushdown0(int node,int l,int r){
	if(las0[node]){
		int mid=l+r>>1;
		las0[node<<1]+=las0[node];
		las0[node<<1|1]+=las0[node];
		tr0[node<<1]+=las0[node]*(mid-l+1);
		tr0[node<<1|1]+=las0[node]*(r-mid);
		tr0[node<<1]%=mo,tr0[node<<1|1]%=mo;
		las0[node]=0;
	}
}

void update0(int node,int l,int r,int x,int y,ll k){
	if(x<=l&&y>=r){
		tr0[node]+=k*(r-l+1);
		las0[node]+=k;
		tr0[node]%=mo,las0[node]%=mo;
		return;
	}
	pushdown0(node,l,r);
	int mid=l+r>>1;
	if(x<=mid) update0(node<<1,l,mid,x,y,k);
	if(y>=mid+1) update0(node<<1|1,mid+1,r,x,y,k);
	tr0[node]=tr0[node<<1]+tr0[node<<1|1];
	tr0[node]%=mo;
}

void pushdown1(int node,int l,int r){
	if(las1[node]){
		int mid=l+r>>1;
		las1[node<<1]+=las1[node];
		las1[node<<1|1]+=las1[node];
		tr1[node<<1]+=las1[node]*dc(l-1,mid);
		tr1[node<<1|1]+=las1[node]*dc(mid,r);
		tr1[node<<1]%=mo,tr1[node<<1|1]%=mo;
		las1[node]=0;
	}
}

void update1(int node,int l,int r,int x,int y,ll k){
	if(x<=l&&y>=r){
		tr1[node]+=k*dc(l-1,r);
		las1[node]+=k;
		tr1[node]%=mo,las1[node]%=mo;
		return;
	}
	pushdown1(node,l,r);
	int mid=l+r>>1;
	if(x<=mid) update1(node<<1,l,mid,x,y,k);
	if(y>=mid+1) update1(node<<1|1,mid+1,r,x,y,k);
	tr1[node]=tr1[node<<1]+tr1[node<<1|1];
	tr1[node]%=mo;
}

void pushdown2(int node,int l,int r){
	if(las2[node]){
		int mid=l+r>>1;
		ll rlas=las2[node]*pow[mid-l+1]%mo;
		las2[node<<1]+=las2[node];
		las2[node<<1|1]+=rlas;
		tr2[node<<1]+=las2[node]*sn[mid-l+1];
		tr2[node<<1|1]+=rlas*sn[r-mid];
		tr2[node<<1]%=mo,tr2[node<<1|1]%=mo;
		las2[node<<1]%=mo,las2[node<<1|1]%=mo;
		las2[node]=0;
	}
}

void update2(int node,int l,int r,int x,int y,ll k){
	if(x<=l&&y>=r){
		tr2[node]+=k*(sn[r-x+1]-sn[l-x]);
		las2[node]+=k;
		tr2[node]%=mo,las2[node]%=mo;
		return;
	}
	pushdown2(node,l,r);
	int mid=l+r>>1;
	if(x<=mid) update2(node<<1,l,mid,x,y,k);
	if(y>=mid+1) update2(node<<1|1,mid+1,r,x,y,k);
	tr2[node]=tr2[node<<1]+tr2[node<<1|1];
	tr2[node]%=mo;
}

void pushdown3(int node,int l,int r){
	
	if(f1[node]||f2[node]){
		int mid=l+r>>1,pos=mid-l+2,sop=r-mid+1;
		ll inf1=fi[pos-1]*f2[node]+fi[pos-2]*f1[node];
		ll inf2=fi[pos]*f2[node]+fi[pos-1]*f1[node];
		
		f1[node<<1]+=f1[node];
		f2[node<<1]+=f2[node];
		tr3[node<<1]+=fi[pos-1]*f1[node]+(fi[pos]-1)*f2[node];
		f1[node<<1]%=mo,f2[node<<1]%=mo,tr3[node<<1]%=mo;
		
		f1[node<<1|1]+=inf1;
		f2[node<<1|1]+=inf2;
		tr3[node<<1|1]+=fi[sop-1]*inf1+(fi[sop]-1)*inf2;
		f1[node<<1|1]%=mo,f2[node<<1|1]%=mo,tr3[node<<1|1]%=mo;
		
		f1[node]=f2[node]=0;
	}
}

void update3(int node,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		f1[node]+=fi[l-x+1];
		f2[node]+=fi[l-x+2];
		tr3[node]+=fi[r-l+1]*fi[l-x+1]+(fi[r-l+2]-1)*fi[l-x+2];
		f1[node]%=mo,f2[node]%=mo,tr3[node]%=mo;
		return;
	}
	pushdown3(node,l,r);
	int mid=l+r>>1;
	if(x<=mid) update3(node<<1,l,mid,x,y);
	if(y>=mid+1) update3(node<<1|1,mid+1,r,x,y);
	tr3[node]=tr3[node<<1]+tr3[node<<1|1];
	tr3[node]%=mo;
}

void find(int node,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		sum+=tr0[node]+tr1[node]+tr2[node]+tr3[node];
		
		return;
	}
	pushdown0(node,l,r);
	pushdown1(node,l,r);
	pushdown2(node,l,r);
	pushdown3(node,l,r);
	int mid=l+r>>1;
	if(x<=mid) find(node<<1,l,mid,x,y);
	if(y>=mid+1) find(node<<1|1,mid+1,r,x,y);
}

int main(){
	scanf("%lld%lld%lld",&n,&m,&D);
	build(1,1,n);
	ll inv=qpow(D-1,mo-2);pow[0]=1;
	for(int i=1;i<=n;i++){
		pow[i]=pow[i-1]*D%mo;
		sn[i]=num((pow[i]-1)*inv);
	}
	fi[0]=0,fi[1]=1;
	for(int i=2;i<=n;i++)
		fi[i]=(fi[i-1]+fi[i-2])%mo;
	
	for(int i=1;i<=m;i++){
		int op,l,r;
		ll k,d;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lld%lld",&k,&d);
			update0(1,1,n,l,r,num(k-d*l));
			update1(1,1,n,l,r,d);
		}
		else if(op==2){
			scanf("%lld",&k);
			update2(1,1,n,l,r,k);
		}
		else if(op==3){
			update3(1,1,n,l,r);
		}
		else{
			sum=0;
			find(1,1,n,l,r);
			printf("%lld\n",num(sum));
		}
	}
	return 0;
}

无语了,这道题赛时3h30min都没调出来,所以这种多合一,思维量低,巨大码量题,出出来就是为了恶心人吗?

2022/8/20 13:09
加载中...