这棵树多漂亮啊
查看原帖
这棵树多漂亮啊
578628
Undead2008楼主2022/10/27 18:41

这棵漂亮的线段树全WA了。求助。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1000010
#define upper 1e10 
struct hgint{
	int val;
	bool ist;
	hgint operator - (int x){
		if(ist)return {0,1};
		return {max(val-x,1ll*1),0};
	}
	hgint operator * (int x){
		if(ist)return {0,1};
		if(1ll*val*x>upper) return {0,1};
		return {1ll*val*x,0};
	}
	bool operator <= (int x){
		return (!ist&&val<=x);
	}
};
int n,T,q,cnt[inf<<2];string str;
hgint val[inf];
void bdtree(int x,int l,int r){
	if(l==r){cnt[x]=(val[l]<=T);return;}
	int mid=(l+r)>>1;
	bdtree(x<<1,l,mid);bdtree(x<<1|1,mid+1,r);
	cnt[x]=cnt[x<<1]+cnt[x<<1|1];
}
void modify(int x,int l,int r,int pos,int ty,int dlt){
	if(l==r){
		if(ty==1)val[l]=val[l]-dlt;
		if(ty==2)val[l]=val[l]*dlt;
		if(ty==3)val[l]={dlt,0};
		cnt[x]=(val[l]<=T);
		return void();
	}
	int mid=(l+r)>>1;
	if(pos<=mid)modify(x<<1,l,mid,pos,ty,dlt);
	else modify(x<<1|1,mid+1,r,pos,ty,dlt);
	cnt[x]=cnt[x<<1]+cnt[x<<1|1]; 
	return void();
}
int query(int x,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return cnt[x]*600;
	int mid=(l+r)>>1,ret=0;
	if(ql<=mid)ret+=query(x<<1,l,mid,ql,qr);
	if(qr>mid )ret+=query(x<<1|1,mid+1,r,ql,qr);
	return ret;
}
signed main(){
	cin>>n>>T;
	for(int i=1,v;i<=n;i++)
		cin>>v,val[i]={v,0};
	bdtree(1,1,n);cin>>q;
	for(int i=1,pos,dlt;i<=q;i++){
		cin>>str>>pos>>dlt;
		if(str=="BookCity")modify(1,1,n,pos,1,dlt);
		if(str=="Guy")modify(1,1,n,pos,2,dlt);
		if(str=="tingtime")modify(1,1,n,pos,3,dlt);
		if(str=="Zero")cout<<query(1,1,n,pos,dlt)<<endl;
	}
}
2022/10/27 18:41
加载中...