WA求条
  • 板块P10463 To the Max
  • 楼主FS_NEO
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/9 07:57
  • 上次更新2024/11/9 11:26:04
查看原帖
WA求条
537654
FS_NEO楼主2024/11/9 07:57

第一个线段树维护差分,第二个线段树维护A数组的值 WA On line 1679 column 1, read 2, expected 6. 求大佬看看哪里错了

#include<bits/stdc++.h>
#define R register
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int MAXN=500005;
ll n,m,a[MAXN],b[MAXN];
ll x,y,z;
char t;
struct node{
	int l,r;
	ll w;
}tree[MAXN*4];
struct node2{
	int l,r;
	ll w,d;
}tree2[MAXN*4];
ll ggcd(ll t1,ll t2){
	if(t2==0)return t1;
	return ggcd(t2,t1%t2);
}
inline ll gcd(ll t1,ll t2){
	if(t1<0)t1=-t1;
	if(t2<0)t2=-t2;
	return ggcd(t1,t2);
}
void build(int x,int l,int r){
	tree[x].l=l,tree[x].r=r;
	if(l==r){
		tree[x].w=b[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	tree[x].w=gcd(tree[x*2].w,tree[x*2+1].w);
}
void build2(int x,int l,int r){
	tree2[x].l=l,tree2[x].r=r;
	if(l==r){
		tree2[x].w=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build2(x*2,l,mid);
	build2(x*2+1,mid+1,r);
	tree2[x].w=tree2[x*2].w+tree2[x*2+1].w;
}
void down(int x){
	tree2[x*2].d+=tree2[x].d;
	tree2[x*2+1].d+=tree2[x].d;
	tree2[x*2].w+=tree2[x].d*(tree2[x*2].r-tree2[x*2].l+1);
	tree2[x*2+1].w+=tree2[x].d*(tree2[x*2+1].r-tree2[x*2+1].l+1);
	tree2[x].d=0;
}
void add(int x,int l,ll t){
	//cout<<tree[x].l<<" "<<tree[x].r<<" "<<tree[x].w<<"\n";
	if(tree[x].l==0)return ;
	if(tree[x].l==l&&tree[x].r==l)tree[x].w+=t;
	int mid=(tree[x].l+tree[x].r)>>1;
	if(l<=mid)return add(x*2,l,t);
	else add(x*2+1,l,t);
	tree[x].w=gcd(tree[x*2].w,tree[x*2+1].w);
}
void add2(int x,int l,int r,ll t){
	//cout<<tree2[x].l<<" "<<tree2[x].r<<" "<<tree2[x].w<<"\n";
	if(tree2[x].l>=l&&tree2[x].r<=r){
		tree2[x].w+=t*(tree2[x].r-tree2[x].l+1);
		tree2[x].d+=t;
		return ;
	}
	if(tree2[x].d)down(x);
	int mid=(tree2[x].l+tree2[x].r)>>1;
	if(l<=mid)add2(x*2,l,r,t);
	if(r>mid)add2(x*2+1,l,r,t);
	tree2[x].w=tree2[x*2].w+tree2[x*2+1].w;
}
ll check(int x,int l,int r){
	//cout<<tree[x].l<<" "<<tree[x].r<<" "<<tree[x].w<<"\n";
	if(tree[x].l>=l&&tree[x].r<=r)return tree[x].w;
	int mid=(tree[x].l+tree[x].r)>>1;
	ll tmp=0;
	if(l<=mid)tmp=check(x*2,l,r);
	if(r>mid)tmp=gcd(tmp,check(x*2+1,l,r));
	return tmp;
}
ll check2(int x,int l){
	if(tree2[x].l==l&&tree[x].r==l)return tree2[x].w;
	if(tree2[x].d)down(x);
	int mid=(tree2[x].l+tree2[x].r)>>1;
	if(l<=mid)return check2(x*2,l);
	return check2(x*2+1,l);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}
	build(1,1,n);
	build2(1,1,n);
	//for(int i=1;i<=2*n;i++)cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].w<<"\n";
	for(int i=1;i<=m;i++){
		cin>>t;
		if(t=='C'){
			cin>>x>>y>>z;
			add2(1,x,y,z);
			add(1,x,z);
			if(y!=n)add(1,y+1,-z);
		}
		else{
			cin>>x>>y;
			//cout<<"*"<<check2(1,x)<<" "<<check(1,x+1,y)<<"\n";
			if(x==y)cout<<abs(check2(1,x))<<"\n";
			else cout<<gcd(check2(1,x),check(1,x+1,y))<<"\n";
		}
	}
	return 0;
}
2024/11/9 07:57
加载中...